CH Round #57 - Story of the OI Class 凯撒密码

  很有意思的一道题目

  考场上想的是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.
上一篇:自动化集成:Docker容器入门简介


下一篇:Docker容器入门-基本命令的使用