提高组的解题报告, 发的好像有点晚了. 

第一题, 机器翻译(translate): 利用循环队列维护.

第二题, 乌龟棋(tortoise):
动态规划. 设 f[n][m1][m2][m3][m4] 为到达 n 处, 卡片的使用情况为 (m1, m2, m3, m4) 的最大得分. 这个算法的复杂度是 O(N*40^4), 可以进一步优化. 
易得出, n = m1 + m2 * 2 + m3 * 3 + m4 * 4, 五维的优化成四维, 复杂度降为 O(40^4).

第三题, 关押罪犯(prison):
做法 1:
设当前的答案是 Ans. 则对于每个罪犯 i, 所有和罪犯 i 有矛盾的罪犯 j, 如果矛盾值 w > Ans, 则他们显然不能放在同一个集合里. 于是我们可以连无向边 (i, j') 和 (i', j) (假若是有向的就是 2-SAT 问题). 求这个图的连通块, 对于每对 (i, i'), 都不在同一个连通块里, 则 Ans 是一个可行答案. 然后二分答案就可以了. O(logN(N+M)) 的时间复杂度.  
做法 2:
注意到做法 1 求连通块会反复建图, 做了很多的无用功, 我们可以尝试将边排序后, 从大到小依次枚举 Ans. 利用并查集维护连通性, 一直到发现存在 (i, i') 处于同一个连通块为止.
从时间效率上来看, 做法 2 是比较优的.

第四题, 引水入城(flow):
从所有的 (1, i) 的格子开始宽搜, 记录每个格子所能到达 (n, i) 的格子. 可以证明, 如果存在一个解, 那么所有第一行的格子能到达的最后一行的格子都是连续的, 而且能覆盖到所有最后一行的格子.

对于这种连续区间求最小覆盖的问题, 有一个很漂亮的贪心算法可以做到 O(NlogN+N).

参考代码: https://foreverbelloisolutions.googlecode.com/svn/Other/NOIp/2010