P1：注意到单词数量很少，可以分别对每个单词进行一次KMP匹配，对每个单词的每次开始位置打上标记。每次询问L..R相当于求L..（R-len）中标记的个数，直接用前缀和维护即可。

P2：原谅我的失误，目前还没有想到一个正解（原来的想法有纰漏）。

先谈一下原来的想法：首先可以证明对于每一格密码，要么只向上转，要么只向下转。（不然，可以简单地把这段重复操作的区间去掉，不影响结果）于是可以以此作为状态，用f[i][0..1]表示第i格向上/向下转所需的最小代价，每格要么跟前一格一起转（此时可以用类似去年积木大赛的方法转移），要么反着转（直接计算）。

但是比赛结束后发现有选手采取和我类似的方法却只有45分。对拍以后发现，由于我在赋初值直接用的else，造成本来“相等”，应该赋0的情况被赋成了10——但这样反而得到了更小的答案。对拍出错的这组数据参考：

7 8 8 9 8 2 7 7

4 2 4 0 2 1 2

答案是11而不是12，是通过把第五格向下转动整整10格来实现的！也就是说，即使一个点的方向确定，它转动的格数也无法确定。进一步分析发现，每一个方向都至多有两种可能性（比如说向上转1格与11格（显然不可能转21格！）），但尽管如此，在状态转移时却无法知道当前的状态是从哪一种可能性转移而来的，而我们必须保证它只能以固定的一个状态参与转移（不然，再次转移的时候，可能出现当前最小值是由两个不能同时取得的状态转移而来的情况，还是上面那组数据会跑出错误的答案9）。对于这种情况我并没有太好的解决方法，也希望大家能再想一想。

P3：USACO搬运而来。原题的解法是维护一个前缀和序列，把白牛标为1，斑点牛标为-1，则原题等价于寻找一个最长的、包含偶数个元素的区间使得这段区间的和非负。（因为所有的白牛都可以变成斑点牛，所以只要白牛的数量超过一半就行）枚举左端点，对于一个右端点，如果存在一个在它右边并且前缀和比它小的点，那么这个点一定对答案没有贡献（直接把它换成前一个右端点显然更优）。于是所有可能对答案有贡献的点的前缀和都是单调不减的，使用二分找到这样的点即可。

我还有一个复杂度不详，但也能AC的算法。还是用前缀和维护区间中白牛的数量，枚举左端点l，然后按右端点r从大到小检验，如果当前区间白牛的数量s超过区间内总数的一半则更新答案；否则令r=l+s*2-1继续检验。这样“跳跃着检索”，效果还是不错的。

这是我第一次举办比赛，有许多不足的地方还望大家包涵。