Tag Archives: POJ

[ACM] POJ1009解题报告

4 Replies

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

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

view source
print?
1#include <cstdio>
2#include <cstring>
3#include <cmath>
4#define MAXNUM 2000
5 
6typedef struct pair {
7    int v,l;
8} Pair;
9 
10typedef struct pointer {
11    int p,num;
12} Pointer;
13 
14Pair a[MAXNUM],r[MAXNUM];
15int width,prow,rp;
16Pointer p2,p5,p8;
17 
18void calc();
19void set(Pointer *target,int p,int num);
20void go(int spit,int steps);
21void gop(Pointer *p,int steps);
22int pre(Pointer p);
23int next(Pointer p);
24int spit();;
25 
26int main() {
27    int i;
28    while(1) {
29        rp=0;
30        scanf("%d",&width);
31        if(width==0) {
32            printf("0\n");
33            return 0;
34        }
35        for(i=1;;i++) {
36            scanf("%d%d",&a[i].v,&a[i].l);
37            if(!a[i].v&&!a[i].l)
38                break;
39        }
40        a[0].v=a[i].v=-1;
41        a[0].l=a[i].l=width;
42        r[0].v=-1;
43        r[1].l=0;
44        calc();
45        printf("%d\n",width);
46        for(i=1;;i++) {
47            printf("%d %d\n",r[i].v,r[i].l);
48            if(!r[i].v&&!r[i].l)
49                break;
50        }
51    }
52}
53 
54void calc() {
55    int i,counter;
56    int x,y,z,steps;
57    prow=1;
58    set(&p2,0,1);
59    set(&p5,1,1);
60    counter=0;
61    for(i=1;counter<=width;i++)
62        counter+=a[i].l;
63    i--;
64    set(&p8,i,width-counter+a[i].l+1);
65    while(1) {
66        if(a[p5.p].v==-1)
67            break;
68        x=a[p2.p].l-p2.num;
69        y=a[p5.p].l-p5.num;
70        z=a[p8.p].l-p8.num;
71        steps=x>y?y:x;
72        steps=steps>z?z:steps;
73        if(steps<3) {
74            go(spit(),1);
75            continue;
76        }                           //可在此处插入判断边界程序
77        go(spit(),1);
78        go(spit(),steps-1);
79    }
80    rp++;
81    r[rp].v=r[rp].l=0;
82}
83 
84void set(Pointer *target,int p,int num) {
85    target->p=p;
86    target->num=num;
87}
88 
89int spit(){
90    int result=0,i=0,temp,x=a[p5.p].v;
91    bool top=false,bottom=false;
92    if(a[p2.p].v==-1)
93        top=true;
94    if(a[p8.p].v==-1)
95        bottom=true;
96    if(prow!=1) {
97        if(!top)
98            result=(temp=fabs(pre(p2)-x))>result?temp:result;
99        result=(temp=fabs(pre(p5)-x))>result?temp:result;
100        if(!bottom)
101            result=(temp=fabs(pre(p8)-x))>result?temp:result;
102    }
103    if(prow!=width) {
104        if(!top)
105            result=(temp=fabs(next(p2)-x))>result?temp:result;
106        result=(temp=fabs(next(p5)-x))>result?temp:result;
107        if(!bottom)
108            result=(temp=fabs(next(p8)-x))>result?temp:result;
109    }
110    if(!top)
111        result=(temp=fabs(a[p2.p].v-x))>result?temp:result;
112    if(!bottom)
113        result=(temp=fabs(a[p8.p].v-x))>result?temp:result;
114    return result;
115}
116 
117int pre(Pointer p) {
118    if(p.num==1)
119        return(a[p.p-1].v);
120    else
121        return(a[p.p].v);
122}
123 
124int next(Pointer p) {
125    if(p.num==a[p.p].l)
126        return(a[p.p+1].v);
127    else
128        return(a[p.p].v);
129}
130 
131void go(int spit,int steps) {
132    if(r[rp].v==spit)
133        r[rp].l+=steps;
134    else {
135        rp++;
136        r[rp].v=spit;
137        r[rp].l=steps;
138    }
139    gop(&p2,steps);
140    gop(&p5,steps);
141    gop(&p8,steps);
142    prow=(prow+steps-1)%width+1;
143}
144 
145void gop(Pointer *p,int steps) {
146    p->num+=steps;
147    while(p->num>a[p->p].l) {
148        p->num-=a[p->p].l;
149        p->p++;
150    }
151}

[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的时间，不可能超过最长时间，因而无需额外考虑，方便啊！

view source
print?
1#include <cstdio>
2#include <cstring>
3#define MAXNUM 500
4 
5typedef struct card{
6    int time;
7    int l[MAXNUM+1];
8    bool touched,out;
9} Card;
10 
11int n,p,p1=-1,p2;
12float time;
13Card a[MAXNUM+1];
14 
15void dij();
16void between();
17 
18int main() {
19    int c,b,l,m;
20    int i,N=1;
21    Card ini;   //used to initialize
22    memset(ini.l,-1,sizeof(int)*(MAXNUM+1));
23    ini.time=0;
24    ini.touched=false;
25    ini.out=false;
26    scanf("%d%d",&n,&m);
27    while(n!=0) {
28        for(i=1;i<=MAXNUM;i++)
29            a[i]=ini;
30        p1=-1;
31        time=0;
32 
33        for(i=0;i<m;i++) {
34            scanf("%d%d%d",&c,&b,&l);
35            a[c].l[b]=a[b].l[c]=l;
36        }
37        a[1].touched=true;
38        for(i=1;i<=n;i++)
39            dij();
40        between();
41        printf("System #%d\nThe last domino falls after %.1f seconds, ",N,time);
42        if(p1!=-1)
43            printf("between key dominoes %d and %d.\n\n",p1,p2);
44        else
45            printf("at key domino %d.\n\n",p);
46        N++;
47        scanf("%d%d",&n,&m);
48    }
49    return 0;
50}
51 
52void dij() {
53    int i,j,reachtime;
54    p=-1;
55    for(i=1;i<=n;i++) {
56        if(!a[i].touched||a[i].out)
57            continue;
58        if(p==-1||a[p].time>a[i].time)
59            p=i;
60    }
61    for(i=1;i<=n;i++) {
62        if(a[p].l[i]==-1||a[i].out)
63            continue;
64        reachtime=a[p].time+a[p].l[i];
65        if(!a[i].touched||a[i].time>reachtime) {
66            a[i].time=reachtime;
67            a[i].touched=true;
68        }
69    }
70    a[p].out=true;
71    time=a[p].time;
72}
73 
74void between() {
75    int i,j;
76    float t;
77    for(i=1;i<=n;i++)
78        for(j=i;j<=n;j++) {
79            if(a[i].l[j]==-1||(t=(float)(a[i].time+a[j].time+a[i].l[j])/2)<=time)
80                continue;
81            p1=i;
82            p2=j;
83            time=t;
84        }
85}

[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没有触及到

view source
print?
1#include <cstdio>
2 
3 typedef struct unit {
4     int num;
5     int contact[99];
6     int settime[99];
7     bool set;
8     int time;
9 } Unit;
10 
11 typedef struct aa {
12     int start;
13     int time;
14 } Result;
15 
16void calc();
17int search();
18 
19Unit a[101];
20Result x,result;
21int n;
22 
23int main() {
24    int i,j,start;
25    scanf("%d",&n);
26    while(n) {
27        for(i=1;i<=n;i++) {
28            scanf("%d",&a[i].num);
29            for(j=0;j<a[i].num;j++)
30                scanf("%d%d",&a[i].contact[j],&a[i].settime[j]);
31        }
32        result.start=-1;
33        for(start=1;start<=n;start++) {
34            for(i=1;i<=n;i++) {
35                a[i].set=false;
36                a[i].time=-1;
37            }
38            a[start].set=true;
39            a[start].time=0;
40            i=0;
41            while(i<n+1) {
42                calc();
43                for(i=1;i<=n;i++)
44                    if(a[i].set==true)
45                        break;
46            }
47            x.time=search();
48            x.start=start;
49            for(i=1;i<=n;i++)
50                if(a[i].time==-1) {
51                    x.start=-1;
52                    break;
53                }
54            if(x.start==-1)
55                continue;
56            if(x.time<result.time||result.start==-1)
57                result=x;
58        }
59        if(result.start==-1)
60            if(n==0)
61                printf("0 0\n");
62            else
63                printf("disjoint\n");
64        else
65            printf("%d %d\n",result.start,result.time);
66        scanf("%d",&n);
67    }
68    return 0;
69}
70 
71void calc() {
72    int i,j,spreadtime;
73    for(i=1;i<=n;i++)
74        if(a[i].set) {
75            for(j=0;j<a[i].num;j++) {
76                spreadtime=a[i].time+a[i].settime[j];
77                if(a[a[i].contact[j]].time>spreadtime||a[a[i].contact[j]].time==-1) {
78                    a[a[i].contact[j]].time=spreadtime;
79                    a[a[i].contact[j]].set=true;
80                }
81            }
82            a[i].set=false;
83        }
84}
85 
86int search() {
87    int max,i;
88    max=a[1].time;
89    for(i=2;i<=n;i++)
90        if(a[i].time>max)
91            max=a[i].time;
92    return max;
93}

[ACM] POJ1661 解题报告

Speak

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

view source
print?
1#include <cstdio>
2#include <cstdlib>
3typedef struct flat {
4    int l,r,h,lmin,rmin;
5} Flat;
6Flat a[1001];
7int N,MAX;
8 
9void search(int i,int k,bool bLeft);
10int compare(const void *a,const void *b);
11 
12int main() {
13    int i,j,location;
14    int t,X,Y;
15    scanf("%d",&t);
16    while(t--) {
17        scanf("%d%d%d%d",&N,&X,&Y,&MAX);
18        for(i=1;i<=N;i++)
19            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h);
20        qsort(a+1,N,sizeof(a[0]),compare);
21        for(i=1;i<=N+1;i++) {
22            if(a[i].l<=X&&a[i].r>=X||i==N+1) {
23                a[i-1].l=a[i-1].r=X;
24                a[i-1].h=Y;
25                location=i-1;
26                break;
27                }
28        }
29        for(i=N;i>=location;i--) {
30            for(j=i+1;j<=N;j++)
31                if(a[j].h!=a[i].h)
32                    break;
33        search(i,j,true);
34        search(i,j,false);
35        }
36        printf("%d\n",a[location].lmin);
37    }
38    return 0;
39}
40 
41void search(int i,int k,bool bLeft) {
42    int x,*min,gotol,gotor,fall;
43    if(bLeft) {
44        x=a[i].l;
45        min=&a[i].lmin;
46    }
47    else {
48        x=a[i].r;
49        min=&a[i].rmin;
50    }
51    for(;k<=N;k++)
52        if(a[k].l<=x&&a[k].r>=x)
53            break;
54 
55    if(k==N+1)
56        if(a[i].h>MAX)
57            *min=-1;
58        else
59            *min=a[i].h;
60    else {
61        fall=a[i].h-a[k].h;
62        if(fall>MAX)
63            *min=-1;
64        else {
65            gotol=fall+x-a[k].l+a[k].lmin;
66            gotor=fall+a[k].r-x+a[k].rmin;
67            if(a[k].lmin==-1)
68                if(a[k].rmin==-1)
69                    *min=-1;
70                else
71                    *min=gotor;
72            else
73                if(a[k].rmin==-1)
74                    *min=gotol;
75                else
76                    if(gotol<gotor)
77                        *min=gotol;
78                    else
79                        *min=gotor;
80        }
81    }
82}
83 
84int compare(const void *a,const void *b) {
85    return ((Flat *)b)->h-((Flat *)a)->h;
86}