【D1T1vigenere密碼】
P1778vigenere密碼 Accepted 標簽：[顯示標簽]16世紀法國外交家Blaise de Vigenère設計了一種多表密碼加密算法——Vigenère密碼。Vigenère密碼的加密解密算法簡單易用，且破譯難度比較高，曾在美國南北戰爭中為南軍所廣泛使用。
在密碼學中，我們稱需要加密的信息為明文，用M表示；稱加密後的信息為密文，用C表示；而密鑰是一種參數，是將明文轉換為密文或將密文轉換為明文的算法中輸入的數據，記為k。 在Vigenère密碼中，密鑰k是一個字母串，k=k1k2…kn。當明文M=m1m2…mn時，得到的密文C=c1c2…cn，其中ci=(mi-'A'+ki-'A')mod26+'A'，運算?的規則如下表所示：
Vigenere加密在操作時需要注意：
1. ?運算忽略參與運算的字母的大小寫，並保持字母在明文M中的大小寫形式；
2. 當明文M的長度大於密鑰k的長度時，將密鑰k重復使用。
輸入共2行。
第一行為一個字符串，表示密鑰k，長度不超過100，其中僅包含大小寫字母。第二行為一個字符串，表示經加密後的密文，長度不超過1000，其中僅包含大小寫字母。
輸出共1行，一個字符串，表示輸入密鑰和密文所對應的明文。
CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm
Wherethereisawillthereisaway
每個測試點1s
對於100%的數據，輸入的密鑰的長度不超過100，輸入的密文的長度不超過1000，且都僅包含英文字母。
Noip2012提高組復賽D
【分析】這難道不是純模擬？不要諷刺我P的代碼啦啦啦~又臭又長。。。
【代碼】
var
k,c:ansistring;
kk:char;
p,i,temp,now,l:longint;
map:array['A'..'Z','A'..'Z'] of char;
pq:longint;
q1,q2,j:char;
begin
readln(k);
k:=upcase(k);
l:=length(k);
readln(c);
now:=1;
for q1:='A' to 'Z' do
begin
map[q1,'A']:=q1;
pq:=ord(q1);
for q2:='B' to 'Z' do
begin
pq:=pq+1;
if pq>90 then pq:=65;
map[q1,q2]:=chr(pq);
end;
end;
for i:=1 to length(c) do
begin
kk:=k[now];
for j:='A' to 'Z' do
if map[j,kk]=upcase(c[i]) then
begin
if c[i] in ['A'..'Z'] then write(j)
else write(chr(ord(j)+32));
end;
inc(now);
if now>l then now:=1;
end;
end.
【D1T2國王游戲】
P1779國王游戲 Accepted 標簽：[顯示標簽]恰逢H國國慶，國王邀請n位大臣來玩一個有獎游戲。首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數。然後，讓這n位大臣排成一排，國王站在隊伍的最前面。排好隊後，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然後向下取整得到的結果。
國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少。注意，國王的位置始終在隊伍的最前面。
第一行包含一個整數n，表示大臣的人數。
第二行包含兩個整數a和b，之間用一個空格隔開，分別表示國王左手和右手上的整數。接下來n行，每行包含兩個整數a和b，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數。
輸出只有一行，包含一個整數，表示重新排列後的隊伍中獲獎賞最多的大臣所獲得的金幣數。
3 1 1 2 3 7 4 4 6
2
每個測試點1s
對於20%的數據，有1≤ n≤ 10，0 < a、b < 8；
對於40%的數據，有1≤ n≤20，0 < a、b < 8；
對於60%的數據，有1≤ n≤100；
對於60%的數據，保證答案不超過10^9；
對於100%的數據，有1 ≤ n ≤1,000，0 < a、b < 10000。
Noip2012提高組復賽Day1T2
【分析】以前好像不會證明，然後看題解的。現在重新做一遍，感覺真是水啊。考慮最後一個大臣，顯然他很可能是金幣最多的人。我們要讓他的金幣盡量的少。之前的大臣左手的數肯定會乘起來，所以我們要使S/A/B盡量的大。（設S是左手所有數的乘積），即讓A*B盡量的大。選完最後一個後，我們把他踢掉，然後再找一個最後的大臣。如此往復，相當於就是對A*B排序。-----當然我的證明不是很嚴謹啦。
【代碼】以前不注重長度的後果。。
ar
ans,c,d,e,f:array[0..10000] of longint;
a,b:array[0..1000] of longint;
ansk,ck,ek,fk,x,i,j,n,t,k:longint;
function da:boolean;
var
i:longint;
begin
if ek>ansk then exit(true);
if ansk>ek then exit(false);
for i:=ansk downto 1 do
if ans[i]>e[i] then exit(false)
else exit(true);
end;
begin
readln(n);
readln(a[0],b[0]);
for i:=1 to n do
readln(a[i],b[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]*b[i]>a[j]*b[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
t:=b[i];
b[i]:=b[j];
b[j]:=t;
end;
ck:=1;
c[ck]:=1;
ansk:=0;
ans[ansk]:=0;
for i:=1 to n do
begin
fk:=0;
while a[i-1]>0 do
begin
inc(fk);
f[fk]:=a[i-1] mod 10;
a[i-1]:=a[i-1] div 10;
end;
for j:=1 to ck do
begin
d[j]:=c[j];
end;
fillchar(c,sizeof(c),0);
for j:=1 to ck do
for k:=1 to fk do
c[j+k-1]:=c[j+k-1]+d[j]*f[k];
for j:=1 to ck+fk-1 do
if c[j]>9 then
begin
c[j+1]:=c[j+1]+c[j] div 10;
c[j]:=c[j] mod 10;
end;
ck:=ck+fk-1;
while c[ck+1]>0 do
begin
inc(ck);
c[ck+1]:=c[ck+1]+c[ck] div 10;
c[ck]:=c[ck] mod 10;
end;
x:=0;
ek:=ck;
for j:=ck downto 1 do
begin
e[j]:=(x*10+c[j]) div b[i];
x:=(x*10+c[j]) mod b[i];
end;
while (e[ek]=0) and (ek>1) do
dec(ek);
if da then
begin
ansk:=ek;
for j:=1 to ansk do
ans[j]:=e[j];
end;
end;
for i:=ansk downto 1 do
write(ans[i]);
end.
【D1T3開車旅行】
P1780開車旅行 Accepted 標簽：[顯示標簽】小A和小B決定利用假期外出旅行，他們將想去的城市從1到N編號，且編號較小的城市在編號較大的城市的西邊，已知各個城市的海拔高度互不相同，記城市i 的海拔高度為Hi，城市i 和城市j 之間的距離d[i,j]恰好是這兩個城市海拔高度之差的絕對值，即d[i,j] = |Hi - Hj|。
旅行過程中，小A和小B輪流開車，第一天小A開車，之後每天輪換一次。他們計劃選擇一個城市S作為起點，一直向東行駛，並且最多行駛X公裡就結束旅行。小A和小B的駕駛風格不同，小B總是沿著前進方向選擇一個最近的城市作為目的地，而小A總是沿著前進方向選擇第二近的城市作為目的地（注意：本題中如果當前城市到兩個城市的距離相同，則認為離海拔低的那個城市更近）。如果其中任何一人無法按照自己的原則選擇目的城市，或者到達目的地會使行駛的總距離超出X公裡，他們就會結束旅行。
在啟程之前，小A想知道兩個問題：
1．對於一個給定的X=X0，從哪一個城市出發，小A開車行駛的路程總數與小B行駛的路程總數的比值最小（如果小B的行駛路程為0，此時的比值可視為無窮大，且兩個無窮大視為相等）。如果從多個城市出發，小A開車行駛的路程總數與小B行駛的路程總數的比值都最小，則輸出海拔最高的那個城市。
2. 對任意給定的X=Xi 和出發城市Si，小A開車行駛的路程總數以及小B行駛的路程總數。
第一行包含一個整數N，表示城市的數目。
第二行有N個整數，每兩個整數之間用一個空格隔開，依次表示城市1到城市N的海拔高度，即H1，H2，……，Hn，且每個Hi 都是不同的。
第三行包含一個整數X0。
第四行為一個整數M，表示給定M組Si和Xi。
接下來的M行，每行包含2個整數Si 和Xi，表示從城市Si 出發，最多行駛Xi 公裡。
輸出共M+1行。
第一行包含一個整數S0，表示對於給定的X0，從編號為S0的城市出發，小A開車行駛
的路程總數與小B行駛的路程總數的比值最小。
接下來的M行，每行包含2個整數，之間用一個空格隔開，依次表示在給定的Si 和Xi 下小A行駛的裡程總數和小B行駛的裡程總數。
4 2 3 1 4 3 4 1 3 2 3 3 3 4 3
1 1 1 2 0 0 0 0 0
10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7
2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0
每個測試點1s
對於30%的數據，有1≤N≤20，1≤M≤20；
對於40%的數據，有1≤N≤100，1≤M≤100；
對於50%的數據，有1≤N≤100，1≤M≤1,000；
對於70%的數據，有1≤N≤1,000，1≤M≤10,000；
對於100%的數據，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，數據保證Hi 互不相同。
Noip2012提高組復賽Day1T3
【分析】話說這題目真TM的拗口。我開始把A和B的操作搞反了233。
首先是拼預處理。如何快速預處理一個點之後第一個和第二個比他大的點。
以前我曾和SKYDEC做過討論的，詳見此。
之後隨便來點倍增就行了。我想法太天真，於是寫了兩端倍增。先倍增預處理出2^j後A和B分別到哪裡（顯然只要一個數組，因為奇偶性決定A還是B），再分別預處理A和B走了多少的距離。
第一問就是O（N）枚舉，找到一個最優的。第二問就直接求解了。
為了避免溢出，各種細節。調的我都快吐血了。
【代碼】
