做题好慢啊。

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}$

复杂度 $O (n^{4})$ 。

3日

AcWing277 饼干

题目

简单 DP。

先贪心地让怨气值大的在前，则分配饼干个数单调不增，设 $f_{i, j}$ 表示前 i 个人分 j 个饼干最优答案。

简化状态，强制让最后一个人只得到 1 个，其他状态 $f_{i, j} \Leftarrow f_{i, j - i}$ 。

接下来只要考虑最后有多少个人同样分到 1 个就行。

复杂度 $O (n^{2} m)$ 。

P6564 [POI2007] 堆积木KLO

题目

CDQ，BIT，LIS 等均可。

$\begin{aligned} i & > j, \\ a_{i} & > a_{j}, \\ a_{i} - a_{j} & \leq i - j \end{aligned}$

满足后两个条件时一定满足第一个条件，转化为二维偏序直接上 CDQ。

因为一个 $>$ 一个 $\geq$ ，所以 $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_{2} n$ 级别（线性基）。

那么只要处理前 $\log_{2} n$ 的 $f^{i} (x)$ 即可，每次暴力 FWT 和 iFWT 可以做到 $O (n \log^{2} n)$ 。

丧心病狂的出题人 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}$

每次只要 $O (n)$ 即可得到单点的值，总复杂度降至 $O (n \log n)$ 。

P3047 [USACO12FEB]Nearby Cows G

题目

换根 DP。

先处理出 $f_{u, i}$ 表示以 u 为根的子树深度为 i 的点权和， $O (k)$ 转移。此时 1 的 DP 值为答案。

换根，每次将 u 的一个子树 v 贡献减去，分成两个独立的树，再由 u 转移到 v 即可。

换根 DP 的特点是能够快速地将子树分离、改变父子关系后合并

5日

P4161 [SCOI2009]游戏

题目

数论，背包 DP。

容易发现一个排列可以看成几个环，而变换回来的步数是这些环的 $lcm$ 。

问题转化成：n 拆成若干个数的和，这些数的 $lcm$ 的种数。

将 $lcm$ 唯一分解，每个质因子的指数为所有数该质因子的最大指数。

那么 DP 每个质数不同质数的情况下的方案数，转化成完全背包。

设 $f_{i, j}$ 表示到第 i 个质数，将 j 拆开的 $lcm$ 种数，则 $f_{i, j} \leftarrow f_{i - 1, j} + f_{i - 1, j - p_{i}^{k}}$ 。

因为无法处理 1，而 1 不影响 $lcm$ ，所以拆开的数的和不一定为 n，剩下的用 1 填满，最后答案为 $\sum_{i = 0}^{n} f_{c n t_{p}, i}$ 。

P6280 [USACO20OPEN]Exercise G

题目

和上题一样，只不过是求 $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，枚举断点后直接做， $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 m a (\mod b) & (1 < m < b) \\ x & = m a + n b & (1 < m < b, n < 0) \end{aligned}$

当 x 最大时， $m = b - 1, n = - 1$ ，证毕。

P5092 [USACO04OPEN]Cube Stacking

题目

并查集。

在 $x$ 和 $f a$ 的边之间维护压缩的边数，路径压缩优化，再维护每个并查集的 size。

P2894 [USACO08FEB]Hotel G

题目

线段树。

维护每个区间的最长连续区间和左端开头、右端开头的最长连续区间。

二分最早的 r 使得 $[1, r]$ 的最长连续区间长度大于 x， $O (n \log^{2} n)$ 。

query 时直接左区间优先即可， $O (n \log n)$ 。

11日

P7076 动物园

题目

贪心（？），CSP2020 T2。

将所有动物或起来，对于每一位，没有饲料或者有饲料并且已经购买，该位可以选或不选；有饲料且未购买，只能不选。

把每一位的答案乘一下，坑点是开了 unsigned long long 也见祖宗，需要特判 $2^{64}$ 的情况。

12日

P7077 函数调用

题目

拓扑 DP，CSP2020 T3。

考场上写的线段树暴力，~~好歹也是个不小的数据结构啊怎么才给 30 分！~~其实是不错的题。

可以发现单点加值，整体乘值，所有操作形成若干个 DAG，只要求最终序列，于是方向转向图论。

设所有乘法之积为 $m u l$ ，每个点初始值的贡献一定是 $a_{i} \times m u l$ 。

接下来考虑单点加和其之后的变化。每个单点加的贡献是后面所有乘法之积。

那么先预处理每个点的及后面乘法的积 $m_{i}$ ，然后按照操作序列倒着 DP 每个DAG 的贡献次数。

再在 DAG 里倒着 DP， $f_{v} \leftarrow f_{v} + f_{u}, f_{u} \leftarrow f_{u} \times m_{v}$ ，对于单点加的贡献就有 $f_{u} \times v a l_{u}$ 。

17日

P7078 贪吃蛇

题目

博弈论+单调性优化，CSP2020 T4。

见博客题解。

20日

CF455D Serega and Fun

题目

平衡树或者分块。

对于第一个操作可以用一棵 splay 轻松维护，称其为序列树。

因为值域 $O (n)$ ，第二个操作考虑每个值维护一棵 splay，节点存其对应的序列树的编号。

每次询问一个区间要求在某一棵 splay 里寻找区间内最靠左和最靠右的点，可以通过在序列树上查 rank 来二分，单次 $O (\log^{2} n)$ 。

S2OJ#41 新斯诺克

题目

归并排序就够了。

可以让所有数减去 m，然后做前缀和，满足 $j < i, s_{j} < s_{i}$ 的一对点构成一个合法区间。

二维偏序，可以做到 $O (n \log n)$ 。这个煞笔又写了个比别多个 $\log$ 的 CDQ 分治。

21日

S2OJ#42 方舟连接

题目

区间 DP + 四边形不等式优化。

把路径看成一棵树，然后发现这是两两相邻子树合并，转化成一个序列就是区间 DP。

$O (n^{3})$ 过不去，简单证明一下 DP 为凸，套上经典的四边形不等式优化，降到 $O (n^{2})$ 。

S2OJ#60 A Simple Math Problem VI

题目

小数据裸完全背包。大数据特殊性质 $a_{i} = 1$ ，组合数问题见 OI wiki。

22日

P4093 [HEOI2016/TJOI2016]序列

题目

CDQ 分治。

设 $m i_{i} = min {v a l_{i}, w_{i}}, m a_{i} = max {v a l_{i}, w_{i}}$ ，求 LIS 的时候转移的条件为：

$\begin{aligned} j & < i \\ v a l_{j} & \leq m i_{i} \\ m a_{j} & \leq v a l_{i} \end{aligned}$

CDQ 分治，左右分别按上边对应的属性排序；优先递归处理左区间。复杂度 $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}$

复杂度 $O (n^{4})$ 。

3日

AcWing277 饼干

题目

简单 DP。

先贪心地让怨气值大的在前，则分配饼干个数单调不增，设 $f_{i, j}$ 表示前 i 个人分 j 个饼干最优答案。

简化状态，强制让最后一个人只得到 1 个，其他状态 $f_{i, j} \Leftarrow f_{i, j - i}$ 。

接下来只要考虑最后有多少个人同样分到 1 个就行。

复杂度 $O (n^{2} m)$ 。

P6564 [POI2007] 堆积木KLO

题目

CDQ，BIT，LIS 等均可。

$\begin{aligned} i & > j, \\ a_{i} & > a_{j}, \\ a_{i} - a_{j} & \leq i - j \end{aligned}$

满足后两个条件时一定满足第一个条件，转化为二维偏序直接上 CDQ。

因为一个 $>$ 一个 $\geq$ ，所以 $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_{2} n$ 级别（线性基）。

那么只要处理前 $\log_{2} n$ 的 $f^{i} (x)$ 即可，每次暴力 FWT 和 iFWT 可以做到 $O (n \log^{2} n)$ 。

丧心病狂的出题人 $A z u s a C a t$ 竟然卡掉两个 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}$

每次只要 $O (n)$ 即可得到单点的值，总复杂度降至 $O (n \log n)$ 。

P3047 [USACO12FEB]Nearby Cows G

题目

换根 DP。

先处理出 $f_{u, i}$ 表示以 u 为根的子树深度为 i 的点权和， $O (k)$ 转移。此时 1 的 DP 值为答案。

换根，每次将 u 的一个子树 v 贡献减去，分成两个独立的树，再由 u 转移到 v 即可。

换根 DP 的特点是能够快速地将子树分离、改变父子关系后合并

5日

P4161 [SCOI2009]游戏

题目

数论，背包 DP。

容易发现一个排列可以看成几个环，而变换回来的步数是这些环的 $lcm$ 。

问题转化成：n 拆成若干个数的和，这些数的 $lcm$ 的种数。

将 $lcm$ 唯一分解，每个质因子的指数为所有数该质因子的最大指数。

那么 DP 每个质数不同质数的情况下的方案数，转化成完全背包。

设 $f_{i, j}$ 表示到第 i 个质数，将 j 拆开的 $lcm$ 种数，则 $f_{i, j} \leftarrow f_{i - 1, j} + f_{i - 1, j - p_{i}^{k}}$ 。

因为无法处理 1，而 1 不影响 $lcm$ ，所以拆开的数的和不一定为 n，剩下的用 1 填满，最后答案为 $\sum_{i = 0}^{n} f_{c n t_{p}, i}$ 。

P6280 [USACO20OPEN]Exercise G

题目

和上题一样，只不过是求 $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，枚举断点后直接做， $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 m a (\mod b) & (1 < m < b) \\ x & = m a + n b & (1 < m < b, n < 0) \end{aligned}$

当 x 最大时， $m = b - 1, n = - 1$ ，证毕。

P5092 [USACO04OPEN]Cube Stacking

题目

并查集。

在 $x$ 和 $f a$ 的边之间维护压缩的边数，路径压缩优化，再维护每个并查集的 size。

P2894 [USACO08FEB]Hotel G

题目

线段树。

维护每个区间的最长连续区间和左端开头、右端开头的最长连续区间。

二分最早的 r 使得 $[1, r]$ 的最长连续区间长度大于 x， $O (n \log^{2} n)$ 。

query 时直接左区间优先即可， $O (n \log n)$ 。

11日

P7076 动物园

题目

贪心（？），CSP2020 T2。

将所有动物或起来，对于每一位，没有饲料或者有饲料并且已经购买，该位可以选或不选；有饲料且未购买，只能不选。

把每一位的答案乘一下，坑点是开了 unsigned long long 也见祖宗，需要特判 $2^{64}$ 的情况。

12日

P7077 函数调用

题目

拓扑 DP，CSP2020 T3。

考场上写的线段树暴力，~~好歹也是个不小的数据结构啊怎么才给 30 分！~~其实是不错的题。

可以发现单点加值，整体乘值，所有操作形成若干个 DAG，只要求最终序列，于是方向转向图论。

设所有乘法之积为 $m u l$ ，每个点初始值的贡献一定是 $a_{i} \times m u l$ 。

接下来考虑单点加和其之后的变化。每个单点加的贡献是后面所有乘法之积。

那么先预处理每个点的及后面乘法的积 $m_{i}$ ，然后按照操作序列倒着 DP 每个DAG 的贡献次数。

再在 DAG 里倒着 DP， $f_{v} \leftarrow f_{v} + f_{u}, f_{u} \leftarrow f_{u} \times m_{v}$ ，对于单点加的贡献就有 $f_{u} \times v a l_{u}$ 。

17日

P7078 贪吃蛇

题目

博弈论+单调性优化，CSP2020 T4。

见博客题解。

20日

CF455D Serega and Fun

题目

平衡树或者分块。

对于第一个操作可以用一棵 splay 轻松维护，称其为序列树。

因为值域 $O (n)$ ，第二个操作考虑每个值维护一棵 splay，节点存其对应的序列树的编号。

每次询问一个区间要求在某一棵 splay 里寻找区间内最靠左和最靠右的点，可以通过在序列树上查 rank 来二分，单次 $O (\log^{2} n)$ 。

S2OJ#41 新斯诺克

题目

归并排序就够了。

可以让所有数减去 m，然后做前缀和，满足 $j < i, s_{j} < s_{i}$ 的一对点构成一个合法区间。

二维偏序，可以做到 $O (n \log n)$ 。这个煞笔又写了个比别多个 $\log$ 的 CDQ 分治。

21日

S2OJ#42 方舟连接

题目

区间 DP + 四边形不等式优化。

把路径看成一棵树，然后发现这是两两相邻子树合并，转化成一个序列就是区间 DP。

$O (n^{3})$ 过不去，简单证明一下 DP 为凸，套上经典的四边形不等式优化，降到 $O (n^{2})$ 。

S2OJ#60 A Simple Math Problem VI

题目

小数据裸完全背包。大数据特殊性质 $a_{i} = 1$ ，组合数问题见 OI wiki。

22日

P4093 [HEOI2016/TJOI2016]序列

题目

CDQ 分治。

设 $m i_{i} = min {v a l_{i}, w_{i}}, m a_{i} = max {v a l_{i}, w_{i}}$ ，求 LIS 的时候转移的条件为：

$\begin{aligned} j & < i \\ v a l_{j} & \leq m i_{i} \\ m a_{j} & \leq v a l_{i} \end{aligned}$

CDQ 分治，左右分别按上边对应的属性排序；优先递归处理左区间。复杂度 $O (n \log^{2} n)$ 。

26日

CF571D Campus

题目

转化成树上问题 + 树状数组上二分技巧。

见博客

27日

GYM102331B Bitwise Xor

题目

简单 DP + 01-trie。

见博客

28日

S2OJ#61 连续段的期望

题目

二进制优化。

$xor, or, and$ 操作每一位互不影响，可以把每一位分开做（常规套路），其实也是其中 $30$ 分部分分的意义。

对于一个 01 串：

$xor$ ，每个和为奇数的区间贡献为 $1$ ，通过类似差分的技巧扫一遍即可；
$and$ ，区间内全为 $1$ 贡献为 $1$ ，所有每个连续为 $1$ 的段贡献为 $l e n^{2}$ ；
$or$ ，反过来想，区间全为 $0$ 的没有贡献。

记得每一位的答案乘上 $2^{i}$ 。

29日

S2OJ#52 练习曲

题目

简单 DP。

不修改的话 DP 方程： $\begin{aligned} f_{i} & = min_{i - L \leq j < i} {f_{j}} + w (j + 1, i) \\ w (j, i) & = max {max_{j \leq k < i} {a_{k}}, a_{i} - 1} + 1 \end{aligned}$

修改的话，发现一个点只影响 $2 L$ 个 DP 值，那么预处理正着和倒着分别 DP 一遍，处理影响的一段后拼接得到答案。

可以发现 $f_{i}$ 是单调不降的。从 $(x - L, x]$ 中固定一个起点，当 $x$ 所在段权值一定时，这一段越长越好。

所以每次只要 $O (L)$ 处理即可，复杂度 $O ((n + q) L)$ 。其实觉得过不了的。

30日

CF1175E Minimal Segment Cover

题目

倍增。

设 $f_{i, j}$ 表示从 $i$ 点走 $j$ 条线段能够到达最远的点，每次询问 $O (\log n)$ 跳到最远的不超过区间右端，再跳一条线段就是答案。