十二月份训练手记

12.1 - 1 - Problem - E - Codeforces

思路

想了一会关于区间的方向未果，意识到一件事情，就是固定区间的一端，则区间 $\mathrm{l}\mathrm{c}\mathrm{m}$ 每次变化必然至少倍乘 $2$ ，又因为区间长度有限，仅考察质数的话一定无法容纳第 $n$ 个质数，所以答案有了一个 $top=w^{-1}(n)$ 的上界，只需要统计这之下的数字出现情况即可，再考察倍乘的性质就知道以某个元素为右端点的区间有效答案至多只有 ${\log }_2(top)$ 数量级，所以我们统计以每个元素为右端点的区间有效答案存入一个 set （其他的什么也可以，这个方便一点），然后从左到右转移顺便记录数字出现情况，最后找到第一个未出现的数字就可以了

收获 & 反思

简单 $\mathrm{l}\mathrm{c}\mathrm{m}$ 性质，十分钟做不出来就该艾草了

12.1 - 2 - Problem - F - Codeforces

思路

首先不难发现对于每一个位置编号比自身数值来得大的元素，一定需要一次 $\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}$ 来帮他归位，设这种元素的数量为 $w$ ，显然我们需要至少 $w$ 次 $\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}$ 操作

然后我们考虑构造到整个下界，想法也很简短，对于置换上的每一个置换环，考虑环上的每一段连续的 “向后跳” 的边（对应着一串可以被连续转移的位置编号比自身数值来得小的元素） 对应着至少一个 “向前跳” 的边，也就是我可以按置换环中的最小元素排列后，这样处理每一个置换环：

• 从起点最小的一段连续的 “向后跳” 的边出发，沿着边运送数字，直到遇见第一个向前跳的边的起点，带着这个元素回到起点再送到对应的位置
• 此接下去重复第一部分直到整个置换环被完全 “修正”，此时指针应该在环的最小节点处并且缓冲区为空，所以我们可以不用返回直接寻找下一个置换环继续操作

这样就证明了答案的充要性，维护答案也很简单，注意到每个元素做贡献至多三个区间，打上差分标记后前缀和统计即可

至于反转操作就更没意思了，对反序列也求一遍答案并实时维护对应的反序列的状态即可

收获 & 反思

充要性的证明，还蛮好玩的，算半个构造题吧

12.2 - 1 - Problem - D2 - Codeforces

思路

很好考虑，也很好玩

我们发现 $k$ 可能会巨大无比，所以考虑倍增或者找规律之类的东西，显然这种东西和倍增没什么关系，于是专心看看有没有什么可以发扬人类智慧的地方

首先是对于 $k\le n$ 的情形，不难想到我们可以将每次操作都应用为 $+$ ，也就是我们会给当前最小的元素 $+k$ ，次小的 $+k-1$ ...... 以此类推，这样的正确性是显然的，此时打表即可

然后不难注意到，当 $k=n+2m$ 的时候，我们可以贪心地让最后 $n$ 次操作均为加法，而前面就是 $2m$ 次的加减交替，并且一加一减需要作用在同一个元素上，也就是 $m$ 次的减一操作，考虑调换操作顺序，依然贪心地先分配最后的 $n$ 次加操作，然后我们开始 “削顶”，每次对最大的元素减一，这可以保证我们在某一答案可行的时候一定能构造出来，所以条件是充要的。此时，我们只需要记录在经过一轮的加操作之后，各个元素超出最小值的总和，就可以在询问的时候 $\mathrm{O}(1)$ 判断

那最后就来到了比较神秘的 $k=n+2m-1$ 的情况，本来一直想不出什么思路，直到注意到一个东西：对于之前 $k=n+2m$ 的情况，我可以保证每个元素最后都是蓝色，也就是都以加操作结尾，但是对于 $k=n+2m-1$ 若所有元素都已加操作结尾，那么除开每最后一次加操作应该是若干个 “变蓝 - 变红” 的颜色循环，但实际上只剩下 $2m-1$ 次操作，无法成对，所以矛盾了，也就是至少有一个元素以减操作结尾（或是没有被操作过），此时由操作参数的递增性质可以得出，这个元素一定不比其初值来得大。根据贪心的想法，我们意识到让最大的元素做这个 “不增” 的元素一定是不劣的，所以问题就变成了对前面 $n-1$ 个元素做 $n-1+2m$ 次操作，就变得和上一情况一样了，但是值得注意的一点是，如果前 $n-1$ 个元素的最小值比留出的元素小，那么留出的元素也可以用于 “削顶”，否则需要与留出的元素取最小值

收获 & 反思

很喵喵的题目，思维比较灵活，好题

12.3 - 1 - Problem - B - Codeforces

思路

我们考虑固定手上的彩票号码之后，怎么去求让我们能中奖的号码有多少？

我们不妨假设我们的号码 $x$ 比中奖号码小，那么我们只需要往右找到第 $k$ 个大于我们的数 $x_k$，只要这个数离中奖号码比我们来的远我们就可以中奖，也就是左边界为 $\lfloor \frac{x+x_k-1}{2}\rfloor$ ，特别地，当 $x=x_k$ ，不存在大于等于 $x$ 的中奖号码

同理可以求出右侧的端点，从而计算出总共可能的中奖号码数量

由上述的计算方式我们不难发现，当 $x$ 在两个元素之间的时候，答案只和奇偶性有关，所以对两个元素中间的部分只需要枚举两个，这样我们就可以枚举答案来检查了

最后注意特殊情况，就是如果所有情况都可以中奖，那么答案就是 $0$

收获 & 反思

感觉思路不是特别难，但是为什么想不到呢？可能是因为没有手玩？

12.4 - 1 - Problem - E - Codeforces

思路

注意到不寻常的 $k$ 的范围，这启发我们从 $k-1$ 向 $k$ 来递推

因为显而易见的 $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$ ，又观察 $b_i$ 的生成方式，就有 $b_{k,i}=b_{k-1,i-1}+b_{k,i-1}$ 于是就可以在 $\mathrm{O}(nk)$ 的时间复杂度内算出来了

收获 & 反思

需要一点注意力，我的注意力虽然不多，但够用

12.5 - 1 - Problem - F - Codeforces

思路

我们知道一个经典的反悔贪心问题是 “给定权值总和上限，求最多选取物品数”，这启发我们这题可以直接二分答案，check 很简单，用本次二分的时间上限正反两个方向跑一遍反悔贪心，然后就可以检查是否有一个划分方法使得前后在时限内完成的任务数之和满足要求

就是这样，做完了...... 吗？

傻逼出题人全家活暗暗卡你吗的 multiset 的常数

换成 priority_queue 就过了

收获 & 反思

没什么好说的，经典反悔贪心 + 经典二分答案

哦，priority_queue 常数小

12.6 - 1 - Problem - F - Codeforces

神秘喵喵题

思路

我们发现这题比较神秘的地方在于他有一个 “差的绝对值”，这使得我们子树内的答案在转移的时候必须对 $k$ 进行分类讨论，具体地，我们需要求出 $|sum-(k-sum)|=|k-2sum|$ 的值

更深入地思考一下会得出一个结论，就是黑色节点一定形成一个连通块，证明很简单：

• 若不是一个连通块，那么一定存在一条边连接一个黑点和一个白点，并且断开之后黑点所属的连通块包含更少数量的黑点，此时将这条边两端的节点颜色调换，答案一定更优

显然在这个连通块以外的边贡献固定为 $k$ 所以我们考虑在这个 “黑树” 上如何统计答案，考虑一个很重要的事情，就是对于一棵树的重心，其任意非根节点的子树大小均不超过节点总数的一半，也就是 $|k-2sum|=k-2sum$ ，就可以把绝对值去掉了，此时每个点对答案的负贡献与其深度（在多少条边的子树里）成正比，所以我们 BFS 一遍按深度逐个取点即可

但是如果枚举重心出错怎么办？不难发现此时的答案一定不优，所以并不影响最终答案的求取

收获 & 反思

重心的神秘性质，好玩的勒

1. 等价定义：

   • 在树中删去结点 $v$ 后，得到的图 $T\setminus \{v\}$ 中每个连通分量的大小均不超过原树结点数的一半。

   • 在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小。

   • 树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小。

2. 树的重心如果不唯一，则恰有两个。这两个重心相邻。而且，删去它们的连边后，树将变为两个大小相同的连通分量。

3. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

4. 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树的重心的路径上。

5. 一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。

12.7 - 1 - Problem - F - Codeforces

思路

我们很容易就能想到用 dp 来做这个东西，但是我们发现一件事情：dp 需要三维：横坐标，纵坐标，时间，这样看的话好像一定会超时

但是我们可以注意到一件事情：既然角色只能向右下方运动或者停止，那么角色到某一个坐标处的时间和他这一路上的停止次数是可以相互求出的，又不难发现角色至多只会停下来规避轨道炮至多 $r$ 次，所以我们将时间复杂度优化到了 $\mathrm{O}(nmr)$ 就可以通过这道题了

收获 & 反思

在 dp 的时候，设状态是很重要的，考虑尽可能多的利用已知的信息去简化我们的状态描述，减少总状态数

12.8 - 1 - Problem - F - Codeforces

思路

考虑对于每个数有四种状态：除 + 减，除，减，什么都不干。

• 引理 1：操作全用完一定不劣。

• 引理 2：对于除 + 减的数，一定先除后减。

接下来将所有数从大到小排列，得到 $a_1,a_2,\cdots ,a_n$。

显然除 + 减的数一定是一段前缀。直接枚举前缀 $k_0$。

为了方便，令 $max(0,k_1+k_2-n)\le k\le min(k_1,k_2)$。鉴于引理 1，这样做没问题。

剩下了 $k_1-k$ 个除和 $k_2-k$ 个减。

• 引理 3：除了 $a_1,a_2,\cdots ,a_k$，进行操作的数字必然是 $a_{k+1},a_{k+2},\cdots ,a_{k_1+k_2-k}$。

对于 $a_{k+1},a_{k+2},\cdots ,a_{k_1+k_2-k}$，按照与 $b$ 的大小关系，分成两段：

$a_{k+1},a_{k+2},\cdots ,a_p$ 与 $a_{p+1},a_{p+2},\cdots ,a_{k_1+k_2-k}$。

假设已经给两段分别配好了各自除和减的数量，那么确定具体的对每个数字的操作呢？

1. 对于不小于 $b$ 的 $a_{k+1},a_{k+2},\cdots ,a_p$：

   • 减操作的贡献一定是 $b$，而除操作对于 $a_x$ 的贡献是 $\lfloor \frac{a_x}{2}\rfloor$。
   • 既然减给谁都无所谓，那么显然要给大的数据，给小的数减。

   即对于 $a_{k+1},a_{k+2},\cdots ,a_p$ 的操作是：// ---。

2. 对于小于 $b$ 的 $a_{p+1},a_{p+2},\cdots ,a_{k_1+k_2-k}$：

   • 对于 $a_x$，减操作的贡献是 $a_x$，除操作的贡献是 $\lfloor \frac{a_x}{2}\rfloor$。显然，我们应当给大的数据，给小的数除。

   即对于 $a_{p+1},a_{p+2},\cdots ,a_{k_1+k_2-k}$ 的操作是：--- //。

发现了什么？$a_{k+1}$ 到 $a_{k_1+k_2-k}$ 的操作是先除，再减，最后除。

所以我们不用真的对 $a_x$ 根据 $b$ 分段，只需要在枚举 $k$ 之后，再枚举前缀为一段的开头 $a_p$ 即可。可以通过简单的 $O(n)$ 预处理达到单次 $O(1)$ 算出一个方案的答案。

时间复杂度 $O(n^2)$。

收获 & 反思

很好玩的贪心，好像还有 wqs 二分的做法，后面再说吧

12.9 - 1 - Problem - F2 - Codeforces

思路

首先需要明确一个性质，就是对于带有可重元素的序列，完全排序所需的步骤数依旧是元素数量减去能构造出来的环的数量的最大值，而显然若构造出来的环中存在两个相同的元素，则可以断成两个环，由此可知我们能最大化的交换次数等于元素总数减去数量最多的元素的个数，也就是恰好每个环中都含有一个数量最多的元素

换而言之，我们要检查一个序列是否是最大化交换次数的，就可以去找是否有一个环不包含数量最多的元素，如果能找到，说明可以构造更多环，也就是需要的交换次数并非最大值

接下来就是找环，直接优化建图（采用对应数值的虚拟节点作为边的中转站）然后在图上找环即可，对于有向图找环，一个简单的方法就是拓扑排序，不断删去入度为 $0$ 的点，剩下的部分就一定有环

收获 & 反思

核心出装：

• 排列上环的数量与交换次数的关系
• 中继节点优化建图
• 拓扑排序判环

12.10 - 1 - Problem - E - Codeforces

思路

考虑作为 “二者选其一” 的经典模型来做，先假设最开始全都变成 $1$，那么对于原来是 $0$ 的点，划为 $0$ 的收益就是 $v_i$ （相当于撤回开销），划为 $1$ 的收益是 $0$ ，所以向源点连权值为 $v_i$ 的边；对于原来是 $1$ 的点，划为 $0$ 的收益是 $-v_i$ （进行操作） ，划为 $1$ 的收益是 $0$ ，所以向汇点连权值为 $v_i$ 的边

而对于每个人要求的组合，如果要求为 $1$ ，那么一开始就被满足，可能的收益是 $-w_i(-g)$ ，向汇点连相应大小的边，而对于要求为 $0$ 的，可能的收益是 $w_i+g$ ，向源点连相应大小的边，最后跑最小割，用总收益减去最小割即可。

这里关于总收益减去最小割的推导：

• 原先的收益是所有要求为 $1$ 的 $w_i$ ，减去要求为 $0$ 的赔款 $G$ ，再减去所有初始为 $0$ 的点的改造费用，也就是：

  $$\sum _{nee{d}_i=1}{w}_i-\sum _{se{x}_i=0}{v}_i-\sum _{nee{d}_i=0}g$$

• 考虑我们收益的变化量是所有连向源点的边的权值之和减去最小割，也就是：

  $$\sum _{nee{d}_0=1}(w_i+g)+\sum _{se{x}_i=0}{v}_i-minCut$$

• 也就是我们最后的总收益为：

  $$\begin{array}{rl}& (\sum _{nee{d}_i=1}{w}_i-\cancel{\sum _{se{x}_i=0}{v}_i}-\cancel{\sum _{nee{d}_i=0}g})+(\sum _{nee{d}_i=0}{w}_i+\cancel{\sum _{nee{d}_i=0}g}+\cancel{\sum _{se{x}_i=0}{v}_i}-minCut)\\ \\ & =\sum w_i-minCut\end{array}$$

收获 & 反思

经典的网络流建模思路，多练，别到时候犯傻了板子题不会做

12.10 - 2 - Problem - G - Codeforces

思路

不难发现钦定一个根节点之后，一次操作相当于把所选的节点深度 $-1$ 且子树内每个节点的深度 $-2$ ，注意到这只改变了所选节点的深度的奇偶性，所以至少需要对应的奇数点或偶数点的数量次操作（根节点不计）才能达成要求，至此必要性得到证明

考虑证明充分性，就是在按照深度从大到小来操作每一个节点，就可以达到要求（容易证明），至此，我们只需要看看哪种奇偶性的节点数量较少就可以了

收获 & 反思

没什么好说的，简单结论题

12.11 - 1 - Problem - C - Codeforces

思路

既然它保证了两个多项式是相似的，那么我们只要找一个必要条件就可以了

原本的多项式次数太高了，我们考虑给他求导降次，但是我们又不知道他的表达式，于是我们可以把原本的多项式看作一个下降幂多项式，然后对他做等间距（间距为 $1$ ）的差分，这在下降幂多项式中的意义与求导类似

于是我们就可以知道求他的 $d-1$ 阶差分之后，$A(x+s)$ 和 $B(x)$ 会变成两个一样的一次函数，此时利用剩余的点值就可以解出 $s$ 的值

问题就在于我们当然不会求出所有的 $d-1$ 阶差分，我们可以利用 $k$ 阶差分在生成函数意义下等价于原多项式乘上 $(1-x{)}^k$ ，于是就可以快速地得到原点值的每一项对于高阶差分某一项的贡献，具体地，有：

$${\mathrm{\Delta }}^{k}f(x)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})(-1{)}^{k-i}f(x+i)$$

于是就只需要预处理组合数就行了

收获 & 反思

一些非常色情的知识点，值得反复学习：有限微积分与数列求和 - 洛谷专栏

12.12 - 1 - Problem - E - Codeforces

思路

一件显而易见的贪心思想就是，如果一个人需要的某一种食物，它的数量大于等于需要它的人数，那么这个人的需求一定可以被满足，不会和其他人产生可能的竞争，所以我们贪心地把他放到最后一个

我们接着这个思路，考虑证明这是存在答案的充要条件：

• 首先考虑充分性：若对于每一步我们都能找出这样的人放到序列的最后，那么显然可以构造出一个合法的序列
• 然后考虑必要性：考虑反证，因为前面的操作是不具备后效性的，所以如果到了某一步为止，场上所有的食物的需求都大于储备，那么不妨考虑任何一个人进厨房，除非某种食物的余量为 $0$ ，否则这个人需要的两种食物的储备和需要他们的人数都会减少一，也就是场面依然保持 “场上所有的食物的需求都大于储备”，考虑操作到只剩一个人，那么由于 $x\ne y$ ，所以这个人一定没东西吃，必要性证明完毕

于是我们只需要统计每个食物的需求量和储存量，然后不断取出 “储量安全” 的食物的需求者，把他们放进末尾并且维护对应食物的需求人数即可

收获 & 反思

经典的贪心 + 证明充要条件，没什么好说的，做不出来埃及拔草

12.12 - 2 - Problem - 833B - Codeforces

思路

不难意识到这个 $k$ 很小，是题目在启发我们做 $1\sim k$ 的动态规划，不妨用 $dp[i][j]$ 表示对于前 $j$ 个数，将其分为 $i$ 段的最大收益，用 $val(x,j)$ 表示区间 $[x,j]$ 上不同元素的个数，一个很朴素的转移方程如下：

$$dp[i][j]=\underset{x=i}{\overset{x<=j}{max}}\left(dp[i-1][x-1]+val(x,j)\right)$$

我们不难发现其复杂度瓶颈在于我们每次更新都需要比较 $\mathrm{O}(n)$ 个元素，所以我们考虑用数据结构来优化 dp ，具体地，我们初始时用前一层的 $dp$ 值，全部向后移一位（为了满足式子中的 $x-1$ ）来建树，然后使用经典的区间加来维护固定左端点的 $val$ 值，并维护区间最大值，每次查询就只需要 $\mathrm{O}(\log n)$ 次操作了，时间复杂度能够接受

收获 & 反思

考虑数据结构优化 dp ，不只是简单的查询，也可以是以便查询一边有修改

12.13 - 1 - P1361 小 M 的作物

思路

简单的网络流 “二者选其一模型”，作为练习题做

12.13 - 2 - P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

思路

简单的网络流 “二者选其一模型”，作为练习题做

12.13 - 3 - P4313 文理分科

思路

简单的网络流 “二者选其一模型”，作为练习题做

12.13 - 4 - P1646 [国家集训队] happiness - 洛谷

思路

简单的网络流 “二者选其一模型”，作为练习题做

12.13 - 5 - Problem - 1975F - Codeforces

非常厉害题

思路

真的是神仙题，不知道怎么出出来的，不知道怎么想出来的

大概题意就是给定一系列二进制数 $v_i$，对应着一系列集合 $V_i$ （$V_i=f^{-1}(v_i)$），要求所有可能的 $S$ 使得 $S$ 与所有 $x$ 所代表的集合的交的元素数量属于 $V_i$ ，并且升序输出

直接来做的话，不难想到枚举 $S$ 然后逐一校验，但是这样操作的开销是 $\mathrm{O}(2^{2n})$ 的，无法接受，我们考虑如何优化

这就是本题最厉害的地方了，对于一个要求

$$\mathrm{\forall }t\in [0,2^n),|S\cap f^{-1}(t)|\in f^{-1}(v_t)$$

我们考虑集合 $S$ 的最后一位：

• 如果最后一位是 $0$ ，那么他始终不做贡献，也就是对于 $S$ 来说，对 $t$ 的要求和对 $t\oplus 2^{n-1}$ 的要求是一样的，所以可以合并为一个要求

  $$\begin{gathered} \mathrm{\forall }t\in [0,2^{n-1}),|S\cap f^{-1}(t)|\in (f^{-1}(v_t)\mathrm{\&}{f}^{-1}(v_{t^{\prime }})) \\ {t}^{\prime }=t\oplus 2^{n-1} \end{gathered}$$

• 如果最后一位是 $1$ ，那么他只在 $t$ 的相应位为 $1$ 时有 $1$ 点贡献，也就是对于 $S$ 来说，对 $t$ 的要求恰好比对 $t\oplus 2^{n-1}$ 的要求少一的，所以也可以合并为一个要求

  $$\begin{gathered} \mathrm{\forall }t\in [0,2^{n-1}),|S\cap f^{-1}(t)|\in (f^{-1}(v_t)\mathrm{\&}(f^{-1}(v_{t^{\prime }})>>1)) \\ {t}^{\prime }=t\oplus 2^{n-1} \end{gathered}$$

至此一个规模为为 $2^n$ 的问题就转化为了两个规模为 $2^{n-1}$ 的问题，于是可以分析得出原问题可以在 $\mathrm{O}(n{2}^n)$ 的时间复杂度内完成

具体地，我们每次将 $S$ 分为两类，将原数组处理为新的要求数组传递到子问题，通过类似于 DFS 的方式来检查每一个 $S$ 是否合法，由于最后一次固定有 $n=0$ ，于是此时只需要检查这个子问题中 $S\mathrm{\&}{v}_0$ 就可以了。特别地，我们没有定义 $v_0$ 的值，但是由于任何数与 $f^{-1}(0)$ 的交集大小都为 $0$ ，于是只需要令 $v_0=1$ 即可自洽。

收获 & 反思

真的超级厉害题，对于这种 “要求” 类型的题目，可以考虑往归纳要求，合并要求，收敛子问题这样的方向去思考

12.14 - 1 - Problem - 2128F - Codeforces

非常厉害最短路

思路

我们考虑先证明如下引理

• 如果存在方案，那么将方案中对应的最短路全部取下界，其他边全部取上界一定是一个合法的构造
  • 因为增加不在路上的边长不会改变最短路，也不会使任何经过 $k$ 的路径缩短，一定不劣
  • 同时，减少在路上的边长至多只会使任何经过 $k$ 的路径减少同样的长度，路径长短关系不变，一定不劣
• 那既然能这样构造，那么题意等价于存在一条路径，按照上边的方法构造之后，使得你从路径上任意一点出发去 $k$ 在回到路径上任意一点都要比直接沿着路径走来得慢
  • 充分性显然，若能构造则一定合法
  • 必要性，如果对于任意一条路径都不存在，说明任何上述构造都不合法，又因为若有合法路径一定能由上述构造构造出来，所以若不存在则没有合法方案
• 最后就是最牛逼的部分了，我们对问题做非常厉害的改写：
  • 考虑你是一名通缉犯，沿着长度为下界的边移动，你每走到一个节点处，这里的人就会尝试去警察局 $k$ 点报警，此后警察会出警来抓你，你需要考虑能否有一条路使得你能够不被抓到从 $1$ 到达 $n$
  • 对于这个问题，我们显然是可以用 Dijkstra 来维护求出的：我们令 $di{s}_i$ 表示到某个点的时候警察最短已经出警的时间，如果还未出警就为负值，表示即将出警，转移就是从前一个结点出警的警察和新的报警人之间取最值，若到某个点处 $di{s}_i$ 大于等于 $k$ 点沿上界边到该点的最短路，说明在此点被捕无法避免，则无法用这个点继续松弛

至此问题得解

收获 & 反思

非常厉害题，都不知道怎么想出来的

就直接改写了？就直接改写了？

12.15 - 1 - Problem - 601E - Codeforces

思路

经典的线段树分治，用暴力维护添加元素来代替 “删除” 操作

但是在这道题当中，背包 dp 用到的数组不支持回退操作，直接给每个节点开一个的话又会爆空间，于是我们隆重介绍 —— 按深度优化空间存储

不难意识到，到了子节点的时候，我们只需要从父结点继承上一个状态，再将自身的节点信息维护进去就可以，而这个过程中有意义的数组数量始终不超过树的深度，也就是我们只要为每个节点保留其上一层的数组信息，就可以当作 “副本” 或者 “回溯”，此时占用的空间数量级会大大减少

收获 & 反思

嘛，就是这样

12.16 - 1 - Problem - 1819D - Codeforces

动态规划好题

思路

我们考虑最后的答案来自哪些商店的贡献，不难发现一定是来自最后某一段后缀，那自然就有这个后缀不能有重复元素并且越长越好，那我们就需要找到一个方案，使得最后一次清空操作尽可能的早

考虑动态规划，求取每一个点 “能否在此处被清空”，记作 $f_i$ ，每个点中元素最晚一次出现的位置记作 $po{s}_i$ ，并且维护 $t$ 表示最近一次清空商店的最早时间（显然，最近一次清空商店的时间越晚，我们的操作空间才越大，才能保证能正确求出 $f_i$ ），那么对于一个点，首先考虑维护 $f_i$ ：

• 如果 $po{s}_i>t$ ，也就是最后一次清空商店后出现了该商店内有的元素，那么显然有 $f_i=1$
• 如果 $po{s}_i\le t$ ，那么就没有重复元素，只能找 $(po{s}_i,i]$ 范围内有没有 $0$ 号商店，如果有则 $f_i=1$ ，否则 $f_i=0$

如果 $f_i=1$ ，则考虑维护 $t$ （否则 $t$ 不变） ：

• 如果 $po{s}_i>t$ ，那么直接令 $t=po{s}_i$ 再进行接下来的调整，因为 $t$ 在 $po{s}_i$ 之前必然会导致此次清空，是最坏结果
• 如果 $po{s}_i\le t$ ，我们就令 $t$ 为此后第一个 $f_i=1$ 的位置，因为到这里就能处理掉所有前面带来的 “可能重复” 的元素

最后我们贪心的取一个最长的合法后缀统计答案即可

收获 & 反思

依旧考虑动态规划的本质：

• 你维护的东西能解决问题
• 你维护的东西没有后效性（是一个独立的子问题，且可以高效支撑后续求解）

并且考虑动态规划设计过程中的常见思想：

• 利用贪心来构建单调性，或是确认 / 简化维护对象，譬如这题里的 “最近一次清空商店的最早时间”
• 尝试挖掘一些性质来作为跳板
• 如果单一的变量不好维护或性质不良，那么就考虑拆分答案或者组合贡献来维护
• 必要时，使用数据结构来优化动态规划过程

12.17 - 1 - Problem - 79D - Codeforces

思路

非常厉害题，还有 plus 版本

我们考虑把这个问题一步一步转化，首先是常见的区间操作换为两点处的差分操作，还有就是操作显然可逆，所以考虑如何把目标序列转化为全零串

这样一来，原本的若干区间取反就变为了若干点对的取反，而我们不难意识到，如果要消去一个点对 $(u,v)$，那么我们将进行一系列形如 $(u,x_1),(x_1,x_2),\cdots ,(x_n,v)$ 的操作，我们将操作看作连边，数位看作节点，如何用最少的步数消去特定点对就是一个最短路问题，可以用 BFS 来解决，于是就可以求出这些点两两之间消去的最少使用步骤

接下来的问题就是如何把所有点都消去，显然，如果我们建立一个新图，图上只有需要被消去的位数，两点之间的边权就是这两点消去的代价，不难意识到答案就是这张图的最小权完美匹配，对于 $n$ 个点的图复杂度是 $\mathrm{O}(n^3)$ ，但是这道题没有那么抽象和毒瘤，注意到点数非常的小，所以我们只需要暴力枚举子集跑状压 DP 就可以了

收获 & 反思

常用的转化思路：

• 区间操作换为两点处的差分操作
• 若操作可逆，则考虑如何目标态转化为初始状态
• 消去点对，等价于一系列头尾相连的操作

[双倍经验（未完成）](P3943 星空 - 洛谷)

12.18 - 1 - Problem - F - Codeforces

神秘计数题

思路

首先需要借用一下之前某道题的小结论（历历在目）

就是我们考虑在 $n$ 个可重元素中，每次至多消去 $k$ 个互不相同的元素，用尽可能少的次数消完，有一个结论就是答案是 $min(maxCnt,\lceil \frac{n}{k}\rceil )$ ，也就是说，一定能保证每次能消去任意小于当前不同元素种数，于是就有，我们最终 “合并” 出来的集合只要满足最大值不超过元素种数，并且从大到小排序的前缀和均不超过按照每步都取物品种数的取法的前缀和 $pref[i]$ （也就是理论上每步都取最多）

但是最终分出的组的总数并没有固定，所以我们不妨把所有的分法都用空集补齐到 $n$ 个，这就和 “划分物品” 问题等价了，于是我们有了一个在固定顺序下，充要的限制，就可以考虑 DP 来计数：记 $dp[i][j][k]$ 表示考虑到第 $i$ 大的集合为止，总和为 $j$ 且第 $i$ 次划分了 $k$ 个物品的方案数，于是转移方程就是：

$$dp[i][j][k]=\sum _{x\le k\le j}dp[i-1][j-k][x](j\le pref[i])$$

乍一看转移需要的开销是 $\mathrm{O}(n^4)$ 的，但实际上我们可以用前缀和优化来实现 $\mathrm{O}(1)$ 转移，并且注意到前 $i$ 个集合的元素数量都至少为 $k$ ，所以有 $i\times k\le n$ ，所以总状态数其实是 $\mathrm{O}(n^2\log n)$ 级别的，配合滚动数组和前缀和优化就可以实现 $\mathrm{O}(n^2\log n)$ 的时空复杂度，毫无悬念地通过此题

收获 & 反思

结论运用的很巧妙，好在之前接触过，倒是在复杂度分析那里卡了比较久，相关注意力有待提升

12.19 - 1 - Problem - G - Codeforces

并查集维护边双连通分量

思路

这题的关键是注意到固定三元组中的 $w$ 之后，剩下 $u,v$ 的可选组合是很好求取的