P3523 [POI2011]DYN-Dynamite
Description
Solution
经典树上 (dp)。
首先二分 (mid) 表示最远的距离。
设 (f_{x}) 表示距 (x) 最远的未被覆盖的关键点到 (x) 的距离，(g_x) 表示 (x) 到该子树中的选定点的最小距离。
初值显然：(f_x = -inf)，(g_x = inf)
转移方程：(f_x = max { f_y + 1 })，(g_x = max{ g_y + 1})
但是并不是所有的点都能被选，所以要分类讨论一下：
- (f_x + g_x leq mid)，可以直接覆盖，(f_x = -inf)。
- (f_x = mid)，此时选 (x)，那么 (f_x = -inf)，(g_x = 0)，(ans++)。
- (g_x > mid) 且 (d_x = 1)，这时就要扔给 (fa_x) 处理，所以 (f_x = max{ f_x, 0})
P2324 [SCOI2005]骑士精神
Description
Solution
(IDA*) 板子题，乐观估价函数就是 (5 imes 5) 的目标矩阵和当前 dfs 到的矩阵中不同的点的个数。
爆搜即可。
P3205 [HNOI2010]合唱队
Description
Solution
经典区间 (dp)。
设 (f_{i,j}) 表示选了区间 ([i,j]) 且最后一个人从左边进来的方案数，(g_{i,j}) 表示最后一个人从右边进来的方案数。
转移就很 easy 了：
(f_{i,j} = f_{i + 1, j} imes (a_i < a_{i + 1}) + g_{i + 1, j} imes (a_i < a_{j}))
(g_{i, j} = g_{i, j - 1} imes (a_{j} > a_{j - 1}) + f_{i, j - 1} imes (a_j > a_i))
P2513 [HAOI2009]逆序对数列
Description
Solution
看到名字，本来以为又是树状数组维护什么东西，结果不是……
看了一眼题解发现要 (dp) 一下子，(dp) 就 (dp) 吧。
我们设 (f_{i,j}) 表示 (i) 的全排列中，逆序对数为 (j) 的个数。
我们考虑把 (i) 插入到 (i - 1) 的全排列中，枚举这次插入增加了 (k) 个逆序对。
那么转移方程就是：
朴素的转移是 (O(n^2)) 的，考虑优化。
优化也很简单，发现 (k) 是从 0 开始枚举的，做个前缀和即可。
P2592 [ZJOI2008]生日聚会
Description
Solution
模拟赛上考了原题，还是比较 easy 的。
发现数据范围还是很小的，考虑四维 (dp)。
设 (dp_{i, j, c1, c2}) 表示安排了 (i) 名男生，(j) 名女生，且后缀男生数量减去女生数量最大是 (c1)，最大后缀女生减男生数量是 (c2)。
转移就比较显然了，用刷表法（边界好处理一点）。
在最右边安排一名男生：
安排女生同理。
P4295 [SCOI2003]严格N元树
Description
Solution
高精度板子
还是 (dp)，设 (f_i) 表示深度不超过 (i) 的严格 (n) 元树的个数。
转移的过程相当于再增加一个根，且新建的根节点需要 (n) 个子树。
那么转移方程就是：(f_i = f_{i - 1}\, ^ n + 1) （+1 就是只有自己）
简单吧，但是要用高精度（
P2607 [ZJOI2008]骑士
Description
Solution
基环树上 (dp) 板子。
（但是为什么全机房除了我其他人都做过啊啊啊，果然还是我太菜了 (QwQ)）
这道题给出的骑士之间的厌恶关系会形成基环树（森林），那么我们要在上面跑 (dp)。
以下按一棵基环树来讨论。
我们先找到环，然后选择上面的一个点为根，跑树形 (dp)，然后再换成与它相邻的一个点为根跑一遍树形 (dp)，取个最大值就是答案了（树形 (dp) 最下面再说）。
我们再来考虑基环树森林，其实是一样的。
主函数里枚举一遍所有的点，如果还没遍历过，就重复一次上述操作。
那么树形 (dp) 怎么跑？类似于 没有上司的舞会。
我们设 (f_{x,0/1}) 表示以 (x) 为根（(x) 选 或 不选）的子树中最大战斗力。
转移方程：
P4035 [JSOI2008]球形空间产生器
Description
Solution
高斯消元板子
不过还是要稍稍推一下式子的。
关于 (n) 维空间里两个点之间的距离题目下方的说明/提示里有。
这道题给我们的都是表面上的点，言外之意，到球心距离相等。
假设我们要求的球心坐标：((x_1, x_2, x_3……x_n))
那么有：(sumlimits_{i = 1}^{n}{sumlimits_{j = 1}^n(a_{i,j} - x_j)^2 = C})
但是这是个二次方程，还有个常数怎么办啊？
上下一减就完了，减的过程就不写了（懒得打字了），建议自己手推一下。
下面是化简完的式子：
看着不清新？换元一下：
对这个式子建个增广矩阵，跑个高斯消元就完了。
P2146 [NOI2015] 软件包管理器
Description
Solution
树链剖分板子题，不多说了。
P2375 [NOI2014] 动物园
Description
Solution
(kmp) 好题。但是讲一次忘一次
大概就是不能暴力调 (next) 数组，会被卡。
所以我们不用重置前一次跳到的坐标，每次往后跳一格，判断一下即可。
P4133 [BJOI2012]最多的方案
Description
Solution
记忆化搜索不解释。
记录一个斐波那契数列的前缀和，每次跟当前搜索到的要分解的数(x) 比一下。
如果 (x > sum_{i - 1}) ，当前位就必须选了，否则的话选或不选两种情况都搜一遍。
P1640 [SCOI2010]连续攻击游戏
Description
Solution
二分图匹配好题。
观察到每个物品只能用一次，即每次只用使用一个属性值。
那么我们把武器和属性值连边，从 1 开始枚举并跑匈牙利算法。
如果无法匹配直接break（题意要求），然后输出答案即可。
P1403 [AHOI2005]约数研究
Description
Solution
不能理解为什么是橙题……我怕不是连橙题都不会了……
通过打表发现，一段数的约数个数是一样的，每次让 (i) 等于 (frac{i}{n/i} + 1) 中间的数整体算即可。