2016/04/30 18:55 twd2：要比赛辣~
2016/04/30 22:01 比赛已经全部结束，稍后将可以看到成绩。

以下部分为题解（汇总版），大家也可以浏览每一题的题解栏。
××××××××××××××××××××××××××××××××××××××
××××××××××××××××××题目分析×××××××××××××××
×××××××××××××××××××AHdoc×××××××××××××××
第一题，游戏
　　为了找出t和m的最大差，我们需要先找出所有可能的m，也就是要算出来有哪些数字可以通过在n个数字中挑选k个来得到。这一个简化版的01背包问题，记F[i][j][x]表示前i个数字中选出j个来，是否可以组成数字x。这样做时间复杂度是O(nkMAXB)的，可以通过85%的数据。
　　又可以发现F[i][j][x]全都是boolean型的，考虑把多个F[i][j][x]在最后一维进行压缩，例如我们可以用一个64位整数来表示64个boolean值。01背包的所有转移都可以用位运算来实现。这便可以通过100%的数据。

第二题，自行车比赛
　　对于第i位选手来说，如果想要夺冠，最好的情况一定是他在下一场夺冠，且其余人按照原有排名的逆序从依次为第二名到第n名。如果先对所有人排序，这样做的时间复杂度是O(n^2)的，可以得到60分。
　　再考虑上述过程，可以发现对于从小到大排序后第i位选手和第i+1位选手来说，最优方案下其余人下一场的得分都是一样的，所以只需要顺序处理好两邻选手的情况即可。

第三题，迷宫
　　把平面上每一个区域看作一个结点，最外层没有边界的区域也看作一个结点。如果一个区域刚好被另外一个区域直接包含，则连边。构成的图上做最短路径即可以得到40~60的分数。
　　又发现，上述得到的图是树结构的，在树上预处理好任意两点的最近公共祖先，之后的询问可以线形完成，这便可以得到满分。

第四题，黑白序列
　　一个显而易见的动态规划方程用F[i]记录前i位可以得到的不同黑白序列的个数。转移需要考虑所有的j<i，并尝试使j+1到i是一个独立的黑白序列段。总时间复杂度是O(n^2)的，这便可以得到65分。
　　考虑上述转移中涉及到的j，可以发现需要被考察的j往往是连续的偶数，而其中的断点总会使得对最后一个黑白序列段的长度要求有了两倍以上的限制。所以转移中j的断点只有O(logn)个。用链表维护需要转移的连续若干个j，总的时间复杂度为O(nlogn)，便可以得到满分。
××××××××××××××××××××××××××××××××××××××