【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行，一个字符串，表示输入密钥和密文所对应的明文。
样例1
样例输入1[复制]
CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm
样例输出1[复制]
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，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
样例1
样例输入1[复制]
3
1 1
2 3
7 4
4 6
样例输出1[复制]
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[c