test0427

博客 ： https://so.csdn.net/so/search/s.do?q=GDKOI&t=blog&u=alan_cty

T1 染色大战(coloring)

self : 有想过状压， 但是没有想出如何处理得分则继续走的转移， 所以就放弃了这题

std ： 状压

设 dp[sta] 表示 当前图为 sta 的状态， 当前的先手的得分 与 当前的后手的得分之差 的 最优值

由于有得分继续走的转移， 考虑从后往前(即从状态数大的往小的枚举) 枚举， 枚举 i 为 转移后的状态， j 为转移的状态， 那么 to = i | j 即为转移前的状态 (也就是 i 状态 将 j 变为黑色 后得到 to 的状态)， dp 值从 to 转移到 i， 可以按照得分与否分为两种情况：

如果当前这一次转移得分， 那么说明， to 的状态开始走时， 当前i的先手 依旧是 to 的先手， 所以 dp[i] 就可以由 dp[to] + now（其中now 为当前的得分值) 转移来，

如果当前这一次转移不得分， 那么说明， to 的状态开始走时， 当前 i 的先手与后手 在 to 时进行了交换， 设 i 的先手为 x， 后手为 y， 那么 to 时相反， dp[to] 存的是 va[x] - va[y]， （设 va 为得分值）， 所以 dp[i] = -dp[to] （当前没有得分）

exp : 对于顺序 枚举转移处理比较麻烦的dp, 可以考虑 逆序枚举转移， 比如这种 前后状态的转移关系不唯一， 但是可以通过转移的状态唯一确定 前后状态的关系， 虽然正序也可以转移， 但是应该要多开一维记录到当前这一步的转移是否得分， 那转移方程又会复杂一些

T2 QT 与 泰剧

self : 数位dp 写挂了……

exp : 数位dp里对于等于上界的情况， 需要是一直都等于上界， 然后对于 不可能再等于上界的情况， 由于已经直接加在 dp 里了， 所以就可以直接 return ； 了

T3 项链

self : 看错题了， 一直在想可以剪断多处的情况， 所以就用了个 LCS O(n^3)地跑， 也不知道怎么还有 20‘

std : 对于一个对称串(环)， 一定是由 两个回文串拼起来的， 这题是环， 所以就可以倍长然后manacher 求出 最长回文串， 考虑 一对 合法的 i, j (i < j)， 则一定要满足 len(i, j) <= n， rt(len(i)) >= lf(len(j)) ， 其中 len(x) / len(x, y)表示 以 x 为对称中心的回文串 / 以 x 、 y 为对称中心的回文串的∪， rt/lf(x) 表示 串 x 的右/左端点， 根据 p[i] 可以转为 一个二维偏序问题， 用线段树维护， 对称中心 在 [l, r] 范围内的 回文串 x 的 右端点的最大值， 然后查询的时候， 到一个全都符合 j - i <=n 的区间内 就查询 维护的值 满足 左右端点条件的 最靠右 的 对称中心， 然后答案就是 j - i ， 由于有倍长 还有 manacher 插入的符号， 处理的时候细节有一点麻烦

T4 小学生数学问题

self : 有推出前半部分的处理方法， 但是后半部分不知道自然数幂和, 也还根本就没有提出这个东西

std : 很多公式的推导， 博客里很清楚， 还在看 拉格朗日插值 求 自然数幂和

自然数幂和 博客： https://zhuanlan.zhihu.com/p/26351880

test0427

原文：https://www.cnblogs.com/-wxyz/p/12790694.html