VIJOS1005超长字符串【宋壬初吧】

宋壬初吧关注：25贴子：419

8回复贴，共1页

VIJOS1005超长字符串

221.194.73.*

经过一个下午的努力，我终于将我学习OI三年的一个夙愿完成了。那就是成功AC了一道题：超长字符串
type ar=array[0..1001] of longint;
var i,j,k,n,t:longint;
    a,mid,num,ans:ar;
    start:ar;startpos:longint;           //起始数字及头部在起始数字的位置
    pd,done,wangzilong:boolean;
    c:char;
procedure minus(var mid:ar);             //将数字减一得到高精度数
var g:longint;
begin
    dec(mid[1]);
    for g:=1 to mid[0] do
    begin
        if mid[g]>=0 then break;
        inc(mid[g],10);dec(mid[g+1]);
    end;
    if mid[mid[0]]=0 then dec(mid[0]);
end;
procedure plus(var mid:ar);             //将数字加一得到高精度数
var g:longint;
begin
    inc(mid[1]);
    for g:=1 to mid[0] do
    begin
        if mid[g]<10 then break;
        dec(mid[g],10);inc(mid[g+1]);
    end;
    if mid[mid[0]+1]>0 then inc(mid[0]);
end;
function compare(x,y:ar):longint;
var g:longint;
begin
    for g:=1001 downto 1 do
    begin
        if x[g]>y[g] then exit(1);
        if x[g]<y[g] then exit(-1);
    end;
    exit(0);
end;
procedure gjdminus(var start:ar;mid:ar);
var g:longint;
begin
    for g:=1 to 1000 do
    begin
        start[g]:=start[g]-mid[g];
        if start[g]<0 then
        begin
            inc(start[g],10);
            dec(start[g+1]);
        end;
    end;
end;
procedure cheng(var start:ar;t:longint);
var g:longint;
begin
    for g:=1 to 1000 do start[g]:=start[g]*t;
    for g:=1 to 1000 do

1楼2009-11-04 20:04回复

221.194.73.*

            begin
                for k:=1 to i do num[k]:=a[i+j-k];         //将完整的第一个数赋给num
                num[0]:=i;                                     //记录数字位数

                pd:=true;                                      //初始化标记为可能可行

                if j>1 then                                    //前面有一个只有后缀的数，所以判断
                begin
                    mid:=num;
                    minus(mid);                                //算出前面的减一后的数字
                    for k:=1 to j-1 do if mid[k]<>a[j-k] then  //发现与前面的后缀不符
                    begin
                        pd:=false;break;
                    end;
                    if not pd then continue;                 //不符条件，跳过

3楼2009-11-04 20:04

221.194.73.*

                end else mid:=num;

                t:=j+i;                                        //找后面所有的数字看是否符合
                while t<=n do
                begin
                    plus(num);                                 //将数字加一，看是否和后面的字串匹配
                    for k:=num[0] downto 1 do
                    begin
                        if a[t]<>num[k] then
                        begin
                            pd:=false;break;                   //发现不符，跳出
                        end;
                        inc(t);if t>n then break;
                    end;
                    if t>n then break;                         //已经超过总长而没有发现不符或已发现不符，跳出
                    if not pd then break;

4楼2009-11-04 20:04

221.194.73.*

                end;

                if not pd then continue;
                t:=compare(mid,start);                         //1表示num大，0表示相等，－1表示num小
                if j=1 then k:=1 else k:=mid[0]-j+2;           //计算第一个位置为第一个数字的第几个位置
                if (t=-1)or((t=0)and(k<startpos)) then
                begin
                    startpos:=k;start:=mid;done:=true;
                end;
            end else
        //case 2
            begin
                pd:=true;

                fillchar(num,sizeof(num),0);

                for k:=1 to j-1 do num[k]:=a[j-k];
                num[0]:=j-1;
                plus(num);

                for k:=1 to j-1 do
                begin
                    if k+i>n then break;
                    if num[j-k]<>a[i+k] then

5楼2009-11-04 20:04

221.194.73.*

                    begin
                        pd:=false;break;
                    end;
                end;

                if not pd then continue;

                fillchar(mid,sizeof(mid),0);
                mid[0]:=i;
                for k:=1 to j-1 do mid[k]:=a[j-k];
                for k:=i downto j do mid[i+j-k]:=a[k];

                if num[0]=j then dec(mid[j]);
                for k:=j to mid[0] do
                begin
                    if mid[k]>=0 then break;
                    inc(mid[k],10);dec(mid[k+1]);
                end;
                if mid[mid[0]]=0 then dec(mid[0]);

                t:=compare(mid,start);                         //1表示num大，0表示相等，－1表示num小
                if j=1 then k:=1 else k:=mid[0]-j+2;           //计算第一个位置为第一个数字的第几个位置

6楼2009-11-04 20:04

221.194.73.*

                if (t=-1)or((t=0)and(k<startpos)) then
                begin
                    startpos:=k;start:=mid;done:=true;
                end;
            end;
        end;
    end;
    end;

    for i:=1001 downto 1 do if start[i]>0 then break;
    fillchar(mid,sizeof(mid),0);
    for j:=1 to i-1 do mid[j]:=9;
    gjdminus(start,mid);
    cheng(start,i);
    ans:=start;

    for j:=1001 downto 1 do if ans[j]>0 then break;

    for j:=1 to i-1 do
    begin
        fillchar(mid,sizeof(mid),0);
        mid[j]:=9;
        cheng(mid,j);
        gjdplus(ans,mid);
    end;

    startpos:=i-startpos;

    if startpos>0 then
    begin
        fillchar(mid,sizeof(mid),0);
        mid[1]:=startpos mod 10;
        mid[2]:=(startpos mod 100) div 10;
        mid[3]:=startpos div 100;
        mmminus(ans,mid);
    end;

    for j:=1001 downto 1 do if ans[j]>0 then break;
    for k:=j downto 1 do write(ans[k]);writeln;
end.

7楼2009-11-04 20:04

210.42.140.*

囧,,楼上是错的啊.......大部分是对的..但是还是有的是错的啊````

8楼2009-11-13 19:36

121.21.255.*

举个例子。这个在VJ上过了

9楼2009-11-14 12:03

唉，现在再写是费劲啦

禁言 |10楼2010-08-06 20:03

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

8回复贴，共1页

<返回宋壬初吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴

日	一	二	三	四	五	六

VIJOS1005超长字符串

登录百度账号

扫二维码下载贴吧客户端