使用的题目是： Asia Regional Contest, Tokyo, 2012-11-18
F
裸带拳冰茶几
A
题目给的第二个结论是一个很有用的必要条件，据此可以暴力在勾股数集合中找因子。
值得注意的是，如果勾股数对应有一个数字为0，那么有4种组合情况；如果两个均不为0，那么有8种组合情况。（尽管是一一对应的关系，但是组内元素互换位置的不同情况也是需要考虑的）
C
遇见这种形式的递推必定要往矩阵的方向进行考虑，毕竟归根结底矩阵是一个处理n元变换关系的有力工具。
仔细考察后发现是一个裸的矩阵快速幂。= =
D
给出d，表示一个f(x)是一个d次多项式，之后给出f(0), f(1), f(d + 2)共d + 3项的值。其中保证有且仅有一个的值不是真值，问这d + 3项中哪一项不是真值。
我第一反应是逐差，看作是一个高阶等差数列。但是这样子只能检验出原AP是不是满足确实是一个高阶等差数列（当然不是），不能确定是哪一项出了问题…假了假了。
后来还是回归到了coolwx用的算法，枚举每一项作为假值，检验剩余的值是否可以构成一个正确的函数。这里有一个定性的问题：函数为d次方，共有d + 1个未知数，那么将给出的d + 3个拿出一个作为假值还剩d + 2个，这样子只需要取d + 1个高斯消元解方程就可以得到一个初值，之后要用这个初值对剩下的一个值进行检验，只有这d + 2个值都满足才可以说这是一个成立的函数。因为如果只对d + 1个求解，那么除非行列式为0，都是可以有解的，粗犷的小懒虫就是枚举的那个假值可以在任意位置，这就不对了。
不过因为最后没有设置多组数据的终止条件WA到迷茫之后喜提AC…我倒立洗头了…
I 二分答案 + DP检验
仔细看了很多博客，他们的思路都差不多，但是有些代码写的比较冗长，这一篇比较简洁：bzoj 4692: Beautiful Spacing 二分 但是其中有一些小地方（比如0开头的数组和1开头的数组之间的转化）…我看了着实有一会才懂（不过有一说一，看到了这篇博客35行解法后其余动辄百行的解法直接pass掉不想看了） 这两篇对于状态的转移与条件的判断讲的比较清楚：BZOJ4692 Beautiful Spacing 与 bzoj4692: Beautiful Spacing
我综合考虑了这些博客之后自己尝试写了一下，WA在了一些小地方（严格说起来是对算法还是不够理解），仔细考察了一番之后AC。
AC代码
有几个地方值得说一下：
最重要的地方我觉得是DP的使用，因为这是二分答案的检验过程。我们用bool dp数组记录每一个位置是否可以成为满足条件的末尾单词（所谓满足条件就是在此之前的最长空格不会超过目前二分的答案）。然后我们从1到n顺序考虑每一个位置i成为末尾单词的情况（之所以用1开头的数组是因为这样子可以比较漂亮的构造出前缀和数组以降低时间复杂度），可以成为这个末尾单词所在行的开头单词要满足一定的条件：一个是这一段总共的最短长度要小于等于W，不然放不下；另一个是最大长度要大于等于W，不然一定会有一段空格的长度超过目前的二分答案。那么我们可以据此，设置双指针j、k代表满足上述条件的开头位置[j, k) 。（区间具体怎么表示无所谓，我个人喜欢仿照STL的区间表示方式） 通过一些手段得到了j和k之后，只需要看一下dp[j - 1] - dp[k - 2]之间是否有一个“1”，如果有1的话，这个1所在的位置就是上一行的满足条件的末尾单词下标，那么这个1之后的那个单词一直到单词i就可以构成一个满足条件的新行，也就可以表明目前的i是一个可行解，更新dp[i]。从1到n-1都可以这样子直接处理，但是在第n个单词的时候需要注意，第n个单词作为末尾的时候不一定要 “顶格”，那么只要这一行的最小距离不要爆W就可以，从而我们对于dp[n]的开头区间的右端点k应该直接置为n。第二个地方是j、k的求解。容易想到的是对于每一个i都从0开始搜索一遍j与k，算法总时间复杂度O(N2logN)，爆T。我们仔细看一下我们的区间转移方程关系就会发现，随着i的增加，j与k都是单调增加的。那么其实将j与k放在循环体外面而不是每一次都初始化为0就可以有效降低复杂度了，搜索jk的总时间复杂度就是线性的了。第三个地方是dp数组。在注意点1中我们看到，我们在使用dp数组时也是用的区间值，所以类似于单词的存储，dp数组也维护为前缀和形式即可。题后反思：
涉及到最小化最大值的情况要多往 二分答案 的角度去考虑。对于dp的构建与使用…我实在是不太擅长…基本上CFdiv2的DE题就是个序列dp题（每遇必G…)（这我也不想啊…) 之后打算开一个dp专题，把一些常见的dp办法都做一个深刻的理解，然后再刷一些进阶的dp问题。（比如说VJ上的暑训dp专题的坑还没有补 = =）