首页 > 代码库 > CH Round #57 - Story of the OI Class 凯撒密码
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=600001; maxm=26; maxlen=5;var n,t,i,j:longint; a,b:array [0..maxn] of longint; f:array [0..maxm,0..maxm] of longint; s:string;begin readln(n); for i:=1 to maxm do for j:=1 to maxm do if j>=i then f[i,j]:=j-i else f[i,j]:=26-i+j; //hash求出定值 for i:=1 to n do begin readln(s); t:=0; for j:=1 to maxlen-1 do t:=t*26+f[ord(s[j])-ord(‘a‘)+1][ord(s[j+1])-ord(‘a‘)+1]; a[t]:=i; b[t]:=ord(s[1]); //维护标号 end; for i:=1 to n do begin readln(s); t:=0; for j:=1 to maxlen-1 do t:=t*26+f[ord(s[j])-ord(‘a‘)+1][ord(s[j+1])-ord(‘a‘)+1]; writeln(a[t],‘ ‘,f[ord(s[1])-ord(‘a‘)+1][ord(b[t])-ord(‘a‘)+1]); end;end.
CH Round #57 - Story of the OI Class 凯撒密码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。