Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC了,顺带说一句,这个题目有漏洞可钻

Posted by 547320073 at 2013-06-14 00:11:02 on Problem 1009
如果周期大于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,&times);
    k=numb;
    cout(&zero,times-1,repeattime,number);
    while(times)
    {

        k=numb;
        scanf("%d%d",&numb,&times);
        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,&times);
    sumtimes+=times;
    if(sumtimes<=cycle)
    {
evaluation(Bottom,0,times,numb);
    }
    while(sumtimes<cycle)
    {
        scanf("%d%d",&numb,&times);
        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,&times);//¥新加
    }
    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,&times);
    }
    //走完流程之后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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator