CH Round #44 - KpmCup#1 NOI2014欢

比赛状况：

   又是被屠了一脸啊QAQ，前三名分别是[wyx528](http://contesthunter.org/user/wyx528)(210) , [huzecong](http://contesthunter.org/user/huzecong)(210) 及 [bill125](http://contesthunter.org/user/bill125)(206)，无限膜拜仰慕~~~

Problem_A Maze

状况：这题似乎是最容易的嗯，总共有5个人AC，分别为：wyx528,huzecong,bill125 ♂,sone,Stil。

算法1（动态规划）：

期望得分：10

这是一个明显的动态规划问题，令dp(x,y)表示从S到(x,y)的路径方案数，那么可以得到动态转移方程

78310a55b319ebc4f6d6fa5c8026cffc1f17164c.jpg.png

状态数总共O(nm)级别，转移O(k)，所以总的复杂度是O(nmk)。

算法2（矩阵快速幂优化算法1）：

期望得分：结合算法1共30

我们发现算法1里面的递推式是线性的，而且存在20%的数据m很小，但是n很大，那么可以使用矩阵快速幂对整一行进行状态转移，复杂度O(m^3 log n)。

算法3（多项式乘法优化算法1）：

期望得分：50

我们发现对于一个dp(x,y)，只会转移到dp(x,z)(z>=y)中去，然后又发现对于固定的(z-y+1)，dp(x,y)前面的系数总是一样的，这样就可以考虑到多项式乘法：

0ff41bd5ad6eddc44ad53b3e3bdbb6fd536633c0.jpg.png

所以我们多项式乘法+快速幂即可，复杂度O(m^2 log n)

算法4（FFT优化算法3）：

期望得分：100

算法3的瓶颈在于O(m^2)的多项式乘法，使用FFT可以优化到O(m log m)，那么就可以在O（mlog m log n）的时间复杂度内解决此题。

Problem_B Code

状况：这题是这次比赛被刷的最惨的一道题了，各种手调+搜索引擎无限秒杀QAQ，总共有8个满分，分别是：wyx528,huzecong,dailinsubjam,luoruixuan,Glaceon08,NKWBTB,zerotrac ♂,BillXu2000

解法：

首先题目保证了所给出的明文密文符合英语语法并且足够长，那么这题目就变得非常好做了。

解法1：

 根据以上条件，我们可以发现在一段足够长的文章里面的字母出现频率是有一定规律的，那么可以把明文和密文里面的字母分别按照出现频率排序，然后一一对应，期望得分：0~20

解法2：

既然有了明文这个字典，我们就可以定义一个估价函数F（S）为S对应下密文的可读性，表示对于S这一个解，密文里面有多少个单词是有意义的（在明文里面出现过），然后用解法1的方法贪心初始解，然后暴力随机调整解，记录最优解作为答案，期望得分：0~60

解法3：

 解法二效率比较低的原因是由于盲目对答案调整，我们可以更好的用模拟退火算法来随机调整解，这样某种程度上可以保证解不会退化，期望得分：0~80

解法4：

算法3的模拟退火由于只有一个解进行搜索，所以容易陷入局部最后解，为了解决这个问题，可以使用遗传算法进行随机调整，先贪心初始解，然后随机暴力调整出一定数量的解作为初始种群，然后按F(S)按概率进行模拟遗传，越优的解有越大的机会将其性状遗传至下一代，然后再按一定概率进行突变的模拟，防止陷入局部最优解，标程就是这个解法，详解附加文件的”code.cpp”，期望得分60~100。

解法5：

前面四个解法都是非人工操作的解法，但是这题是答案提交题，所以事实上可以手调，用前面的解法调出一个较优的解，然后暴力把密文翻译出来，然后根据英语常识手动调整，事实上这个方法可行度反而比上述4个方法更高，期望得分：60~100

解法6（伪）：

事实上文学积累比较好（？）的选手更容易解决此题，可以发现数据中的文章都是文学名著，然后接下来就是考验你文学积累的时间啦~，期望得分：0~100？

Problem_C Escape

状况：尼萌怎么都来写这题呢TAT 总共有1个满分：sone，有得分的却只有4位QAQ。

解法：

解法1：

暴力枚举子串求解，时间复杂度：灰常大，期望得分：10

解法2：

 我们发现有40%的大数据是没有强制在线的，那么可以很方便的用后缀数组+线段树+ST RMQ算法离线求解，结合解法1，复杂度O((n+q) log n)期望得分：50

解法3：

事实上在头添加字符查询前缀和在尾添加字符查询后缀是等价的，那么我们很容易可以想到后缀自动机在线维护，假如一个查询串s匹配到的状态是f(s)，那么我们可以发现所有可以产生出符合条件的子串的状态组成了f(s)在parent-tree上的子树，而且除了f(s)之外的其他该种状态产生的子串均符合条件，考虑这些状态中的一个f（x）产生的不同子串的数目，首先两个本质相同的子串一定在同一个状态中表示，因为他们的匹配到的状态是一样的，然后一个状态f(x)产生的子串只跟他的right（）集合和允许该right（）集合的长度范围（设为(len(parent(f(x))),len(f(x))]）有关，两个本质不同的子串（状态一样）当且仅当长度不同，所以f(x)对答案的贡献就是len(f(x))-len(parent(f(x)))，(len(f(x))表示f(x)这个状态的right()集合维持的最长长度)，然后对于f(s)要分开讨论，因为存在部分子串长度甚至没有达到s的长度，所以这部分的要舍去，因此f（s）的贡献是(len(f(s))-|s|+1)，然后这个就可以很方便的用splay维护dfs序列或者是动态树方法解决，复杂度O((n + q) log n),期望得分：100。

比赛内容整合包：http://pan.baidu.com/s/1c01VvWW