noip 2012 提高组 解题报告.docxVIP

noip 2012 提高组 解题报告 Vigenère密码模拟注意大小写vari,l,t:longint;a:Array[0..1000] of longint;s:string;ch:char;begin readln(s); l:=length(s); for i:=1 to l do if ord(s[i])=97 then a[i]:=ord(s[i])-96 else a[i]:=ord(s[i])-64; a[0]:=a[l]; read(ch); i:=1; t:=ord(ch); while (t64)and(t124) do begin if t97 then begin t:=t-64; t:=(t-a[i mod l]+27) mod 26; if t=0 then t:=26; t:=t+64; write(chr(t)); end else begin t:=t-96; t:=(t-a[i mod l]+27) mod 26; if t=0 then t:=26; t:=t+96; write(chr(t)); end; read(ch); inc(i); t:=ord(ch); end;end.国王游戏快排+高精乘+高精除可以证明最优序列是按照左手上的数*右手上的数递增排序，所以按照左手上的数*右手上的数递增排序前n-1个左手上的数累乘（高精乘）除以n右手上的数（高精除）vari,n,l:longint;a,b,c:array[0..10000] of longint;g,g2:array[0..100000] of longint;procedure gj1;varj:longint;begin for j:=1 to l do g[j]:=g[j]*b[i]; for j:=1 to l do begin g[j+1]:=g[j+1]+g[j] div 10; g[j]:=g[j] mod 10; end; inc(l); while g[l]9 do begin g[l+1]:=g[l+1]+g[l] div 10; g[l]:=g[l] mod 10; inc(l); end; if g[l]=0 then dec(l);end;procedure gj2;varj:longint;begin for j:=l downto 1 do begin g[j-1]:=g[j-1]+(g[j] mod c[n])*10; g[j]:=g[j] div c[n]; end; while g[l]=0 do dec(l);end;procedure sort(l,r:longint);vari,j,x,y:longint;begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]x do inc(i); while xa[j] do dec(j); if not (ij) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=c[i]; c[i]:=c[j]; c[j]:=y; inc(i); dec(j); end; until (ij); if lj then sort(l,j); if ir then sort(i,r);end;begin readln(n); readln(b[0],c[0]); for i:=1 to n do begin read(b[i],c[i]); a[i]:=b[i]*c[i]; end; sort(1,n); l:=1; g[1]:=b[0]; for i:=1 to n-1 do gj1; gj2; for i:=l downto 1 do write(g[i]); writeln;end.开车旅行链表+倍增按城市高度递增顺序排序，放到链表中从第一个城市起，找离它最近和次近的城市，记录下来填每个点向前走2^0步（压缩后的一步，即A走一次B走一次）；倍增：处理处每个点向前走2^j步能到的城市和到这个城市A,B需要走的距离方程：f[I,j]=f[f[I,j-1],j-1]]; a[I,j]=a[I,j-1]+a[f[I,j-1],j-1]; b[I,j]=b[I,j-1]+b[f[I,j-1],j-1]依据s,x判断能走到哪个城市及A,B走过距离program day13;label 1;typepoint=^rec;rec=record da:longint; la,ne:point;end;vari,n,m,t,s,top,j,k,ans,dk,lj:longint;h,a,mi,mmi,b:array[0..1000