首页 > 代码库 > NOI2003 文本编辑器editor

NOI2003 文本编辑器editor

2024-07-15 23:28:37   225人阅读

1507: [NOI2003]Editor

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 1908  Solved: 738
[Submit][Status]

Description

Input

输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中： 为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。 除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定： ? MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。 ? 所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。 ? DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。 ? 输入文件没有错误。 对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。

Output

输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。

Sample Input

15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

Sample Output

.\/.
abcde^_^f.\/.ghijklmno

HINT

 

Source

题解：

我靠。。。

刚开始WA,后来栈溢出，然后TLE，还让不让人活了。。。

代码：

1.递归，中序遍历输出结果

  1 {$inline on}  2 {$M 10000000,0,maxlongint}  3 const maxn=2000000+1000;  4 var s,fa:array[0..maxn] of longint;  5     v:array[0..maxn] of char;  6     c:array[0..maxn,0..1] of longint;  7     i,j,n,m,x,y,z,tot,rt,now,l,r:longint;  8     ch:char;  9     st,st2:ansistring; 10 procedure pushup(x:longint);inline; 11  begin 12   s[x]:=s[c[x,0]]+s[c[x,1]]+1; 13  end; 14 procedure rotate(x:longint;var k:longint);inline; 15  var y,z,l,r:longint; 16  begin 17   y:=fa[x];z:=fa[y]; 18   l:=ord(c[y,1]=x);r:=l xor 1; 19   if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 20   fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 21   c[y,l]:=c[x,r];c[x,r]:=y; 22   pushup(y);pushup(x); 23  end; 24 procedure splay(x:longint;var k:longint);inline; 25  var y,z:longint; 26  begin 27   while x<>k do 28    begin 29     y:=fa[x];z:=fa[y]; 30     if y<>k then 31      if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 32      else rotate(y,k); 33     rotate(x,k); 34    end; 35  end; 36 function find(x,rank:longint):longint;inline; 37  var l,r:longint; 38  begin 39   l:=c[x,0];r:=c[x,1]; 40   if s[l]+1=rank then exit(x) 41   else if s[l]>=rank then exit(find(l,rank)) 42   else exit(find(r,rank-s[l]-1)); 43  end; 44 procedure print(x:longint);inline; 45  begin 46   if x=0 then exit; 47   print(c[x,0]); 48   write(v[x]); 49   print(c[x,1]); 50  end; 51  52 procedure main; 53  begin 54   readln(n); 55   l:=maxn-100+1;r:=maxn-100+2; 56   rt:=l; 57   c[l,1]:=r;fa[r]:=l;s[l]:=2;s[r]:=1; 58   now:=1;tot:=0; 59   for i:=1 to n do 60    begin 61     read(ch); 62     case ch of 63     ‘P‘:begin 64         readln; 65         dec(now); 66         end; 67     ‘N‘:begin 68         readln; 69         inc(now); 70         end; 71     ‘M‘:begin 72         while ch<>‘ ‘ do read(ch);readln(x); 73         now:=x+1; 74         end; 75     ‘I‘:begin 76         while ch<>‘ ‘ do read(ch);readln(m); 77         readln(st);while length(st)<m do begin readln(st2);st:=st+st2;end; 78         for j:=1 to m do begin inc(tot);fa[tot]:=tot-1;v[tot]:=st[j];s[tot]:=m-j+1;c[tot,0]:=0;if j<>m then c[tot,1]:=tot+1 else c[tot,1]:=0;end; 79         x:=find(rt,now);y:=find(rt,now+1); 80         splay(x,rt);splay(y,c[x,1]); 81         c[y,0]:=tot-m+1;fa[tot-m+1]:=y; 82         pushup(y);pushup(x); 83         end; 84     ‘D‘:begin 85         while ch<>‘ ‘ do read(ch);readln(m); 86         x:=find(rt,now);y:=find(rt,now+m+1); 87         splay(x,rt);splay(y,c[x,1]); 88         z:=c[y,0];fa[z]:=0;c[y,0]:=0; 89         pushup(y);pushup(x); 90         end; 91     ‘G‘:begin 92         while ch<>‘ ‘ do read(ch);readln(m); 93         x:=find(rt,now);y:=find(rt,now+m+1); 94         splay(x,rt);splay(y,c[x,1]); 95         print(c[y,0]);writeln; 96         end; 97     end; 98    end; 99  end;100 begin101   assign(input,‘input.txt‘);assign(output,‘output.txt‘);102   reset(input);rewrite(output);103   main;104   close(input);close(output);105 end.
View Code

2.人工栈

  1 {$inline on}  2 {$M 1000000000,0,maxlongint}  3 const maxn=2000000+1000;  4 var s,fa:array[0..maxn] of longint;  5     v:array[0..maxn] of char;  6     c:array[0..maxn,0..1] of longint;  7     i,j,n,m,x,y,z,tot,rt,now,l,r,top:longint;  8     ch:char;  9     sta:array[0..maxn*3] of record a,b:longint;end; 10     st,st2:ansistring; 11     function min(x,y:longint):longint;inline; 12      begin 13       if x<y then exit(x) else exit(y); 14      end; 15 procedure pushup(x:longint);inline; 16  begin 17   s[x]:=s[c[x,0]]+s[c[x,1]]+1; 18  end; 19 procedure rotate(x:longint;var k:longint);inline; 20  var y,z,l,r:longint; 21  begin 22   y:=fa[x];z:=fa[y]; 23   l:=ord(c[y,1]=x);r:=l xor 1; 24   if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 25   fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 26   c[y,l]:=c[x,r];c[x,r]:=y; 27   pushup(y);pushup(x); 28  end; 29 procedure splay(x:longint;var k:longint);inline; 30  var y,z:longint; 31  begin 32   while x<>k do 33    begin 34     y:=fa[x];z:=fa[y]; 35     if y<>k then 36      if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 37      else rotate(y,k); 38     rotate(x,k); 39    end; 40  end; 41 procedure print(x:longint); 42  var i,j:longint; 43  begin 44   top:=1;sta[top].a:=x;sta[top].b:=1; 45   while top>0 do 46     begin 47      i:=sta[top].a;j:=sta[top].b;dec(top); 48      if j=2 then write(v[i]) 49      else 50        begin 51          if c[i,1]>0 then 52            begin 53              inc(top);sta[top].a:=c[i,1];sta[top].b:=1; 54            end; 55          inc(top);sta[top].a:=i;sta[top].b:=2; 56          if c[i,0]>0 then 57            begin 58              inc(top);sta[top].a:=c[i,0];sta[top].b:=1; 59            end; 60        end; 61     end; 62  end; 63  64 function find(x,rank:longint):longint;inline; 65  var l,r:longint; 66  begin 67   l:=c[x,0];r:=c[x,1]; 68   if s[l]+1=rank then exit(x) 69   else if s[l]>=rank then exit(find(l,rank)) 70   else exit(find(r,rank-s[l]-1)); 71  end; 72 procedure main; 73  begin 74   readln(n); 75   l:=maxn-100+1;r:=maxn-100+2; 76   rt:=l; 77   c[l,1]:=r;fa[r]:=l;s[l]:=2;s[r]:=1; 78   now:=1;tot:=0; 79   for i:=1 to n do 80    begin 81     read(ch); 82     case ch of 83     ‘P‘:begin 84         readln; 85         dec(now); 86         end; 87     ‘N‘:begin 88         readln; 89         inc(now); 90         end; 91     ‘M‘:begin 92         while ch<>‘ ‘ do read(ch);readln(x); 93         now:=x+1; 94         end; 95     ‘I‘:begin 96         while ch<>‘ ‘ do read(ch);readln(m); 97         readln(st);while length(st)<m do begin readln(st2);st:=st+st2;end; 98         for j:=1 to m do begin inc(tot);fa[tot]:=tot-1;v[tot]:=st[j];s[tot]:=m-j+1;c[tot,0]:=0;if j<>m then c[tot,1]:=tot+1 else c[tot,1]:=0;end; 99         x:=find(rt,now);y:=find(rt,now+1);100         splay(x,rt);splay(y,c[x,1]);101         c[y,0]:=tot-m+1;fa[tot-m+1]:=y;102         pushup(y);pushup(x);103         end;104     ‘D‘:begin105         while ch<>‘ ‘ do read(ch);readln(m);106         x:=find(rt,now);y:=find(rt,min(tot+2,now+m+1));107         splay(x,rt);splay(y,c[x,1]);108         z:=c[y,0];fa[z]:=0;c[y,0]:=0;109         pushup(y);pushup(x);110         end;111     ‘G‘:begin112         while ch<>‘ ‘ do read(ch);readln(m);113         x:=find(rt,now);y:=find(rt,min(tot+2,now+m+1));114         splay(x,rt);splay(y,c[x,1]);115         print(c[y,0]);writeln;116         end;117     end;118    end;119  end;120 begin121   assign(input,‘input.txt‘);assign(output,‘output.txt‘);122   reset(input);rewrite(output);123   main;124   close(input);close(output);125 end.
View Code

 


联系
我们