做题好慢啊。
2日
P3354 [IOI2005]Riv 河流
树形背包 DP。
设 \(f_{u,f,k},g_{u,f,k}\) 表示 u 为根的子树以 f 为关键点、强制 / 不强制 u 为关键点、使用了 k 个关键点的最小花费。
\[\begin{aligned} f_{u,f,k}&\leftarrow f_{v,f,l}+f{u,f,k-l}\\g_{u,f,k}&\leftarrow f_{v,u,l}+g_{u,f,k-l} \end{aligned}\]
复杂度 \(\mathcal O(n^4)\)。
3日
AcWing277 饼干
简单 DP。
先贪心地让怨气值大的在前，则分配饼干个数单调不增，设 \(f_{i,j}\) 表示前 i 个人分 j 个饼干最优答案。
简化状态，强制让最后一个人只得到 1 个，其他状态 \(f_{i,j}\Leftarrow f_{i,j-i}\)。
接下来只要考虑最后有多少个人同样分到 1 个就行。
复杂度 \(\mathcal O(n^2m)\)。
P6564 [POI2007] 堆积木KLO
CDQ，BIT，LIS 等均可。
\[\begin{aligned} i&>j,\\ a_i&> a_j,\\ a_i-a_j&\le i-j \end{aligned}\]
满足后两个条件时一定满足第一个条件，转化为二维偏序直接上 CDQ。
因为一个 \(>\) 一个 \(\ge\)，所以 \(i-a_i\) 属性要作第一维。
P2175 小Z的游戏分队
每个人向不信任的人连边，形成若干个二分图。
以每个二分图两边人数差为权值，背包 DP 某个答案是否能出现。
4日
P1800 software
二分 + 背包 DP。
明显答案是单调的，考虑怎么判定合法。
在时间限制内，每个人固定了任务一的量，就能确定任务二的量，于是将一个人拆成 m 个物品。
背包 DP 出 n 个人完成任务一时最多能够完成的任务二的量即可。
U139384 异或和
FWT。
设 \(f^i(x)\) 表示选 \(i\) 个数，异或和能否为 \(x\)，容易得到 \(f^1(x)\)，通过 FWT 自卷即可转移。
将选取最多的，转化为删去最少的使得异或和为零（前者）。
设所有数异或和为 \(s\)，异或和能够为 \(s\) 的个数只有 \(\log_2n\) 级别（线性基）。
那么只要处理前 \(\log_2n\) 的 \(f^i(x)\) 即可，每次暴力 FWT 和 iFWT 可以做到 \(\mathcal O(n\log^2n)\)。
丧心病狂的出题人 AzusaCat 竟然卡掉两个 log 的做法！！！
考虑优化 iFWT，因为每次只需要 \(f^i(s)\) 的值，单点的话从 FWT 的原理逆推：
\[\begin{aligned} \hat{F}*S&=\sum*{T\subseteq U}(-1)^{|S\cap T|}F_T \\ F_S&=\frac{1}{2^n}\sum_{T\subseteq U}(-1)^{|S\cap T|}\hat F_T \end{aligned}\]
每次只要 \(\mathcal O(n)\) 即可得到单点的值，总复杂度降至 \(\mathcal O(n\log n)\)。
P3047 [USACO12FEB]Nearby Cows G
换根 DP。
先处理出 \(f_{u,i}\) 表示以 u 为根的子树深度为 i 的点权和，\(\mathcal O(k)\) 转移。此时 1 的 DP 值为答案。
换根，每次将 u 的一个子树 v 贡献减去，分成两个独立的树，再由 u 转移到 v 即可。
换根 DP 的特点是能够快速地将子树分离、改变父子关系后合并
5日
P4161 [SCOI2009]游戏
数论，背包 DP。
容易发现一个排列可以看成几个环，而变换回来的步数是这些环的 \(\operatorname{lcm}\)。
问题转化成：n 拆成若干个数的和，这些数的 \(\operatorname{lcm}\) 的种数。
将 \(\operatorname{lcm}\) 唯一分解，每个质因子的指数为所有数该质因子的最大指数。
那么 DP 每个质数不同质数的情况下的方案数，转化成完全背包。
设 \(f_{i,j}\) 表示到第 i 个质数，将 j 拆开的 \(\operatorname{lcm}\) 种数，则 \(f_{i,j}\leftarrow f_{i-1,j}+f_{i-1,j-p_i^k}\)。
因为无法处理 1，而 1 不影响 \(\operatorname{lcm}\)，所以拆开的数的和不一定为 n，剩下的用 1 填满，最后答案为 \(\sum_{i=0}^n f_{cnt_p,i}\)。
P6280 [USACO20OPEN]Exercise G
和上题一样，只不过是求 \(\operatorname{lcm}\) 的和。
每次 DP 时是一个新的素数，所以直接乘以上一个状态，\(f_{i,j}\leftarrow f_{i-1,j}+f_{i-1,j-p_i^k}\times p_i^k\)。
P4342 [IOI1998]Polygon
区间 DP。
题目唬人，但是容易看出来每次断成链后是个区间 DP，枚举断点后直接做，\(\mathcal O(n^4)\) 可过。
然后就 80 分 qwq。因为有乘法，而每个数可能为负，负负得正。
于是同时维护最大值和最小值。
P4158 [SCOI2009]粉刷匠
简单 DP + 背包 DP。
问题在于如何分配粉刷次数，先对于每一行单独处理，将不同粉刷次数的答案化为物品。
设 \(f_{i,k}\) 表示前 \(i\) 位粉刷 \(k\) 次最多正确个数，\(f_{i,k}\leftarrow f_{j,k-1}+\max\{s_0(j+1,i),s_1(j+1,i)\}\)。
然后对于 \(n\times m\) 个物品进行背包即可。
P1092 虫食算
搜索。
正解好像是高斯消元，不会。
从低位到高位开始搜，当三位中有两个确定时就可以推出第三个。
还有一个剪枝，每确定一列，就扫一遍后面没搜的列，看在进不进位的情况下是否都矛盾。
P3951 小凯的疑惑
数论。
打表，发现 \(a<b\) 时答案是 \((a-1)\times b - a\)。
证明：设无法表示出来的为 x。
\[\begin{aligned} x&\equiv ma\pmod b \quad&(1<m<b)\\ x&=ma+nb\quad&(1<m<b,n<0) \end{aligned}\]
当 x 最大时，\(m=b-1,n=-1\)，证毕。
P5092 [USACO04OPEN]Cube Stacking
并查集。
在 \(x\) 和 \(fa\) 的边之间维护压缩的边数，路径压缩优化，再维护每个并查集的 size。
P2894 [USACO08FEB]Hotel G
线段树。
维护每个区间的最长连续区间和左端开头、右端开头的最长连续区间。
二分最早的 r 使得 \([1,r]\) 的最长连续区间长度大于 x，\(\mathcal O(n\log^2n)\)。
query 时直接左区间优先即可，\(\mathcal O(n\log n)\)。
11日
P7076 动物园
贪心（？），CSP2020 T2。
将所有动物或起来，对于每一位，没有饲料或者有饲料并且已经购买，该位可以选或不选；有饲料且未购买，只能不选。
把每一位的答案乘一下，坑点是开了 unsigned long long 也见祖宗，需要特判 \(2^{64}\) 的情况。
12日
P7077 函数调用
拓扑 DP，CSP2020 T3。
考场上写的线段树暴力，好歹也是个不小的数据结构啊怎么才给 30 分！其实是不错的题。
可以发现单点加值，整体乘值，所有操作形成若干个 DAG，只要求最终序列，于是方向转向图论。
设所有乘法之积为 \(mul\)，每个点初始值的贡献一定是 \(a_i\times mul\)。
接下来考虑单点加和其之后的变化。每个单点加的贡献是后面所有乘法之积。
那么先预处理每个点的及后面乘法的积 \(m_i\)，然后按照操作序列倒着 DP 每个DAG 的贡献次数。
再在 DAG 里倒着 DP，\(f_v\leftarrow f_v + f_u, f_u\leftarrow f_u\times m_v\)，对于单点加的贡献就有 \(f_u\times val_u\)。
17日
P7078 贪吃蛇
博弈论+单调性优化，CSP2020 T4。
见博客题解。
20日
CF455D Serega and Fun
平衡树或者分块。
对于第一个操作可以用一棵 splay 轻松维护，称其为序列树。
因为值域 \(\mathcal O(n)\)，第二个操作考虑每个值维护一棵 splay，节点存其对应的序列树的编号。
每次询问一个区间要求在某一棵 splay 里寻找区间内最靠左和最靠右的点，可以通过在序列树上查 rank 来二分，单次 \(\mathcal O(\log^2n)\)。
S2OJ#41 新斯诺克
归并排序就够了。
可以让所有数减去 m，然后做前缀和，满足 \(j<i, s_j<s_i\) 的一对点构成一个合法区间。
二维偏序，可以做到 \(\mathcal O(n\log n)\)。这个煞笔又写了个比别多个 \(\log\) 的 CDQ 分治。
21日
S2OJ#42 方舟连接
区间 DP + 四边形不等式优化。
把路径看成一棵树，然后发现这是两两相邻子树合并，转化成一个序列就是区间 DP。
\(\mathcal O(n^3)\) 过不去，简单证明一下 DP 为凸，套上经典的四边形不等式优化，降到 \(\mathcal O(n^2)\)。
S2OJ#60 A Simple Math Problem VI
小数据裸完全背包。大数据特殊性质 \(a_i=1\)，组合数问题 见 OI wiki。
22日
P4093 [HEOI2016/TJOI2016]序列
CDQ 分治。
设 \(mi_i=\min\{val_i,w_i\},ma_i=\max\{val_i,w_i\}\)，求 LIS 的时候转移的条件为：
\(\begin{aligned} j&<i\\ val_j&\le mi_i\\ ma_j&\le val_i \end{aligned}\)
CDQ 分治，左右分别按上边对应的属性排序；优先递归处理左区间。复杂度 \(\mathcal O(n\log^2 n)\)。
26日
CF571D Campus
转化成树上问题 + 树状数组上二分技巧。
27日
GYM102331B Bitwise Xor
简单 DP + 01-trie。
2日
P3354 [IOI2005]Riv 河流
树形背包 DP。
设 \(f_{u,f,k},g_{u,f,k}\) 表示 u 为根的子树以 f 为关键点、强制 / 不强制 u 为关键点、使用了 k 个关键点的最小花费。
\[\begin{aligned} f_{u,f,k}&\leftarrow f_{v,f,l}+f{u,f,k-l}\\g_{u,f,k}&\leftarrow f_{v,u,l}+g_{u,f,k-l} \end{aligned}\]
复杂度 \(\mathcal O(n^4)\)。
3日
AcWing277 饼干
简单 DP。
先贪心地让怨气值大的在前，则分配饼干个数单调不增，设 \(f_{i,j}\) 表示前 i 个人分 j 个饼干最优答案。
简化状态，强制让最后一个人只得到 1 个，其他状态 \(f_{i,j}\Leftarrow f_{i,j-i}\)。
接下来只要考虑最后有多少个人同样分到 1 个就行。
复杂度 \(\mathcal O(n^2m)\)。
P6564 [POI2007] 堆积木KLO
CDQ，BIT，LIS 等均可。
\[\begin{aligned} i&>j,\\ a_i&> a_j,\\ a_i-a_j&\le i-j \end{aligned}\]
满足后两个条件时一定满足第一个条件，转化为二维偏序直接上 CDQ。
因为一个 \(>\) 一个 \(\ge\)，所以 \(i-a_i\) 属性要作第一维。
P2175 小Z的游戏分队
每个人向不信任的人连边，形成若干个二分图。
以每个二分图两边人数差为权值，背包 DP 某个答案是否能出现。
4日
P1800 software
二分 + 背包 DP。
明显答案是单调的，考虑怎么判定合法。
在时间限制内，每个人固定了任务一的量，就能确定任务二的量，于是将一个人拆成 m 个物品。
背包 DP 出 n 个人完成任务一时最多能够完成的任务二的量即可。
U139384 异或和
FWT。
设 \(f^i(x)\) 表示选 \(i\) 个数，异或和能否为 \(x\)，容易得到 \(f^1(x)\)，通过 FWT 自卷即可转移。
将选取最多的，转化为删去最少的使得异或和为零（前者）。
设所有数异或和为 \(s\)，异或和能够为 \(s\) 的个数只有 \(\log_2n\) 级别（线性基）。
那么只要处理前 \(\log_2n\) 的 \(f^i(x)\) 即可，每次暴力 FWT 和 iFWT 可以做到 \(\mathcal O(n\log^2n)\)。
丧心病狂的出题人 \(\rm \color{black}{A}\color{red}{zusaCat}\) 竟然卡掉两个 log 的做法！！！
考虑优化 iFWT，因为每次只需要 \(f^i(s)\) 的值，单点的话从 FWT 的原理逆推：
\[\begin{aligned} \hat{F}*S&=\sum*{T\subseteq U}(-1)^{|S\cap T|}F_T \\ F_S&=\frac{1}{2^n}\sum_{T\subseteq U}(-1)^{|S\cap T|}\hat F_T \end{aligned}\]
每次只要 \(\mathcal O(n)\) 即可得到单点的值，总复杂度降至 \(\mathcal O(n\log n)\)。
P3047 [USACO12FEB]Nearby Cows G
换根 DP。
先处理出 \(f_{u,i}\) 表示以 u 为根的子树深度为 i 的点权和，\(\mathcal O(k)\) 转移。此时 1 的 DP 值为答案。
换根，每次将 u 的一个子树 v 贡献减去，分成两个独立的树，再由 u 转移到 v 即可。
换根 DP 的特点是能够快速地将子树分离、改变父子关系后合并
5日
P4161 [SCOI2009]游戏
数论，背包 DP。
容易发现一个排列可以看成几个环，而变换回来的步数是这些环的 \(\operatorname{lcm}\)。
问题转化成：n 拆成若干个数的和，这些数的 \(\operatorname{lcm}\) 的种数。
将 \(\operatorname{lcm}\) 唯一分解，每个质因子的指数为所有数该质因子的最大指数。
那么 DP 每个质数不同质数的情况下的方案数，转化成完全背包。
设 \(f_{i,j}\) 表示到第 i 个质数，将 j 拆开的 \(\operatorname{lcm}\) 种数，则 \(f_{i,j}\leftarrow f_{i-1,j}+f_{i-1,j-p_i^k}\)。
因为无法处理 1，而 1 不影响 \(\operatorname{lcm}\)，所以拆开的数的和不一定为 n，剩下的用 1 填满，最后答案为 \(\sum_{i=0}^n f_{cnt_p,i}\)。
P6280 [USACO20OPEN]Exercise G
和上题一样，只不过是求 \(\operatorname{lcm}\) 的和。
每次 DP 时是一个新的素数，所以直接乘以上一个状态，\(f_{i,j}\leftarrow f_{i-1,j}+f_{i-1,j-p_i^k}\times p_i^k\)。
P4342 [IOI1998]Polygon
区间 DP。
题目唬人，但是容易看出来每次断成链后是个区间 DP，枚举断点后直接做，\(\mathcal O(n^4)\) 可过。
然后就 80 分 qwq。因为有乘法，而每个数可能为负，负负得正。
于是同时维护最大值和最小值。
P4158 [SCOI2009]粉刷匠
简单 DP + 背包 DP。
问题在于如何分配粉刷次数，先对于每一行单独处理，将不同粉刷次数的答案化为物品。
设 \(f_{i,k}\) 表示前 \(i\) 位粉刷 \(k\) 次最多正确个数，\(f_{i,k}\leftarrow f_{j,k-1}+\max\{s_0(j+1,i),s_1(j+1,i)\}\)。
然后对于 \(n\times m\) 个物品进行背包即可。
P1092 虫食算
搜索。
正解好像是高斯消元，不会。
从低位到高位开始搜，当三位中有两个确定时就可以推出第三个。
还有一个剪枝，每确定一列，就扫一遍后面没搜的列，看在进不进位的情况下是否都矛盾。
P3951 小凯的疑惑
数论。
打表，发现 \(a<b\) 时答案是 \((a-1)\times b - a\)。
证明：设无法表示出来的为 x。
\[\begin{aligned} x&\equiv ma\pmod b \quad&(1<m<b)\\ x&=ma+nb\quad&(1<m<b,n<0) \end{aligned}\]
当 x 最大时，\(m=b-1,n=-1\)，证毕。
P5092 [USACO04OPEN]Cube Stacking
并查集。
在 \(x\) 和 \(fa\) 的边之间维护压缩的边数，路径压缩优化，再维护每个并查集的 size。
P2894 [USACO08FEB]Hotel G
线段树。
维护每个区间的最长连续区间和左端开头、右端开头的最长连续区间。
二分最早的 r 使得 \([1,r]\) 的最长连续区间长度大于 x，\(\mathcal O(n\log^2n)\)。
query 时直接左区间优先即可，\(\mathcal O(n\log n)\)。
11日
P7076 动物园
贪心（？），CSP2020 T2。
将所有动物或起来，对于每一位，没有饲料或者有饲料并且已经购买，该位可以选或不选；有饲料且未购买，只能不选。
把每一位的答案乘一下，坑点是开了 unsigned long long 也见祖宗，需要特判 \(2^{64}\) 的情况。
12日
P7077 函数调用
拓扑 DP，CSP2020 T3。
考场上写的线段树暴力，好歹也是个不小的数据结构啊怎么才给 30 分！其实是不错的题。
可以发现单点加值，整体乘值，所有操作形成若干个 DAG，只要求最终序列，于是方向转向图论。
设所有乘法之积为 \(mul\)，每个点初始值的贡献一定是 \(a_i\times mul\)。
接下来考虑单点加和其之后的变化。每个单点加的贡献是后面所有乘法之积。
那么先预处理每个点的及后面乘法的积 \(m_i\)，然后按照操作序列倒着 DP 每个DAG 的贡献次数。
再在 DAG 里倒着 DP，\(f_v\leftarrow f_v + f_u, f_u\leftarrow f_u\times m_v\)，对于单点加的贡献就有 \(f_u\times val_u\)。
17日
P7078 贪吃蛇
博弈论+单调性优化，CSP2020 T4。
见博客题解。
20日
CF455D Serega and Fun
平衡树或者分块。
对于第一个操作可以用一棵 splay 轻松维护，称其为序列树。
因为值域 \(\mathcal O(n)\)，第二个操作考虑每个值维护一棵 splay，节点存其对应的序列树的编号。
每次询问一个区间要求在某一棵 splay 里寻找区间内最靠左和最靠右的点，可以通过在序列树上查 rank 来二分，单次 \(\mathcal O(\log^2n)\)。
S2OJ#41 新斯诺克
归并排序就够了。
可以让所有数减去 m，然后做前缀和，满足 \(j<i, s_j<s_i\) 的一对点构成一个合法区间。
二维偏序，可以做到 \(\mathcal O(n\log n)\)。这个煞笔又写了个比别多个 \(\log\) 的 CDQ 分治。
21日
S2OJ#42 方舟连接
区间 DP + 四边形不等式优化。
把路径看成一棵树，然后发现这是两两相邻子树合并，转化成一个序列就是区间 DP。
\(\mathcal O(n^3)\) 过不去，简单证明一下 DP 为凸，套上经典的四边形不等式优化，降到 \(\mathcal O(n^2)\)。
S2OJ#60 A Simple Math Problem VI
小数据裸完全背包。大数据特殊性质 \(a_i=1\)，组合数问题 见 OI wiki。
22日
P4093 [HEOI2016/TJOI2016]序列
CDQ 分治。
设 \(mi_i=\min\{val_i,w_i\},ma_i=\max\{val_i,w_i\}\)，求 LIS 的时候转移的条件为：
\(\begin{aligned} j&<i\\ val_j&\le mi_i\\ ma_j&\le val_i \end{aligned}\)
CDQ 分治，左右分别按上边对应的属性排序；优先递归处理左区间。复杂度 \(\mathcal O(n\log^2 n)\)。
26日
CF571D Campus
转化成树上问题 + 树状数组上二分技巧。
27日
GYM102331B Bitwise Xor
简单 DP + 01-trie。
28日
S2OJ#61 连续段的期望
二进制优化。
\(\operatorname{xor,or,and}\) 操作每一位互不影响，可以把每一位分开做（常规套路），其实也是其中 \(30\) 分部分分的意义。
对于一个 01 串：
- \(\operatorname{xor}\)，每个和为奇数的区间贡献为 \(1\)，通过类似差分的技巧扫一遍即可；
- \(\operatorname{and}\)，区间内全为 \(1\) 贡献为 \(1\)，所有每个连续为 \(1\) 的段贡献为 \(len^2\)；
- \(\operatorname{or}\)，反过来想，区间全为 \(0\) 的没有贡献。
记得每一位的答案乘上 \(2^i\)。
29日
S2OJ#52 练习曲
简单 DP。
不修改的话 DP 方程： \[ \begin{aligned} f_i&=\min_{i-L\le j<i}\{f_j\}+w(j+1,i)\\ w(j,i)&=\max\{\max_{j\le k<i}\{a_k\},\ a_i-1\} + 1 \end{aligned} \]
修改的话，发现一个点只影响 \(2L\) 个 DP 值，那么预处理正着和倒着分别 DP 一遍，处理影响的一段后拼接得到答案。
可以发现 \(f_i\) 是单调不降的。从 \((x-L,x]\) 中固定一个起点，当 \(x\) 所在段权值一定时，这一段越长越好。
所以每次只要 \(\mathcal O(L)\) 处理即可，复杂度 \(\mathcal O((n+q)L)\)。其实觉得过不了的。
30日
CF1175E Minimal Segment Cover
倍增。
设 \(f_{i,j}\) 表示从 \(i\) 点走 \(j\) 条线段能够到达最远的点，每次询问 \(\mathcal O(\log n)\) 跳到最远的不超过区间右端，再跳一条线段就是答案。