Tag Archives: ACM

[ACM] POJ1573解题报告

Speak

夜里边切题边等电影缓冲真是太爽了..
正在慢慢的切某人切不下来的题..
1573挺简单的 以后这种模拟的数组我都从1开始就好了..省得墨迹墨迹的整的头大..

主要就是想到一个监视指针的方法..做个tester指针数组 对应map上面所有的单元
这样本来看不懂的指针地址(0x22fb18这样)就能通过查找tester来获得它的位置(tester是一个地址的数组 找到对应的 然后数数)

详见下图 ap是tester,p==0x22fb18，在ap中排第10个，则p==*(ap[9])

#include <cstdio>
#include <cstring>
typedef struct spot {
    char c;
    bool b;
    int n;
} Spot;
Spot *p;

void move() {
    switch(p->c) {
        case 'N':
            p-=12;
            break;
        case 'S':
            p+=12;
            break;
        case 'E':
            p+=1;
            break;
        case 'W':
            p-=1;
    }
}

int main() {
    int i,enter,j,n,rows,cols;
    Spot a[12][12];
    /*Tester
    Spot *(ap[3][6]);
    for(i=0;i<3;i++)
        for(j=0;j<7;j++)
            ap[i][j]=a[i]+j;*/
    while(1) {
        for(i=0;i<144;i++) {
            ((Spot *)a+i)->c=-1;
            (a[0]+i)->b=false;
        }
        n=0;
        scanf("%d%d%d",&rows,&cols,&enter);
        if(!rows&&!cols&&!enter)
            return 0;
        getchar();
        for(i=1;i<=rows;i++) {
            for(j=1;j<=cols;j++)
                a[i][j].c=getchar();
            getchar();
        }
        p=a[1]+enter;
        /* TESTER
        for(i=0;i<rows;i++) {
            for(j=1;j<=cols;j++)
                printf("%c",a[i][j].c);
            printf("\n");
        } */
        while(1) {
            p->b=true;
            p->n=n;
            if(p->c==-1) {
                printf("%d step(s) to exit\n",n);
                break;
            }
            move();
            if(p->b) {
                printf("%d step(s) before a loop of %d step(s)\n",p->n,n+1-p->n);
                break;
            }
            n++;
        }
    }
    return 0;
}

[ACM] POJ1009解题报告

4 Replies

做了一夜 再也不想敲键盘了..等等再报告 贴出来先 (其实又没人看….)

没有什么任何优化 直接0msAC 真不好意思 XD

#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXNUM 2000

typedef struct pair {
    int v,l;
} Pair;

typedef struct pointer {
    int p,num;
} Pointer;

Pair a[MAXNUM],r[MAXNUM];
int width,prow,rp;
Pointer p2,p5,p8;

void calc();
void set(Pointer *target,int p,int num);
void go(int spit,int steps);
void gop(Pointer *p,int steps);
int pre(Pointer p);
int next(Pointer p);
int spit();;

int main() {
    int i;
    while(1) {
        rp=0;
        scanf("%d",&width);
        if(width==0) {
            printf("0\n");
            return 0;
        }
        for(i=1;;i++) {
            scanf("%d%d",&a[i].v,&a[i].l);
            if(!a[i].v&&!a[i].l)
                break;
        }
        a[0].v=a[i].v=-1;
        a[0].l=a[i].l=width;
        r[0].v=-1;
        r[1].l=0;
        calc();
        printf("%d\n",width);
        for(i=1;;i++) {
            printf("%d %d\n",r[i].v,r[i].l);
            if(!r[i].v&&!r[i].l)
                break;
        }
    }
}

void calc() {
    int i,counter;
    int x,y,z,steps;
    prow=1;
    set(&p2,0,1);
    set(&p5,1,1);
    counter=0;
    for(i=1;counter<=width;i++)
        counter+=a[i].l;
    i--;
    set(&p8,i,width-counter+a[i].l+1);
    while(1) {
        if(a[p5.p].v==-1)
            break;
        x=a[p2.p].l-p2.num;
        y=a[p5.p].l-p5.num;
        z=a[p8.p].l-p8.num;
        steps=x>y?y:x;
        steps=steps>z?z:steps;
        if(steps<3) {
            go(spit(),1);
            continue;
        }                           //可在此处插入判断边界程序
        go(spit(),1);
        go(spit(),steps-1);
    }
    rp++;
    r[rp].v=r[rp].l=0;
}

void set(Pointer *target,int p,int num) {
    target->p=p;
    target->num=num;
}

int spit(){
    int result=0,i=0,temp,x=a[p5.p].v;
    bool top=false,bottom=false;
    if(a[p2.p].v==-1)
        top=true;
    if(a[p8.p].v==-1)
        bottom=true;
    if(prow!=1) {
        if(!top)
            result=(temp=fabs(pre(p2)-x))>result?temp:result;
        result=(temp=fabs(pre(p5)-x))>result?temp:result;
        if(!bottom)
            result=(temp=fabs(pre(p8)-x))>result?temp:result;
    }
    if(prow!=width) {
        if(!top)
            result=(temp=fabs(next(p2)-x))>result?temp:result;
        result=(temp=fabs(next(p5)-x))>result?temp:result;
        if(!bottom)
            result=(temp=fabs(next(p8)-x))>result?temp:result;
    }
    if(!top)
        result=(temp=fabs(a[p2.p].v-x))>result?temp:result;
    if(!bottom)
        result=(temp=fabs(a[p8.p].v-x))>result?temp:result;
    return result;
}

int pre(Pointer p) {
    if(p.num==1)
        return(a[p.p-1].v);
    else
        return(a[p.p].v);
}

int next(Pointer p) {
    if(p.num==a[p.p].l)
        return(a[p.p+1].v);
    else
        return(a[p.p].v);
}

void go(int spit,int steps) {
    if(r[rp].v==spit)
        r[rp].l+=steps;
    else {
        rp++;
        r[rp].v=spit;
        r[rp].l=steps;
    }
    gop(&p2,steps);
    gop(&p5,steps);
    gop(&p8,steps);
    prow=(prow+steps-1)%width+1;
}

void gop(Pointer *p,int steps) {
    p->num+=steps;
    while(p->num>a[p->p].l) {
        p->num-=a[p->p].l;
        p->p++;
    }
}

[ACM] POJ1135解题报告

Speak

Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase “domino effect” comes from).

啥都不用说了..原来我想出来的算法 在五十年前已经被一名叫做的Dijkstra同学提出来了.. 恨啊 晚生半个世纪
Dijkstra’s algorithm传送门
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
右边图示很销魂

前面都差不多就是当结果是between a  and b时需要技巧，我是在所有dominoes都倒下后将所有连接的节点进行计算，多米诺卡在ab之间的时间等于(a.time+b.time+ab之间时间)/2，当b是由a推倒时，这个数值就等于b的时间，不可能超过最长时间，因而无需额外考虑，方便啊！

#include <cstdio>
#include <cstring>
#define MAXNUM 500

typedef struct card{
    int time;
    int l[MAXNUM+1];
    bool touched,out;
} Card;

int n,p,p1=-1,p2;
float time;
Card a[MAXNUM+1];

void dij();
void between();

int main() {
    int c,b,l,m;
    int i,N=1;
    Card ini;   //used to initialize
    memset(ini.l,-1,sizeof(int)*(MAXNUM+1));
    ini.time=0;
    ini.touched=false;
    ini.out=false;
    scanf("%d%d",&n,&m);
    while(n!=0) {
        for(i=1;i<=MAXNUM;i++)
            a[i]=ini;
        p1=-1;
        time=0;

        for(i=0;i<m;i++) {
            scanf("%d%d%d",&c,&b,&l);
            a[c].l[b]=a[b].l[c]=l;
        }
        a[1].touched=true;
        for(i=1;i<=n;i++)
            dij();
        between();
        printf("System #%d\nThe last domino falls after %.1f seconds, ",N,time);
        if(p1!=-1)
            printf("between key dominoes %d and %d.\n\n",p1,p2);
        else
            printf("at key domino %d.\n\n",p);
        N++;
        scanf("%d%d",&n,&m);
    }
    return 0;
}

void dij() {
    int i,j,reachtime;
    p=-1;
    for(i=1;i<=n;i++) {
        if(!a[i].touched||a[i].out)
            continue;
        if(p==-1||a[p].time>a[i].time)
            p=i;
    }
    for(i=1;i<=n;i++) {
        if(a[p].l[i]==-1||a[i].out)
            continue;
        reachtime=a[p].time+a[p].l[i];
        if(!a[i].touched||a[i].time>reachtime) {
            a[i].time=reachtime;
            a[i].touched=true;
        }
    }
    a[p].out=true;
    time=a[p].time;
}

void between() {
    int i,j;
    float t;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++) {
            if(a[i].l[j]==-1||(t=(float)(a[i].time+a[j].time+a[i].l[j])/2)<=time)
                continue;
            p1=i;
            p2=j;
            time=t;
        }
}

[ACM] POJ1125 解题报告

Speak

老田用的弗洛伊德 我觉得我的快一点..不知道叫啥算法 无招胜有招了 (墨镜)
每个人身上两种属性 传到他需要的时间(int time)以及他是否往下传播(bool set)
unit向他的contact传播 => contact.time=unit.settime

[contact](传播到此contact所需时间)+unit.time

1.开始选择的人start, start.set=true
2.扫描所有的unit, 如果set==true则对他的每一个contact判断, 若contact.time>unit.time+unit.setting(contact), 则用这个较快的time赋值,并且contact.set=true, 下一轮用新的time传播给这个contact的contact们
3.重复2知道所有unit.set==false为止
4.判断是否有unit没有触及到

#include <cstdio>

 typedef struct unit {
     int num;
     int contact[99];
     int settime[99];
     bool set;
     int time;
 } Unit;

 typedef struct aa {
     int start;
     int time;
 } Result;

void calc();
int search();

Unit a[101];
Result x,result;
int n;

int main() {
    int i,j,start;
    scanf("%d",&n);
    while(n) {
        for(i=1;i<=n;i++) {
            scanf("%d",&a[i].num);
            for(j=0;j<a[i].num;j++)
                scanf("%d%d",&a[i].contact[j],&a[i].settime[j]);
        }
        result.start=-1;
        for(start=1;start<=n;start++) {
            for(i=1;i<=n;i++) {
                a[i].set=false;
                a[i].time=-1;
            }
            a[start].set=true;
            a[start].time=0;
            i=0;
            while(i<n+1) {
                calc();
                for(i=1;i<=n;i++)
                    if(a[i].set==true)
                        break;
            }
            x.time=search();
            x.start=start;
            for(i=1;i<=n;i++)
                if(a[i].time==-1) {
                    x.start=-1;
                    break;
                }
            if(x.start==-1)
                continue;
            if(x.time<result.time||result.start==-1)
                result=x;
        }
        if(result.start==-1)
            if(n==0)
                printf("0 0\n");
            else
                printf("disjoint\n");
        else
            printf("%d %d\n",result.start,result.time);
        scanf("%d",&n);
    }
    return 0;
}

void calc() {
    int i,j,spreadtime;
    for(i=1;i<=n;i++)
        if(a[i].set) {
            for(j=0;j<a[i].num;j++) {
                spreadtime=a[i].time+a[i].settime[j];
                if(a[a[i].contact[j]].time>spreadtime||a[a[i].contact[j]].time==-1) {
                    a[a[i].contact[j]].time=spreadtime;
                    a[a[i].contact[j]].set=true;
                }
            }
            a[i].set=false;
        }
}

int search() {
    int max,i;
    max=a[1].time;
    for(i=2;i<=n;i++)
        if(a[i].time>max)
            max=a[i].time;
    return max;
}

[ACM] POJ1661 解题报告

Speak

AC大美..之前一直WA到死 把search部分做成函数就AC了 实在不知道哪错了回头再看..
动态规划能不用递归就不用 循环从底层开始算到Jimmy落脚点那一层

#include <cstdio>
#include <cstdlib>
typedef struct flat {
    int l,r,h,lmin,rmin;
} Flat;
Flat a[1001];
int N,MAX;

void search(int i,int k,bool bLeft);
int compare(const void *a,const void *b);

int main() {
    int i,j,location;
    int t,X,Y;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d",&N,&X,&Y,&MAX);
        for(i=1;i<=N;i++)
            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h);
        qsort(a+1,N,sizeof(a[0]),compare);
        for(i=1;i<=N+1;i++) {
            if(a[i].l<=X&&a[i].r>=X||i==N+1) {
                a[i-1].l=a[i-1].r=X;
                a[i-1].h=Y;
                location=i-1;
                break;
                }
        }
        for(i=N;i>=location;i--) {
            for(j=i+1;j<=N;j++)
                if(a[j].h!=a[i].h)
                    break;
        search(i,j,true);
        search(i,j,false);
        }
        printf("%d\n",a[location].lmin);
    }
    return 0;
}

void search(int i,int k,bool bLeft) {
    int x,*min,gotol,gotor,fall;
    if(bLeft) {
        x=a[i].l;
        min=&a[i].lmin;
    }
    else {
        x=a[i].r;
        min=&a[i].rmin;
    }
    for(;k<=N;k++)
        if(a[k].l<=x&&a[k].r>=x)
            break;

    if(k==N+1)
        if(a[i].h>MAX)
            *min=-1;
        else
            *min=a[i].h;
    else {
        fall=a[i].h-a[k].h;
        if(fall>MAX)
            *min=-1;
        else {
            gotol=fall+x-a[k].l+a[k].lmin;
            gotor=fall+a[k].r-x+a[k].rmin;
            if(a[k].lmin==-1)
                if(a[k].rmin==-1)
                    *min=-1;
                else
                    *min=gotor;
            else
                if(a[k].rmin==-1)
                    *min=gotol;
                else
                    if(gotol<gotor)
                        *min=gotol;
                    else
                        *min=gotor;
        }
    }
}

int compare(const void *a,const void *b) {
    return ((Flat *)b)->h-((Flat *)a)->h;
}

[ACM] Longest increasing subsequence

Speak 
#include <cstdio>
int main() {
    int a[1000],maxlen[1000]={0};
    int *p,*max=maxlen;
    int i,j,N;
    scanf("%d",&N);
    for(i=0;i<N;i++) {
        scanf("%d",a+i);
        p=maxlen+i;
        for(j=0;j<i;j++)
            if(a[j]<a[i]&&maxlen[j]>*p)
                p=maxlen+j;                 //求以a[i]为终点的最长上升子序列长度
        maxlen[i]=*p+1;
        if(maxlen[i]>*max)
            max=maxlen+i;
    }
    printf("%d\n",*max);
    return 0;
}