三月份训练手记

3.13 - 1 - Problem - G - Codeforces

思路

因为这个形状要做前缀和或者区间维护比较困难，所以考虑其他做法

不难发现，在总方格数量在一个可以接受的水平时，从以一个格子为顶点的 “区域” 变化到与其相邻的一个格子的 “区域” 只需要去除一段横（或者竖）着的格子，再添加一串斜着的格子即可，在前缀和处理的基础上是可以 $O(1)$ 计算的

于是就考虑暴力计算初始的一部分格点，然后 $O(1)$ 转移

收获 & 反思

对于一些区间组成很奇怪，一眼看过去不好维护的数据范围，可以考虑用范围数据结构维护，也可以考虑重复利用其中的一部分信息，使用转移来快速计算答案

3.13 - 2 - Problem - E - Codeforces

思路

使用动态规划来解决问题

$01$ 串与总 “好子串” 之间的关系是显然的，即只与连续的 $0$ 串的长度有关

考虑记 $dp[i][j]$ 表示已经有了 $i$ 个 “好子串” 且最后一个 “好子串” 的末尾有 $j$ 个零的方案数量

那么转移方程就是：

$$dp[i][j]=\sum _{p+j\le k+1}^{j\times p\le i}dp[i-j\times p][p]$$

收获 & 反思

这道题很明显是一个动态规划问题，转移起来也不复杂，但是难点在于怎么准确分析复杂度

对于每一个 $i$ 来说，在不考虑上限 $k$ 的影响的时候，最多发生的转移次数就是 $\sum _i^n\frac{n}{i}\sim n\log n$

事实上，对于 $k$ 的限制总是比 $n$ 更严格，所以一个更强的复杂度渐进上界是 $\sum _i^n\frac{n}{i}\sim nk\log n$

3.13 - 3 - F - Takahashi in Narrow Road

思路

本题的难点在于每个点只能占一个人

所以我们考虑把每个人脚下的那个点 “藏起来”，使得某种意义上允许格子上站多个人

实现的手段是把每第 $i$ 人的坐标与询问中要他移动到的坐标改为 $x_i-i$ ，这样如果第 $j$ 个人要往前挪动，就必须让他在这基础上多移动 $i-j$ 步，往后移动同理，很巧妙地解决了问题

于是移动就可以化为区间修改操作，统计答案就可以转化为区间求和，用线段树维护即可

收获 & 反思

很巧妙的处理思路，遇到同样具有 “一格一物” 性质的问题可以考虑类似的处理手段

3.14 - 1 - Problem - 865D - Codeforces

思路

采用反悔贪心的策略来解决问题

对于每一天，我们选择在此之前最低价且空闲的一天来买入并且就在这一天卖出，计算收益

反悔的操作基于：

• 在 $a_j$ 这天决定买入 $a_i$ 之后，我们向可选的项中添加一个 $a_j$ 作为 $a_i$ 的反悔选项，如果后续选择了这一个，仍然等价于以 $a_i$ 买入再以新价格卖出（因为 $a_j$ 被抵消了）

特别地，如果此前最低价也比今日价格高，就不做买入操作

同时还要注意，我们还需要再加入一个 $a_j$ 作为这一天的选项（因为之前买入加入的 $a_j$ 实质上是此前另一天的反悔选项，两者不冲突，所以必须一起考虑）

收获 & 反思

反悔贪心，目前还是很不熟悉的算法，做一道就赚一道，做两道就赚两道！

3.14 - 2 - Problem - E - Codeforces

思路

本来用各种树上的策略都试了一遍，发现效果都不好，最后看题解去了

使用 树上启发式合并 来维护每个节点处所有颜色的 “直接子节点” 数量，这样子的时间复杂度是合理的

收获 & 反思

还是没有熟练掌握树上问题，应该意识到 树上启发式合并 是一个简单好用的工具

3.14 - 3 - Problem - D1 - Codeforces

思路

其实有点狗屎这道题

不难意识到，最高位和 $x$ 的最高位相同的时候，是可以一步到位的

进而发现，其实只要 $x$ 在目标的最高位上为 $1$ 就可以

所以，对于最高位和 $x$ 的最高位相同的数，我们可以一步构造

而对于最高位低于 $x$ 次高位的数，则可以先将 $x$ 转化为对应的最大全 $1$ 二进制数，然后一步转化

收获 & 反思

对于构造题，只有多练喵

3.15 - 1 - 天梯赛选拔赛 T2-3

思路

不难发现对于一棵树，也就是 $m=n-1$ 的情况来说，只需要将其中节点按照深度奇偶性分为两组，就一定会有一组满足要求的 $\lceil \frac{k}{2}\rceil$ 个独立点

那么就考虑 $m\ge n$ 的情况，这种情况下，不难注意到，题目的要求其实是等价于找到一个环，如果这个环的体量（节点数）是大于 $k$ 的，那么就可以找到一组满足要求的 $\lceil \frac{k}{2}\rceil$ 个独立点，否则，这个环一定满足要求

但是这里有一个纰漏：环上的独立点之间还可能有边相连，这也好办，我们只要让这个环没有任何的 “子环” 就好了，什么样的环一定没有子环呢：最小的环

于是，我们的任务就变成了寻找最小的环，这是很容易完成的：在 DFS 遍历的过程中储存节点的父亲与其在 DFS 树上的深度，之后我们选择深度差最小的返祖边来生成环就好了

收获 & 反思

非常好树上构造问题，使我的 DFS 旋转

3.18 - 1 - Problem - E - Codeforces

数位 DP 啊，太美妙了

思路

这道题的思路是之前没有见过的，所以在这里详细记录一下：

首先，由于生成的矩阵只有不超过两种数，所以 $a,b$ 中也必然只有不超过两种数，这个正确性是显而易见的

所以接下来按照 $a,b$ 中不同的数的个数来分类讨论对答案的贡献：

1. $a,b$ 中均只有一种数

• 这种情况下， $a,b$ 分别有 $A+1,B+1$ 种选择，所以对答案的贡献是 $(A+1)\times (B+1)$

2. $a,b$ 中有一个包含了两种不同的数，而另一个只有一种数
   • 假如是 $a$ 只有一种数，那么对答案的贡献就是 $(A+1)\times (\genfrac{}{}{0ex}{}{B+1}{2})\times (2^m-2)$
   • 其中 $(2^m-2)$ 意义是这两种数都用上的填满 $b$ 的 $m$ 个空位的不同方案数
   • 同理可得 $b$ 只有一种数时的贡献 $(B+1)\times (\genfrac{}{}{0ex}{}{A+1}{2})\times (2^n-2)$
3. 最后一种，也是最麻烦的一种：$a,b$ 均包含了两种不同的数
   • 假设包含的数分别为 $p_a,q_a$ 与 $p_b,q_b$ ，那么根据题设限制 ，必有 $p_a\oplus p_b=q_a\oplus q_b$ 与 $p_a\oplus q_b=q_a\oplus p_b$ ，其实这两个条件是等价的，即 $p_a\oplus p_b\oplus q_a\oplus q_b=0$
   • 于是我们就要统计符合要求的数对数目
   • 考虑数位 dp，用 $dp[i][j]$ 来表示从高到低填到第 $i$ 位，并且当前对数位限制情况为 $j$ 的方案数量，其中 $j$ 是一个 $[0,15]$ 取值的四位状态压缩量
   • 转移的时候考虑对当前位填 $0,1$ 的情况，再检查是否违反了数位限制，对于合法的填入方法，我们要对于那些原来有数位限制，但填入的数小于原有数位的地方解除数位限制
   • 最后统计答案的时候，因为每一个有序二元组会被统计两次，所以合法方案会被统计 $4$ 次，并且其中还会有 $(A+1)\times (B+1)$ 个方案来自 $p_a=q_a,p_b=q_b$ 需要先减去

收获 & 反思

数位 dp 是很好的东西啊，感觉需要找时间多找几道题做做

3.19 - 1 - Problem - B - Codeforces

思路

其实很容易发现就是用线段树维护区间和，并且实现区间修改

要点在于：

1. 如何找到要求改的区间
   • 可以使用一个 set 维护现有的每个区间，然后使用 set.lower_bound() 查找区间
   • 修改就直接删除原来的区间，插入新的区间
2. 如何用线段树维护等差数列
   • 可以让修改 tag 保存 $0$ 下标处的首项与公差，实现确定一个区间内的等差数列

收获 & 反思

其实就是线段树基本技巧，写一遍找找手感挺好

3.20 - 1 - Problem - F - Codeforces

思路

因为题目有着令人晕头转向的背景，所以考虑转化问题为较自然，较简单的模型

每秒钟的时候，整个地图会向上 “滚动”，所有的地形（终点除外）将会一起移动，我们显然没有办法维护地形的改变，但是不难发现，在大家都可以滚动的条件下，这与我们自身向下移动一格是等价的

于是考虑把问题转化为如下模型：

• 地形不动，每次可以选择
  1. 相对不动，开销为 $1$
  2. 向右一格，同时向下一格，开销为 $1$
  3. 向下两格，开销为 $1$
• 在此基础上发现，操作 1 完全没用，所以接下来的求解过程中不予考虑

这个问题的求解可以靠 BFS 轻松完成，但是最后怎么计算到达终点的最小开销呢？

首先明确以下结论：

• 要到达终点必须先到达倒数第二列的某个格子
• 考虑固定到达倒数第二列的某个格子，那么一定是越早到达越好，不会有 “后效性”，因为最后一列没有障碍物

所以我们只要枚举最小开销的方案经过的倒数第二列的格子，然后根据此时的 “开销” 计算出终点的位置，进而计算出这种情况下的最小开销就可以了

收获 & 反思

原先是考虑用 DP 来写的，但是发现有后效性，在这种开销均为 1 的模型中可以考虑 BFS（开销不为 1 的，有后效性的格点模型也可以考虑最短路算法）

最后对于答案的生成的结论是解出本题的关键，它是一个不那么显然的贪心，再次验证了：“贪心不证明等于耍流氓”

3.20 - 2 - Problem - G - Codeforces

思路

不难发现，凹糟的数量要满足一定要求才能成功组合出要求的链

具体地，这个数量要求是 1 类拼图与 2 类拼图的数量之差不超过 $1$ ，原因如下：

• 递推可知，3、4 类拼图不会改变两端的凹槽形状，而 1、2 类一定会
• 所以可以想象把 3、4 类拼图全部去掉，剩下的一定是 1、2 类拼图的交替结构，结论就显然了

受到上述证明方案存在性的途径的启发，也不难想到统计方案数的方法：

• 1、2 类拼图的摆放方式固定（数量相同的情况下有两种摆放方法），此时方案数就是把 3、4 类拼图嵌入其中的方案数
• 这是经典的组合数学问题：把 $m$ 个等价的物品放入 $n$ 个盒子中，盒子可以为空，不同的方案数有 $(\genfrac{}{}{0ex}{}{n+m-1}{m-1})$ 种

于是就很轻松地做完了

收获 & 反思

组合问题的几种常见解决方法：

• 使用 DP 来解决问题
• （本题）直接观察出结论，化为常见的组合数学模型
• 转化为关联性问题，使用并查集 / 图 / DFS 等来解决

3.21 - 1 - P3295 [SCOI2016] 萌萌哒 - 洛谷

倍增还能这么玩？？？

思路

其实直接读题不难发现题目想要我们干什么：两个子串相同，等价于两个子串上的字符一一对应相同

而等价关系具有传递性，也就是 “结合律”，所以可以考虑使用并查集来维护

但是！直接使用并查集，会让 merge 操作的开销来到无法接受的 $O(n^2)$ 所以要考虑如何优化

这个思路很 nm 巧妙哇！

因为我们复杂度的罪魁祸首是区间长度，区间长度越长，我们要进行的 merge 操作的量也就越多，想一想什么东西可以管上长区间处理呢？

对的！就是二进制分解。

具体地，在这道题中体现为我们使用类似于 “倍增” 的思想，对于长度为 $2^k$ 的子串分别开一组并查集，然后将长子串二进制分解，在不同的并查集上分别进行 merge 操作

最后统计答案的时候，从高到低逐层将 merge 信息 down 下来，显然每层最多只会有 $n$ 次 merge ，所以时间复杂度为可以接受的 $O(n\log n)$

收获 & 反思

对于长区间的处理应该自然联想到二进制分解，多看一些二进制分解与各种数据结构结合的实例

优雅，永不过时喵！

3.21 - 2 - Problem - F - Codeforces

思路

看到题目发现最大的一个特点是地图大小固定为 $7\times 7$ 所以考虑找一些性质

又不难发现，格子之间的影响只通过斜向 “传播”，所以完全可以把所有的格子分成互不影响的两组

观察其中任意一组，发现至多可以用 $4$ 次操作来合法化，所以我们只要找小于四次的操作就好了

直接暴力枚举，然后 check，开销量小于 $({24}^3+{25}^3)\times 7^2<2e6$

收获 & 反思

之前被一道可以暴力完成的题目坑过，之后就知道了，暴力 + 证明 = 合法地耍流氓

3.22 - 1 - Problem - B - Codeforces

思路

首先，你要知道 $manacher$ 算法

然后，你要注意到 $k=1$ 一定成立

再然后，你要注意到 $k$ 为奇数的时候，要求奇数位与偶数位上分别相同，$k$ 为偶数的时候，要求全部相同

最后，随便拿个什么东西维护这个性质

收获 & 反思

学习了 $manacher$ 相当的厉害啊（赞赏）

3.24 - 1 - Problem - D - Codeforces

怎么又是超级钢琴

思路

首先知道这又是一个求 $K-th$ 的问题 ，不难发现题目的限制就是如果你选择了 $[l,r]$ 这个区间，那么你的前一个区间的尾部只能小于等于 $l-1$

这道题要求出所有的前 $K-th$ 其实提示就比较明显了，需要使用超级钢琴的 $Trick$ 来解决：

• 定义 $dp[i][j]$ 为左后一个区间末尾不大于 $i$ 的方案中，第 $j$ 大的方案
• 于是 $dp[i][j]$ 的转移就会变为：
  • 将枚举以 $i$ 结尾的区间 $[p,i]$ （需要考虑空区间）
  • 然后，首先将 $dp[p-2][1]+val[p][i]$ 加入 set 并且记录当前取到的位置
  • 每次从堆中取出最大的，然后将对应的，次大的方案加入堆
• 最后统计答案即可

收获 & 反思

其实就是超级钢琴裸题，但是带上了 DP 式的转移，给自己蠢飞了

3.25 - 1 - Problem - C1 - Codeforces

其实没有那么可怕

思路

因为 $k=0$ 所以不用考虑 “假钥匙”

一开始的时候所有的要是都是等价的，所以任选一把没有区别

而之后如果有钥匙被 “试错” 过，那么它打开新的一个箱子的概率一定更高，所以一定选他

于是所有人的策略就是逮着一只钥匙试

又知道一个很常见的概率结论：不放回的抽取 $n$ 个物品中一个特殊物品，第 $i$ 次抽出的概率是 $\frac{1}{n}$

于是我们就可以设 $dp[i][j]$ 为第 $i$ 个打开的箱子是由 $j$ 号选手打开的概率，然后在转移的时候枚举前一个打开箱子的选手，再结合这是第几次开箱与两人之间的位置差，来统计这种转移的概率

收获 & 反思

对于 DP 的优化技巧，改变内层的转化方案，把可以统一计算的部分放在一起减小开销

3.25 - 2 - Problem - G - Codeforces

思路

很简单的题目，考虑转化为新的图像

将每个站点与他们相连的地铁（也作为一个节点）连一条长度为一的无向边，那么在一个地铁线路中移动开销就是 $2$，于是就有答案是最短路的一半

收获 & 反思

常见建模吧，没什么好说的

3.25 - 3 - Problem - H2 - Codeforces

思路

其实这道题挺麻烦的

考虑在某个点操作的时候，怎样的点会产生贡献：所在的连通块的边缘（包含外围一圈）的坐标范围包含当前点坐标的

换而言之，这样的一个连通块会对所在一纵块与所在一行块产生与其大小相同的影响，但还要注意：

• 不要重复统计影响
• 记得排除所在行与所在列本来就有的
• 上一条中，也不要重复统计

所以使用二维差分数组实现区间修改，最后遍历一遍取出最值即可

收获 & 反思

其实没什么难度，就是实现麻烦了一些，还有就是记得差分可以维护区间修改

3.26 - 1 - Problem - D2 - Codeforces

思路

这个问题最关键的两个步骤就是建模和转移

首先需要发现，不管对于什么样的串，最佳的解决方案都是使用一个 $1$ 来 “搞定” 周围三个位置的需求

所以我们需要做的就是搞清楚最少可以用多少个长度为 $3$ 的区间把串上的所有 $1$ 完全覆盖

这个问题我们可以用 DP 来解决：

• 设 $dp[i]$ 是以 $i$ 为左端点的所有区间的答案总和
• 如果 $i$ 位置是 $0$ ，显然这个位置可以没有任何区间覆盖，所以 $dp[i]=dp[i+1]$
• 对应的，如果 $i$ 位置是 $1$ ，那么一定要有一个区间覆盖这个位置，容易推出这个区间为 $[i,i+2]$ 一定最优，所以 $dp[i]=dp[i+3]+(n-i+1)$

就做完了

收获 & 反思

主要是在建模上卡了很久，按理来说不应该，蠢死我得了

3.27 - 1 - Problem - E - Codeforces

思路

首先不难发现，由于操作的性质，使得最优的状态一定可以在一轮操作内达成

同时有，一个位置能否达成最优状态仅仅依赖其 $\pm 2$ 位置上的数值，所以就有以下 $O(n)$ 的解决方案：

• 如果区间长度 $<4$ ，我们就暴力判断
• 否则，我们认为除了头尾各两个位置外的状态就是最佳状态，然后对头尾特判

收获 & 反思

还是性质题啊，需要惊人的注意力

3.27 - 2 - Problem - D - Codeforces

思路

根据括号序列的性质，我们可以转化为前缀和来做，每次统计前缀和为 $x$ 的位置的数量，在每次遇到 $x$ 的时候统计配对数

但是有一点需要注意，配对的两个位置中间不能有 $\ge 2x+1$ 的数值，否则会导致某一处的右括号失配，所以每次经过 $2x+1$ 的时候将统计的 $x$ 位置的数量清零

收获 & 反思

还是常见结论 & 建模，没什么好说的

3.28 - 1 - Problem - E - Codeforces

思路

还是树上问题，还是没想清楚，怎么回事呢

不难发现，如果要求要成一条链，就要满足以下两个模式之一：

1. 只有一个黑点的父节点是白点（或无父结点，可以使用 $0$ 节点来作为辅助根节点避免特判）并且所有点至多有一个黑儿子
2. 只有一个黑点的父节点是白点，有且仅有这个黑点有两个黑儿子，其他所有点至多有一个黑儿子

所以我们就可以维护节点黑儿子的数量，与父亲是白点的黑点数量，这里需要一些维护技巧

收获 & 反思

树上问题还是不很熟练

常见的维护都是通过父亲来进行的，因为每个节点的父亲是唯一的，而儿子可能有非常多，导致复杂度爆炸

但是也可以维护 “特殊的儿子” 数量，这样的修改也是 $O(1)$ 的，并且还可以利用这个维护量来辅助其他信息的快速维护

值得再看一遍

3.28 - 2 - Problem - B - Codeforces

思路

这个其实有点实现起来有点一坨，但是思路还是很有价值的

首先不难发现，让我们转弯的是位于起点及其左边的 "<" 与起点及其右边的 ">"

所以，我们可以通过前缀和判断这两种字符的数量，再结合起点类型，判断出最后会从哪边出去

然后就是计算步数，不难发现在去掉 “在 <> 之间来回” 的步数后，就是起点直接到出口方向的步数

于是我们可以创建不同字符的索引，再对索引与其下标做前缀和，快速统计区间和，两种字符的区间和相减，就是最难计算的 “在 <> 之间来回” 的步数了

收获 & 反思

常见建模，需要细心考虑边界情况，以及计算方案的正确性

3.29 - 1 - Problem - 1667C - Codeforces

思路

考虑必要条件，至少需要 $ans=\lceil \frac{2n-1}{3}\rceil$ 个棋子

然后再考虑充分性，也就是要在左上角 $ans\times ans$ 的区域内放置棋子，覆盖每一行每一列和每一条空闲斜线

这个构造有很多种方法，都不算很难，故不展开说明

收获 & 反思

构造题的经典考虑方向之，必要条件恰好能完成构造，那就是充要条件

3.30 - 1 - Problem - D - Codeforces

思路

不难发现其实就是找 $[\lceil \frac{A}{G}\rceil ,\lfloor \frac{B}{G}\rfloor ]$ 上距离最远的一对互素的数

接下来证明若有解，一定在 $[l,l+15],[r-15,r]$ 上可取得一组解：

• 首先在 $[l,l+15]$ 上必有一个数与 $2\times 3\times 5\times 7=210$ 互素（打表验证）
• 然后在最坏情况下，这个数最多具有 $12$ 个素因子： $11,13,17,\dots ,53$
• 再在最坏情况下，这些素因子的倍数在另一个区间的分布情况是：
  • $11,13$ 的倍数各两个
  • 其余数的倍数各一个
  • 共计 $14$ 个
• 所以必有一对数互素

有了这个结论，我们就可以只遍历左右各 $15$ 个数来求解了

收获 & 反思

这道题的解决方法很简单，但是证明的结论与其思路非常巧妙，有学习价值

3.30 - 2 - 学习了 BSGS