信息学-解题报告

第二十二届信息学竞赛（NOI2005）试题解Sequence（Day1,Problem数请写一个程序，要求一个数列，支持以下6种操作（请注意，格式栏中的下划线‘_’表示实际输入文件中的空格）操作1.在当前数列的第posi个数字后个数字：c1c2,…,ctot；若在数列首插posi02.positot3.posi续tot个数字修改为4.posi5.positot6.1NM，N表示初始时数列中数的个数，M2NMGET-SUMMAX-SUM操作，向输出文件依次打印结92-6351-5-36GET-SUM54INSERT83-572DELETE12MAKE-SAME33REVERSE3GET-SUM54-1初始时，拥有数 GET-SUM5454个数字之和，1+(-5)+(-3)+6=-1： 5 63+5+1+(-5)+(-3)+6+3=10： -6 执行操作INSERT83-572，即在数列中第8个数字后-572，如下所示 6- 2DELETE12112 MAKE-SAME33233个数字，即下图中的灰色部分，修改为2：2-6 1-6722-6 2-672REVERSE3636 -6 6- 222-5-366-3-5222 -6 - 2- GET-SUM54MAX-SUM110GET-SUM5 GET-SUM操作的答案，60%的分数；MAX-SUM40%GET-SUMMAX-SUM100%位置上打印结果，即必须为另一种操作留下对应的行，否则不保证可以正确评分。150%30000100%500000100%的数据中，任何时刻数列中任何一个数字均在[-1000,1000]20MBytes。的NOI（信息学竞赛）中都有一道数据结构试题，不妨回2001NOI中的同类型试题：NOI2001食物链NOI2002NOI2003文本编辑器NOI2004郁闷的出纳员线段树/，统这样一道数据结构的题目放在了第一天的第一题，意在选手，I2003editrene链式数组本就不容易实现——需要较强的编程基本功因此又在题目中标50%法得到大部分的分，从而大大降低了题目的难度。在试题中已经清楚的标明了本题的测试数据规模及大小测试数据所占50%1802数组模拟+1003400（但不复杂4400行（较复杂5400行（较复杂下面就对这些方法做较为详细的介绍数组模a，这样在一段数的时候可以很容易定位第posi个数字，然后将以后的数字都向后移tot个位置，并在空出的位置中填入待的文本。，tot个位置，并覆盖以前的数字就可以了。MAKE-SAMEREVERSE操作：这些都是顺序存MAX-SUM询问呢？fii个imax{fiLenfif1=fi=max{ai,ai+fi-这样可以在O(Len)的时间内算出所有的fi，选取其中一个最大的输出就O(Len)O(M*Len)。这样的时间效率对付前67链式数入或删除一个数则需要()的时间；而链表好相反，如果确定了要或的时间。虑如何和删除：设最大可能的数列长度为Len，则设最大段长SegLen=Len，那 妨开 )个数组“段用一个单向的链表将这些数组串连起来，这样一个数据结构来信息而要的数列就是按链表的顺序将所有的数组在这个例子中，分了4个段，段间用链表相连，最大段长SegLen=6， 132-15-2436532112-共数组的数目（即链表的长度）则会达到O(N)的数量级。这是不希望看的，如何保证段的数目为 )个呢对于每一段，count对于相邻的两段，countSegLen有了这样两条要求就可以保证段的数目最多也只有 个即 )这个数字在第几个段内，接着在数组中直接定位。由于最多有 )个段因此在链表中查找的时间复杂度为 说时间复杂度还是 )（Split。所谓操作即执行Split(posi)操作后，保证第posi个数位于某一个数组的第一个元素。实现这个操作是很简单的，首先定位第posi个posi显然操作的时间复杂度也是 。在第posi个数之后的位置处一段数字。首先为第(posi+1)个数字执行一次操作，设这道“裂痕”的前一个数组为A，而后一个为B。这样构造一个临时的链式数组C要的一段数字这样在A→B的中间CA→C→B就可以了。这个操作的时间复杂度为 +tot)，tot为文本的数量删除。positotposi(posi+tot)两个数各做一次操作，设裂痕分别在A→B，C→D处，则直接A的后继改为D，并B至C的区间就可以了。这个操作的时间复杂度可 代价可以被平摊入文本中，因此不需要计算由于和删除操作都用到了临时操作Split，因此可能造成一些违背这个数，（ZipSegLen，则将他们合并成为一个新的数组。扫描一次需要 )时间，每合并的时间复杂度为 因此它平摊入操作中就可以了，至此已经初步介绍了链式数组的基本操作。下面还需要加入的操作为MAKE-SAME和REVERSE，以及两个询问操作。为了实现这些操作需要，，做手动修改，则需要太大的时间代价。这里为每一个段加入一个布尔标记sameSameValuesame为真，则表示这一段数已经被修改为SameValue了，以后再查看的时候不需要去看段内数组的内容。，那么若要修改positotposi和区间尾+tot-1)要 )的时间。而中间一部分都是一个个“整段，直接修改段内的和SameValue就可以了，这里的时间复杂度也是 )。所以总的时间复度为 )如果要翻转posi开始的tot个数字则在posi和(posi+tot)处各做一次操为 )求和操作：GET-SUM。sum，表示段内所有数字之sum这个操作的时间复杂度亦为 )，于有反转标记的存在可以使用这样一个技巧：设SideMax[false..true]数组，SideMax[false]从数组的前端向后形成的子串的最大和而SideMax[true]则是SideMax[notreversed]则表是从后向前的最大和。，那么显然构成最大和的子串有两种可能其一是它不任何一段即直接是某一个数组内的最大非空子串和InMax否则若其在至少两段内则可以枚举其最后的那一段。设fi为从顺数第i段向前延伸的非空子串的最大和Blocki+，那么第二种情况的最大值为：

if1=Block1.SideMax[noti>1fi=max{Blocki.SideMax[notreversed],fi-1+这样对每一个数组做一次O(1)的递推，因此整个操作的时间复杂度为 （不实现MAX-SUM操作这样可以得后者60%80~90分。当然，除了链式数组，还可以使用更为高级的数据结构如平衡二叉树，深入的（的邮箱地址见文章首。分选手只是写了简单的数组或链表，他们的得分都比较正常，大部分在预期的50~70分之内。400行去实现较为高级的60分的令人遗憾的结果。可以看出，还有一些选手的编程基本功还不够过数组模拟版本，实际得分：50{Programfor}{$R-,Q-,S-

writtenbyZhouInFile='sequence.in';OutFile='a_array.out';Limit=1000000; =array[1..Limit]of

:N, :proceduremain;i,answerj,posi,c,lasttot,tmp: : :char;readln(N,fori:=1toNdoread(data[i]);readln;fori:=1toMdoread(ch);s:='';whilech<>''dobegins+=ch;ifeolnthench:=''elseread(ch);end;ifs='INSERT'thenreosi,forj:=Ndowntoposi+1dodata[j+tot]:=forj:=1tototdoread(data[posi+j]);readln;N+=tot;ifs='DELETE'thenreadln(posi,forj:=positoN-totdodata[j]:=data[j+tot];N-=tot;ifs='MAKE-SAME'thenreadln(posi,tot,forj:=positoposi+tot-1dodata[j]:=c;ifs='REVERSE'thenreadln(posi,forj:=1tototdiv2dotmp:=data[posi+j-data[posi+j-1]:=data[posi+tot-j];data[posi+tot-j]:=tmp;ifs='GET-SUM'thenreadln(posi,tot);answer:=0;forj:=positoposi+tot-1doanswer+=data[j];ifs='MAX-SUM'thenanswer:=-maxlongint;last:=0;forj:=1toNdolast+=iflast>answerthenanswer:=last;iflast<0thenlast:=0;assign(INPUT,InFile);ReSet(INPUT);assign(OUTPUT,OutFile);ReWrite(OUTPUT);标准程序，链式数组版本，实际得分：100{Programfor}{$R-,Q-,S-

writtenbyZhou ='sequence.in'; ='sequence.out'; =1000;LimitSave= =maxlongintdiv =p, : =object : :array[1..SegLen]oflongint;sum,samevalue,InMax, : :array[false..true]ofreversed,same :boolean;procedureinit;procedurefill;procedurereverseit;procedureSet_Interval(st,ed,c:longint);procedureSet_Same(c:longint);proceduremaintain;functionGet_Sum(st,ed:longint):longint; =open, : :array[1..LimitSave]oflongint;procedureinit;function_new:procedure_dispose(num:longint); =array[1..LimitSave]of

: :Tdata;root, :procedureTSegment.init;next:=0;Len:=0;same:=false;reversed:=false;procedureTSegment.fill; :ifnotsamethenfori:=1toLendodata[i]:=samevalue;same:=false;procedureTSegment.reverseit;i,tmp :longint;ifnotreversedthenexit;ifnotsamethenfori:=1toLendiv2dotmp:=data[i];data[i]:=data[Len-i+1];data[Len-i+1]:=tmp;tmp:=sidemax[false];sidemax[false]:=sidemax[true];sidemax[true]:=tmp;reversed:=false;procedureTSegment.Set_Interval(st,ed,c:longint); :reverseit;fori:=sttoeddodata[i]:=c;procedureTSegment.Set_Same(c:longint);same:=true;samevalue:=c;procedureTSegment.maintain;i,subsum:longint;ifsamethenifsamevalue<0thenInMax:=samevalueelseInMax:=samevalue*Len;sum:=samevalue*Len;sideMax[false]:=InMax;sideMax[true]:=InMax;

sum:=0;subsum:=0;InMax:=data[1];fori:=1toLendosubsum+=data[i];sum+=ifsubsum>InMaxthenInMax:=subsum;ifsubsum<0thensubsum:=0;sideMax[false]:=data[1];subsum:=0;fori:=1toLendosubsum+=ifsubsum>sideMax[false]thensideMax[false]:=subsum;sideMax[true]:=data[Len];subsum:=0;fori:=Lendownto1dosubsum+=ifsubsum>sideMax[true]thensideMax[true]:=subsum;functionTSegment.Get_Sum(st,ed:longint):longint;tmp,i :longint;ifthenexit(samevalue*(ed-st+1))elsebeginifreversedbegintmp:=Len-st+1;st:=Len-ed+1;ed:=tmp;end;tmp:=0;fori:=sttoeddotmp+=data[i];procedureTmem.init; :open:=1;closed:=fori:=1toLimitSavedofree[i]:=i;functionTmem._new:longint;ifopen=closedbeginassign(OUTPUT,'');ReWrite(OUTPUT); n('ERROR');Halt;_new:=free[open];open+=1;ifopen>LimitSavethenopen:=1;procedureTmem._dispose(num:longint);closed+=1;ifclosed>LimitSavethenclosed:=1;free[closed]:=num;procedureinit;i,p,N:longint;readln(N,mem.init;root:=mem._new;data[root].Len:=SegLen;p:=root;fori:=1toNdoifdata[p].Len=SegLenthenbegindata[p].next:=mem._new;data[p].maintain;p:=data[p].next;data[p].init;data[p].Len+=1;read(data[p].data[data[p].Len]);procedureFind(posi:longint;varp:Tcursor);posi+=SegLen;p.p:=root;whileposi>data[p.p].Lenposi-=p.p:=data[p.p].next;p.exec:=posi;procedureSplit(posi:longint;varp:longint); i,tmp :longint;Find(posi,ifcursor.exec<>dursor.p].Lenthenbeginp:=mem._new;data[p].init;data[p].next:=dursor.p].next;dursor.p].next:=p;ddfori:=cursor.exec+1todursor.p].Lendodata[p].Len+=data[p].data[data[p].Len]:=dursor.p].data[i];dursor.p].Len:=cursor.exec;p:=cursor.p;data[p].maintain;data[data[p].next].maintain;

elsebeginp:=cursor.p;data[p].reverseit;data[p].fill;procedureZip;i, : :boolean;i:=root;last:=false;whiledata[i].next<>0doifdata[i].Len+data[data[i].next].Len<=SegLenthenbeginifnotlastthenbegindata[i].fill;data[i].reverseit;end;data[data[i].next].fill;data[data[i].next].reverseit;forj:=1todata[data[i].next].Lendodata[i].Len+=data[i].data[data[i].Len]:=data[data[i].next].data[j];j:=data[i].next;data[i].next:=data[j].next;mem._dispose(j);last:=true;elsebeginiflasttheni:=data[i].next;last:=false;iflastthendata[i].maintain;procedureInsert_Block;i,posi,tot,p,tp

:reosi,tot);Split(posi,p);whiletot>0doifdata[p].Len=SegLenthentp:=mem._new;data[tp].init;data[tp].next:=data[p].next;data[p].next:=tp;p:=tp;data[p].Len+=1;read(data[p].data[data[p].Len]);tot-=1;procedureDelete_Block;i,posi,totst,ed,t:longint;readln(posi,tot);posi-=1;Split(posi,st);Split(posi+tot,ed);t:=data[st].next;data[st].next:=data[t].next;untilt=ed;procedureMake_Same;posi,ctot,t :longint;st, :readln(posi,tot,c);posi-=1;Find(posi,st);Find(posi+tot,ed);ifst.p=ed.pthendata[st.p].Set_Interval(st.exec+1,ed.exec,c)elsebegindata[st.p].Set_Interval(st.exec+1,data[st.p].Len,c);data[ed.p].Set_Interval(1,ed.exec,c);t:=whiledata[t].next<>ed.pdot:=data[t].next;procedureReverse_Block;sum,i,posi,tot,st,ed,t: :array[1..LimitSave]oflongint;readln(posi,tot);posi-=1;Split(posi,st);Split(posi+tot,ed);t:=data[st].next;data[st].next:=ed;sum:=1;list[1]:=t;whilet<>edbegint:=data[t].next;sum+=1;list[sum]:=t