| ||||||||||
| 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