Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC了,顺带说一句,这个题目有漏洞可钻如果周期大于10000,那么只会出现一行像素,恩哼。 PS: 不完全AC代码 (if(cycle>10000)是亮点) #include <stdio.h> #include <math.h> #include <string.h> #define INTLENGTH 100000 #define INTLENGTH1 100000 #define max(x,y) (x>y?x:y) #define max3(x,y,z) ((x>y?x:y)>z?(x>y?x:y):z) int cycle = 0; int numb= 0; int times=0; int repeattime = 0; int number =-1; int zero = 0;//就是个0 int *change;//交换Top与bottom int T[INTLENGTH1]={0}; int B[INTLENGTH1]= {0}; int last[INTLENGTH1]={0}; int mem[INTLENGTH]={0}; int *Bottom = B; int *Top = T; void cout(int *last,int lastrepeat,int *repeattime,int *number) { if(*last == *number) { *repeattime+=lastrepeat; } else { if(*repeattime)//这里可以进一步压缩,只要不是第一次进行就不需要进行判断。 { //不为0 printf("%d %d\n",*number,*repeattime); } *number=*last; *repeattime = lastrepeat; } return; } ; void product(int Top[],int Bottom[] ,int mem[],int last[],int *repeattime,int *number) { int i = 1; last[0] = max(mem[0],mem[3]); last[cycle-1]=max(mem[4*cycle - 4],mem[4*cycle - 7]); while(i < cycle-1) { last[i] = max3(mem[4*i-3],mem[4*i],mem[4*i+3]); i++; }//前期处理 mem[0] = abs(Top[0] - Bottom[0]); mem[1] = abs(Top[1] - Bottom[0]); mem[2] = abs(Bottom[1]-Bottom[0]); last[0]=max3(mem[0],mem[1],last[0]); last[0]=max(mem[2],last[0]); cout(&last[0],1,repeattime,number); i = 1; while(i<cycle-1) { mem[4*i-1] = abs(Top[i-1] - Bottom[i]); mem[4*i] = abs(Top[i] - Bottom[i]); mem[4*i+1] = abs(Top[i+1] - Bottom[i]); mem[4*i+2] = abs(Bottom[i+1] - Bottom[i]); last[0]=max3( mem[4*i] , mem[4*i+1] , mem[4*i+2] ); last[0]=max3(mem[4*i-1] ,last[0] ,mem[4*i-2] ); last[i]=max(last[0],last[i]); cout(&last[i],1,repeattime,number); i++; } mem[4*cycle - 4] = abs(Bottom[cycle-1] - Top[cycle - 1]);//一共4*cycle-3个,所以最后一个数应为-4 mem[4*cycle - 5] = abs(Bottom[cycle-1] - Top[cycle - 2]); last[0]= max3( mem[4*cycle - 4], mem[4*cycle - 5],mem[4*cycle - 6]); last[cycle-1]=max(last[0],last[cycle-1]); cout(&last[cycle-1],1,repeattime,number); return; } void endingproduct(int Top[],int Bottom[] ,int mem[],int last[],int *repeattime,int *number) {//¥存疑,这里的轮转操作需要再看一下,看C语言往里面传的是指针还是数组名 product( Top, Bottom , mem, last,repeattime,number); change = Bottom;//轮转 Bottom = Top; Top =change; mem[2] = abs(Bottom[1]-Bottom[0]); last[0] = max3(mem[0],mem[2],mem[3]); cout(&last[0],1,repeattime,number); int i = 1; while(i<cycle-1) { mem[4*i+2]=abs(Bottom[i+1]-Bottom[i]); last[i]=max3(mem[4*i+3],mem[4*i-3],mem[4*i]); last[i]=max3(last[i],mem[4*i-2],mem[4*i+2]); cout(&last[i],1,repeattime,number); i++; } last[0] = max3(mem[4*cycle-4],mem[4*cycle-6],mem[4*cycle-7]);//最后一位数 cout(&last[0],1,repeattime,number); memset(last,0,INTLENGTH);//其他两项不需要置零,随后的访问会将他覆盖掉 return; } void evaluation(int a[],int begin,int length,int number) { int i = 0; int *b =&a[begin]; while(i<length) { b[i]=number; i++; } return; } void lengthone(int *repeattime,int *number) { int k=1; scanf("%d%d",&numb,×); k=numb; cout(&zero,times-1,repeattime,number); while(times) { k=numb; scanf("%d%d",&numb,×); if(times) { if(k==numb) { cout(&zero,times,repeattime,number); } else { int z=abs(k-numb); cout(&z,2,repeattime,number); cout(&zero,times-2,repeattime,number); }} } printf("%d %d\n",*number,*repeattime+1); printf("%d %d\n",0,0); return; } int main(void)//万一cycle=10000怎么办? 还没有加上cycle = 1和=2的处理 { scanf("%d",&cycle); while(cycle) { printf("%d\n",cycle); if(cycle==1) { lengthone(&repeattime,&number); } else { if(cycle>10000) { lengthone(&repeattime,&number); } else { int sumtimes = 0;//总计 scanf("%d%d",&numb,×); sumtimes+=times; if(sumtimes<=cycle) { evaluation(Bottom,0,times,numb); } while(sumtimes<cycle) { scanf("%d%d",&numb,×); sumtimes+=times; if(sumtimes<=cycle) { sumtimes-=times; evaluation(Bottom,sumtimes,times,numb);//这里有问题,测试数据7 85 5 78 2 sumtimes+=times; } }//先把底部填满 if(sumtimes==cycle) { scanf("%d%d",&numb,×);//¥新加 } else { sumtimes-=times; evaluation(Bottom,sumtimes,cycle-sumtimes,numb);//这里的sum指的是已经放置了的元素数,所以直接使用sum正好能让元素落到该放的位置 times-=cycle-sumtimes; sumtimes+=cycle-sumtimes; } while(times!=0) { if(times<cycle-sumtimes%cycle) { evaluation(Top,sumtimes%cycle,times,numb); sumtimes+=times; } else { if(times-(cycle-sumtimes%cycle)<3*cycle) { evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle;//如果这个在后面那sumtimes一变就错了 sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number);//至多重复4次,直接复制粘贴了事 change = Bottom;//轮转 Bottom = Top; Top =change; //////////////////////////////////////////////////复制部分 if(times<cycle-sumtimes%cycle)//第一遍 { evaluation(Top,sumtimes%cycle,times,numb); sumtimes+=times; } else { evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle; sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number); change = Bottom;//轮转 Bottom = Top; Top =change; if(times<cycle-sumtimes%cycle)//第二遍 { evaluation(Top,sumtimes%cycle,times,numb); sumtimes+=times; } else { evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle; sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number); change = Bottom;//轮转 Bottom = Top; Top =change; if(times<cycle-sumtimes%cycle)//第三遍 { evaluation(Top,sumtimes%cycle,times,numb); sumtimes+=times; } else { evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle; sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number); change = Bottom;//轮转 Bottom = Top; Top =change; if(times<cycle-sumtimes%cycle)//第四遍 { evaluation(Top,sumtimes%cycle,times,numb); sumtimes+=times; } else { evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle; sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number); change = Bottom;//轮转 Bottom = Top; Top =change; } } } } /////////////////////////////////////////////////复制部分 } else {//大于3个周期,大不了中间一行0是空的 //先压入一行,使Top与Bottom都变满 evaluation(Top,sumtimes%cycle,cycle-sumtimes%cycle,numb); times-=cycle-sumtimes%cycle; sumtimes+=cycle-sumtimes%cycle; product(Top,Bottom,mem,last,&repeattime,&number); change = Bottom;//轮转 Bottom = Top; Top =change; //再压入一行 evaluation(Top,0,cycle,numb); times-=cycle;//不再对sumtime累加,没有意义 //强行处理,置空Top与Bottom.注,此时Top之上就全都是一样的数了,其差为0,所以,没必要再去考虑与上边的差的绝对值了 endingproduct(Top,Bottom,mem,last,&repeattime,&number); cout(&zero,(times-times%cycle-cycle),&repeattime,&number);//能对常量取指针吗?存疑//不能。改成了个全局变量 times=times%cycle+cycle; evaluation(Bottom,0,cycle,numb); times-=cycle; evaluation(Top,0,times,numb); times=0; sumtimes+=times; } } scanf("%d%d",&numb,×); } //走完流程之后Top应该是空的,所以直接把Bottom的数组复制到Top中再调用endingproduct即可 mem[2] = abs(Bottom[1]-Bottom[0]); last[0] = max3(mem[0],mem[2],mem[3]); cout(&last[0],1,&repeattime,&number); int i = 1; while(i<cycle-1) { mem[4*i+2]=abs(Bottom[i+1]-Bottom[i]); last[i]=max3(mem[4*i+3],mem[4*i-3],mem[4*i]); last[i]=max3(last[i],mem[4*i-2],mem[4*i+2]); cout(&last[i],1,&repeattime,&number); i++; } last[0] = max3(mem[4*cycle-4],mem[4*cycle-6],mem[4*cycle-7]);//最后一位数 cout(&last[0],1,&repeattime,&number); //ending结束 printf("%d %d\n",number,repeattime); printf("%d %d\n",0,0); }} scanf("%d",&cycle); //复位 memset(B,0,INTLENGTH1); memset(T,0,INTLENGTH1); memset(last,0,INTLENGTH1); memset(mem,0,INTLENGTH); Bottom=B; Top =T; repeattime=0; number = -1; numb =0; times =0; } printf("%d",0); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator