很有意思的一道题目
考场上想的是HASH成一个整数,把末位asicc码值*1,依次乘*10,得到一个整数,然后利用等差性、唯一性快排Nlogn乱搞的
证明如下:
对于明文abcde
密文 bcdef
有(a-b)*10000+(b-c)*1000+(c-d)*100+(d-f)*10+(e-f)*1=一个常数
这个常数我们可以预处理出来,对于任意的f[a,b],a,b属于小写字母,我们都可以预处理出来其值
好吧就是这个考场上写挂了
预处理出来之后依次排序维护标号然后O(n)一遍过就好,哎傻了
CH Round #57 - Story of the OI Class
不过最后又想了下,还是可以直接HASH嘛,HASH过去之后映射回来就行了。。
const maxn=;
maxm=;
maxlen=; var n,t,i,j:longint;
a,b:array [..maxn] of longint;
f:array [..maxm,..maxm] of longint;
s:string; begin
readln(n);
for i:= to maxm do
for j:= to maxm do
if j>=i then
f[i,j]:=j-i else f[i,j]:=-i+j; //hash求出定值
for i:= to n do
begin
readln(s);
t:=;
for j:= to maxlen- do
t:=t*+f[ord(s[j])-ord('a')+][ord(s[j+])-ord('a')+];
a[t]:=i; b[t]:=ord(s[]); //维护标号
end;
for i:= to n do
begin
readln(s);
t:=;
for j:= to maxlen- do
t:=t*+f[ord(s[j])-ord('a')+][ord(s[j+])-ord('a')+];
writeln(a[t],' ',f[ord(s[])-ord('a')+][ord(b[t])-ord('a')+]);
end;
end.