2015-4-13至2015-4-18

颓废了一个星期，我也不知道为什么。

BZOJ1978: [BeiJing2010]取数游戏 game 记$f_i$表示第$i$个数字选择的时候最多选多少个。可以枚举$a_i$的大于$L$的约数$d$，然后记上一个含有$d$的约数为$last[d]$那么显然$f_i=max(fi,f{last[d]}+1)$。因为如果从一个$j < last[d]$且$d | aj$转移，那么一定也可以选择$a{last[d]}$使得答案更大。每个数字最多有$2\sqrt{n}$个约数，复杂度为$O(n\sqrt{n})$

BZOJ3563: DZY Loves Chinese 首先扔度娘的文言文翻译，接着我看了好久也没有意识到哪里逗比了，后来找到了这个……由于每行数量可以读出，就可以利用$k$知道$lastans$，最后一个没法推就并查集暴力。

BZOJ3569: DZY Loves Chinese II 求出dfs树，去掉一些边不连通，那么去掉的边中一定有一条树边且覆盖这条边的非树边全部被去掉。可以记录每条树边有多少条非树边覆盖，然后再枚举其他边要去掉的边看是否覆盖。判断一条边是否覆盖另一条边，可以断判断覆盖边的端点是否是被覆盖边的儿子和祖先，可以利用dfs是记录的$pre$和$suf$两个时间戳判断。还看到另一种判断方法是高斯消元，感觉比较神，记下了可能以后有用。

BZOJ3561: DZY Loves Math VI 推出来一个奇怪的公式：$\sum{T=1}^{n}\sum{d\mid T}d^{d^{mod-2}}T^{2d}\mu(\frac{T}{d}) \sum{i}^{n/T}\sum{j}^{m/T}i^dj^d$，然后枚举$d$，预处理出$i^d$，然后枚举$d$的倍数$T$。似乎复杂度是$O(nlog^{2}n)$计算$T^{2d}$的log去不掉。卡时过了没有再管。

BZOJ2668: [cqoi2012]交换棋子 建立三层节点…刚才编辑的时候remarkable蹦了，什么都没了…那就YY吧。

BZOJ3683: Falsita 可以先dp预处理出答案。接着发现对于单点修改操作，可以用树链剖分修改父亲：对于主链上的点，每次修改答案变动$(size[u]-size[son[u]])*d$，主链就可以预处理出变动值，每次询问求d的和。树状数组即可。而主链间交接的点直接暴力修改。对于子树修改，对父节点的影响相当与单点$d*size[u]$。对儿子的修改，相当于平均值加上$2*d$，可以在dfs序上用树状数组维护。