十一月份训练手记

11.12 - 1 - Problem - F - Codeforces

思路

神秘的树上最优化，首先不难想到把两点之间路径上的边权异或和转化为两点到任何一点（子树根）的路径异或和的异或和，然后原来的边权限制就转成了对 “点权之间的异或和” 的限制，可以轻松使用带权并查集维护并检查是否合法

处理完全部限制之后，考虑怎么处理这个最小化的要求：

• 注意到一个点权对答案的贡献次数等同于这个点在原树上的度数
• 也就是说，我把并查集上在原树中总度数为奇数的一个连通分量全部异或上一个数 $x$，依然是合法的构造，但是答案会被相应地也异或上 $x$
• 所以我们先随意构造，计算现在的答案 $ans$ ，然后寻找任意一个满足上一条的连通分量全部异或上 $ans$ 就能让答案取最小值为零，若找不到则这是唯一答案

一个小思考

为什么我们可以不在乎 “根节点到自身的路径上权值和为零” 这一条件

• 因为选择任意节点为根，就可以把全局异或上当前它的值，不改变任何边权，也就不改变答案

收获 & 反思

做的时候在后面最小值的构造上卡了很久，应该多注意到形如这题奇偶性对贡献的影响的关系

11.12 - 2 - Problem - E - Codeforces

思路

理解完题意发现就是简单的数论分块

对 $\lfloor \frac{s_n}{x}\rfloor$ 和 $\lceil \frac{s_n}{x}\rceil$ 做数论分块，设 $k=\lfloor \frac{s_n}{x}\rfloor$，并分类讨论

• 若二者相等，那么取 k 的倍数计算贡献，总复杂度为调和级数
• 若不相等，那么枚举 $j(j<k)$ 对 $[jk,jk+j]$ 以及 $[k^2,+\mathrm{\infty }]$ 上的数计算贡献

收获 & 反思

没什么的，就简单二维数论分块

11.13 - 1 - Problem - F - Codeforces

思路

还是有点难想的，要求等价于最小化初始排列的环的数量，我们先考虑这个排列是怎么变换的：

以这样一个简单的五元环来演示：

$$23451$$

我们不难发现，数字 $x$ 会将当前排列中第 $x$ 位的元素在下一时刻 “拉至” 他现在的位置，我们用箭头来表示一下这个关系：

$$5\to 4\to 3\to 2\to 1\to 5$$

而我们也不难意识到，假如数字 $x$ 将数字 $y$ “拉” 了过来，那么下一时刻，数字 $x$ 就应该对应上一时刻第 $y$ 位的元素 $z$ ，换而言之，就是数字 $x$ 的箭头跨过 $y$ 指向了 $z$ 。所以至此我们可以归纳出，每一时刻的变换相当于箭头 “跨越” 一次，也就是连着 $k$ 次变换就相当于每个数的箭头在环上跨越了 $2^k$ 位。

同时不难发现，我们可以靠这个环来还原出这些元素的位置（每个元素的位置就是它的后继元素）

所以说，对于偶数环，会在下一时刻分裂成两半，而对于奇数环，则不会再分裂

由此可知，经过 $k$ 次分裂之后，如果是偶数环，那么一定是连续分裂了 $k$ 次，也就是每 $2^k$ 个环合并为一组，而对于奇数环，则可以任选 $2^q(q\le k)$ 个环合并为一组，而合并的操作很简单，因为每次分裂是分离相邻的元素，那么 $2^q$ 个环合并后就是先按顺序插入每个环的第 $1$ 个元素，然后第 $2$ 个...... 以此类推

那现在判断合法性和答案很显然了，尽可能把更多的环融合为一个环，那还有一个需要解决的问题就是，对于奇数环我们该怎么求其前一时刻的状态？

• 不难意识到对于长度为 $2n-1$ 的奇数环，在下一时刻每 “走一步” 相当于在上一时刻走了两步，那么只需要走 $n$ 步就可以相当于在上一时刻走了 $2n=1\mathrm{mod}2n-1$ 步
• 所以要求前 $k$ 时刻的奇数环，只需要在环上走 $n^k$ 步就可以了

实现上是一坨大粪

收获 & 反思

在处理排列变换相关操作的时候要注意环上的性质，并且尽可能依赖操作的可复合性质，利用快速幂 / 倍增一类的算法来高效求解

11.15 - 1 - Problem - F - Codeforces

思路

不难发现答案具有单调性，也就是说如果能走 $m$ 步，那么一定能走 $m^{\prime }\le m$ 步，于是我们考虑二分答案

对于一个可能的答案 $m$ 我们可以这样去 check：

• 做一遍 DFS 我们考虑这一次我们走的一条链是向上的还是向下的
• 分析可知，向下走一定不会更劣，因为按照 DFS 的顺序，向下走不会影响挤占其他点的答案
• 而当向下没法达到要求时，就一定要向上走，如果某一结点有多于一个节点要向上走，那么整个答案无解

收获 & 反思

意识到单调性不难，但是需要注意到可以利用向下走这一操作的 “无后效性” 来高效 Check

11.16 - 1 - Problem - E - Codeforces

思路

题意很简单，就是问我们在补充一个距离数据之后，树上以哪些节点为根时，与给出的 深度 - 节点数量 信息匹配

这不难想到要用树哈希来解决，问题变为如何高效求解每一个节点作为根的时候的哈希值

一个方法是利用换根 DP：

• 第一次的时候可以跑出 $downHash[i]$ 表示某一结点及其子树的哈希值

• 第二次可以用父节点的总哈希值，减去自身哈希值乘 $Base$ 后再乘 $Base$ 来获取向上部分的哈希值 $upHash[i]$，也就是

  $$upHash[i]=(upHash[fa[i]]+downHash[fa[i]]-downHash[i]\cdot Base)\cdot Base$$

• 由此可以通过两次 DFS 求出全体节点的 $Hash$ 值，再和所有 $n$ 种补充方式的哈希值匹配即可

收获 & 反思

小心哈希生日攻击，最后哈希值域开到了 $1e13$ 才通过，下次分析完最好选择双模哈希

11.17 - 1 - Problem - E - Codeforces

思路

一个简单的 DFS 转移 + 复杂度分析

不难发现题目等效于对于 $m$ 的每一个因子 $d$ ，要找 $d$ 的一个不超过 $n$ 的最大的因子 $d^{\prime }$ ，如果 $d/d^{\prime }\ge n$ 则无解，否则答案就是 $d/d^{\prime }$

那我们要怎么找这样的一个 $d^{\prime }$ 呢？

不难发现如果 $d$ 本身就比 $n$ 小，那么 $d^{\prime }=d$ ，否则我们可以枚举 $d$ 的因子中最大的 $d^{\prime }$ 作为答案，这里的枚举可以只枚举 $d$ 除以他的一个素因子获得的因子（显然可以完全覆盖可取的情况，且再除下去不会更优）

于是时间复杂度就是 $\mathrm{d}(\mathrm{m})\cdot \mathrm{m}\text{的素因子个数}$ ，可以接受

收获 & 反思

简单的枚举转移 + 复杂度分析

11.18 - 1 - Problem - D - Codeforces

思路

很神秘的一道题，很考察对题目的转化与分析能力

首先意识到这等价于一个二分图匹配 —— 首先复制一列出来，每个元素可以向自己前面满足要求的元素匹配，匹配数越大，最后的链数越小

于是不难发现，我们可以贪心的去做一个匹配，操作和证明如下:

• 首先不难发现，我们需要优先用 $1$ 去匹配 $2$ ，因为 $1$ 只能供 $2$ 匹配，而优先使用 $3$ 去匹配 $2$ 的话，就可能会浪费 $1$ 而使若干原本能用 $3$ 匹配的 $4$ 失配（也就是贪心地先匹配条件紧的），以此类推，我们从小到大枚举，对每一个数 $a$ 都优先使用 $a-1$ 去匹配（当然从大到小枚举优先使用 $a+1$ 同理，也是对的）
• 然后需要注意的一点是，对于同种元素，我们需要从前往后枚举，这和上一条遵循的原理是一样的：我们优先匹配条件紧张的，而不会浪费条件宽裕的。同种元素中显然越靠前的元素匹配条件越紧张（若不这样做，可能在与 $a-1$ 匹配的时候就浪费了一些条件宽裕的元素，从而使得部分原本能与 $a+1$ 匹配的 $a$ 最后失配）

知道了做法，实现就很简单，每个元素用 set 存一下位置信息，需要的时候 lower_bound 找到对应位置匹配再维护 set 即可

收获 & 反思

对贪心结论的利用不够熟练，看到题目情境无法快速反应这是典型的贪心模型

11.19 - 1 - Problem - G - Codeforces

思路

没什么好说的，很简单的 BFS

注意到需要有一个代币只经过 Bonus 和 1 号节点到达 1 号节点，同时其他代币需要在中间进行至少 $dis-1$ 次移动，于是我们统计每个节点到 1 号节点的最短路径（只经过 Bonus 和 1 号），以及他们能在不作为抵达终点的代币时能提供的最多步数。

不难发现一旦能抵达某两个联通的 Bonus 就可以无限刷步数，反之只能提供 1 步（直接走到独立的 Bonus 上）或者 0 步（没有相邻 Bonus），于是问题得解

收获 & 反思

简单题，不说话装高手

11.20 - 1 - Problem - D - Codeforces

思路

不难发现我们可以通过不断地使用 $A$ 最左侧的第一个 $1$ 纠正最左侧的不同的位来逐渐矫正原数

但是同时存在一个问题，就是最左侧 $1$ 无法矫正自己，也无法保证在矫正比自己更靠左的错位时自己不受影响，也就是说，最好的情况就是 $A$ 最左侧的 $1$ 正好对应 $B$ 的最左侧的 $1$

那就一步就是，我们可以利用 $A$ 最右侧的 $1$ 来从右到左清理掉比 $B$ 最左侧的 $1$ 还要靠左的 $A$ 中的 $1$ ，然后再在 $B$ 最左侧的 $1$ 对应的位置上造出一个 $1$ 来

但又有新的问题，如果 $A$ 最右侧的 $1$ 也在 $B$ 最左侧的 $1$ 的左边呢？很简单，先在 $B$ 最左侧的 $1$ 对应的位置上造出一个 $1$ 来就行了。

收获 & 反思

简单题，不说话装高手 a BVN

11.21 - 1 - Problem - E - Codeforces

思路

我们先考虑固定根节点的情况，结论是显然的：

• 同一种颜色必须是一条直上直下的链
• 在父结点处，选择所有儿子中链长最短的，染上对应颜色 “接续”
• 同时记录其他没有被接续的链的最短长度（以下称为 “断链”）
• 答案就是 根节点所在链长 和 所有断链的最小长度 的最小值

那现在考虑对于根节点任选的情况，不难意识到这要求我们做一个换根 DP，考虑怎么转移根节点信息：

• 我们要维护根节点所在链长和所有断链的最小长度，可以在第一次 DFS 时跑出 $u$ 子树内的断链的最小链长记作 $g[u]$ 和 $u$ 子树意义下 $u$ 节点对应的链长记作 $len[u]$ ，考虑从 $u$ 到 $v$ 换根的时候，$v$ 是否为 $u$ 做出贡献：
  • 如果 $u$ 所在链来自 $v$ 所在子树，那么换根之后 $u$ 就要选择次短链来 “接续”，同理此时 $u$ 自身中的最短断链来自原来 $u$ 的再次短链和 $u$ 的非 $v$ 子树贡献的最短断链取 $min$（这里注意选取的是的是非 $v$ 子树贡献的断链而不是 $u$ 下的所有断链中的次短断链，因为这个次短断链有可能也来自 $v$ 子树）
  • 否则的话，那么换根之后 $u$ “接续” 的最短链不变，同理此时 $u$ 自身中的最短断链来自原来 $u$ 的次短链和 $u$ 的非 $v$ 子树贡献的最短断链取 $min$
• 由此可知，我们在换根的全过程维护节点连接的最短、次短和在次短链，以及节点为根时的最短断链和非最短断链所在子树贡献的最短断链即可，每个点为根的答案就是 $min(len[u],g[u])$ ，对这个取最大值即可

收获 & 反思

理解换根 DP 的本质，知道应该取什么为 “次小值”，才能正确转移。

11.24 - 1 - Problem - F - Codeforces

爵士神秘题目

思路

这个题的核心结论是 Erdős-Ginzburg-Ziv 定理：对于任意 $2n-1$ 个整数，总可以从中选出 $n$ 个整数使它们的和为 $n$ 的倍数。

证明

引理一：对于任意的 $n,m$，若定理成立，则其也对 $nm$ 成立。

对于 $2nm-1$ 个数，先取出 $n-1$ 个数，此时还剩 $(2m-1)n$ 个数。重复 $2m-1$ 次以下过程：每次加入 $n$ 个数，在 $2n-1$ 个数中取出 $n$ 个数使其和是 $n$ 的倍数。最后会得到 $2m-1$ 组数，每组 $n$ 个，且每组的和为 $n$ 的倍数，取出 $m$ 组使和为 $m$ 的倍数即可。

引理二：定理对所有质数成立。

当众数出现大于等于 $n$ 次，取出 $n$ 个众数即可。

否则，可以将数划分为 $n-1$ 对和一个单独的数，每一对中的数不相同。这个排序后第 $i$ 个和第 $n-i+1$ 个配对即可。先选上每对一个和单独的数，设和模 $n$ 余 $r$，此时相当于有 $n-1$ 个模 $n$ 非 $0$ 的数，分别为每对中选的数和未选数的差，要用这些数凑出任意一个模 $n$ 余 $r$。

考虑构造出一颗树，编号 $0\sim n-1$，边权是这 $n-1$ 个数，且 $0$ 号节点到 $i$ 号节点的距离模 $n$ 为 $i$，最后节点 $r$ 到根的路径即为所求。

考虑从根节点不断扩展，按顺序连边，每次连接树内一点和树外一点，则一定能构造出一种合法方案。假设当前边无法连接，设边权为 $w$，因为 $0$ 在树中，所以 $w$ 在树中。类似地，$2wmodn,3wmodn,\dots ,kwmodn$ 在树中。因为 $n$ 是质数，所以 $kwmodn$ 遍历所有点，此时所有点都已加入树中。

然后就不难发现我们可以将班级的体量从小到大排序，这样每次考虑最小的一个班级，剩余的礼盒数量一定大于 $2s_i-1$ 个，所以一定有解，我们只需要逐一跑背包构造方案即可，最后剩下的那一个班级，可以用额外的礼盒来调节总数，主体是背包，时间复杂度 $\mathrm{O}(n^3)$

收获 & 反思

神秘结论题，但是这个结论很好玩，找时间改成自己的神秘题目好了

以及，这个题是有 $\mathrm{O}(n\log n)$ 的做法的，具体来说就是按照上面对于引理的证明过程来代替背包完成构造，前半部分需要质因数分解 + 分组递归，最后对质数的构造是最关键的：

• 对于一组物品我们要快速构造的关键就是每一步要快速找到一个 $k$ 使得 $kwmodn$ 在树中而 $(k+1)wmodn$ 不在，我们可以考虑二分，先随便找一个 $k$ 使 $kwmodn$ 不在树中作为二分右边界，这可以随便找一个不在树中的点 $q$，$k=q{w}^{-1}modn$。虽然没有单调性，但在二分过程中可以始终保持左端点在树中，右端点不在树中，最终必能找到合法点。$\mathrm{O}(n\log n)$。

很神秘的二分，也值得学习

11.26 - 1 - Problem - 1340F - Codeforces

*3300 首杀祭

思路

其实就是考虑线段树维护哈希，从题意出发，我们逐一考虑线段树需要维护什么信息，以及如何维护：

• 首先我们发现如果紧挨着的一对左右括号类型不同，则永远无法消去，这个时候我们可以对这个区间打上非法标记，由这个区间合并而来的区间均为非法区间

• 由上一条性质不难发现，一个可能的合法区间只可能由一个右括号串前缀和一个左括号串后缀组成，并且在合并的过程中检查中间的串是否可以匹配，并且维护匹配后剩余部分的哈希

• 也就是说，若左子区间的左括号后缀长度比右子区间的右括号前缀更长（或相等），那么我们需要取出左子区间的左括号后缀的一个长度匹配的后缀的哈希值来检查是否匹配，若更短则取右子区间的对应前缀。但问题是，我们维护的是整个剩余串的哈希，无法从中获取前后缀的哈希，又因为只要求一边的，所以我们考虑单侧递归来获取：

  • 以获取某区间左侧右括号长度为 $len$ 的前缀为例
  • 如果 $len$ 为 $0$ 或等于右括号串长度，就直接返回答案
  • 否则检查该区间左子区间的右括号前缀长度 $le{n}_1$ ，由于这个前缀是严格不减的，所以如果 $len\le le{n}_1$，我们可以递归到左子区间获取长度为 $len$ 的前缀
  • 如果 $len>le{n}_1$ 那么，我们需要的这个前缀就由左子区间的整个前缀与右子区间被左子区间右侧的左括号匹配后剩下部分的前缀拼成。具体来说，设左子区间的左括号后缀长度为 $le{n}_2$ ，就需要递归到右子区间求取 $len-le{n}_1+le{n}_2$ 长度的前缀，然后减去左子区间的左括号后缀（哈希策略相同的话，这一段等价于被匹配的那一段右括号前缀），再与左子区间的整个前缀拼起来
  • 所以每个节点的更新需要 $\log n$ 次递归，一次修改需要更新 $\log n$ 个节点，故一次修改的时间复杂度为 $\mathrm{O}({\log }^{2}n)$

  接下来考虑查询，由于查询的时候同样需要合并区间，向下递归，但查询时合并区间的树结构并不存在于原本维护的树上，所以实现起来较为复杂，但我们注意到在按顺序合并的时候，任一时刻都不能存在左侧的右括号，所以我们可以建一个序列只存每步合并后的左括号哈希数据，而递归的时候就可以直接递归到前一步合并后的子区间（向左子区间递归）或回到树结构里（向右子区间递归），可以建立深度不超过 $\log n$ 的简易临时合并树结构，查询时间复杂度同样是 $\mathrm{O}({\log }^{2}n)$ 。

收获 & 反思

为了熟悉单侧递归线段树来练的这道题，写完之后也确实对于单侧递归与字符串哈希有了更深刻的理解：

• 单侧递归的核心是数据维护不仅仅需要子区间信息，还需要获取更细化的信息，并且这些信息可以被递归求取，一般来说单侧递归线段树并不在递归求取信息的时候做修改
• 信息可以被递归求取通常意味着左子树和右子树的信息可以只求其一，而另一边在这个时候则可能：不产生贡献 / 贡献可以被快速计算（譬如前缀最大值被 “推平”） / 贡献直接就是该子树上维护的值（譬如这道题的前缀区间）

11.27 - 1 - Problem - E - Codeforces

思路

看到 “对于 $i=1,2,3\dots$ ” 就很自然地想到了动态规划

然后就考虑要维护什么信息，怎么维护，怎么获取答案

首先注意到，修改次数不会超过两次，最差情况就是把头部改为 $1$ 然后把后面构造成一整段

还有就是，我们可以维护直接按 test 区间 “跳” 的情况：是否能恰好跳到底，以及能跳多少个测试区间，这样我们就可以判断是否需要修改：

• 对能恰好跳到底的，如果区间个数与要求一致，则不用修改，否则只需要修改一次要求的区间个数即可
• 对于不能恰好跳到底的，我们需要判断是否能在一次修改内合法化，显然不能修改头部，因为这样至少需要两次修改，那我们只需要考虑它能在一次修改后变出多少个区间：
  • 一个显然的结论是：如果能变出 $k$ 个区间，那么一定可以变出任何比 $k$ 来的少的区间（$0$ 不考虑，因为原数组为正整数）
  • 所以我们要维护 $dp[i]$ 表示 “以第 $i$ 个元素开始的后缀在一次修改内能获取的最大后缀数”
  • 考虑怎么转移，有两种情况：
    • 一是在第一个区间就做了修改，这要求从下一个区间开始要能恰好跳到底，所以我们只需要维护此前能直接跳到底的后缀所包含的最大区间数即可
    • 二是第一次不修改，后面再修改，这要求第一个区间不能跳出序列，且答案就是第二个区间开头对应的 $dp$ 值

至此此题得解

收获 & 反思

简单的 $dp$ ，能考虑清楚所有情况即可

11.28 - 1 - P7521 [省选联考 2021 B 卷] 取模 - 洛谷

思路

很巧妙的观察性质题

我们先考虑如果固定了模数 $m$ 我们可以怎么做，一个很显然的做法就是，把剩余所有数对这个模数取模后排序，分类讨论：

• 如果两个数之和大于 $m$ ，那么我们之间考虑去最大的两个数
• 否则，我们可以用双指针（或者图方便就 set 加 lower_bound ）来快速匹配
• 时间复杂度 $\mathrm{O}(n\log n)$

然而，对于每个数都这么做显然会使时间复杂度爆炸，我们考虑加入一个简单的贪心优化：

• 从大到小枚举这个 $m$ ，假设目前已知的最优答案为 $ans$ ，那么当 $ans\ge m$ 的时候就可以停止枚举了

加入这个贪心优化之后，其实就可以过了，但是，这是为什么呢？

接下来我们考虑证明：

• 假设最终的最优答案为 $an{s}_{final}$ ，那么我们就只会遍历比这个 $an{s}_{final}$ 大的元素 $a_i,a_{i+1},\dots ,a_n$
• 再由 $ans$ 是最优答案可知 $a_i+a_{i+1}\le a_{i+2}+an{s}_{final}$
• 变形得到 ($a_i-an{s}_{final})+(a_{i+1}-an{s}_{final})\le (a_{i+2}-an{s}_{final})$ ，也就是 $a_i-an{s}_{final}$ 呈指数级增长，故元素数量级为 $\log \mathrm{V}$

故总体时间复杂度为 $\mathrm{O}(n\log n\log V)$

收获 & 反思

做法很简单，但是这个复杂度分析真的蛮难想的，可能手玩久一点能发现？

11.29 - 1 - U633827 世界的意义 - 洛谷

同样的数据结构大份

思路

首先受到 CF 1340F 的启发，发现在成功匹配所有能够匹配的括号对之后，只会剩下一个右括号前缀和一个左括号后缀，故考虑使用线段树单侧递归来解决这个问题

不难发现我们把已经合并（消去）了的括号序列当作两个未匹配括号（或左右边界）之间的 “空隙” 的话，答案等价于求这个区间里的最大 “空隙” 大小，又注意到随着每次合并只会有中间的括号进行匹配，且这个空隙大小只增不减，所以我们只要维护这个合并产生的新 “空隙” 大小即可维护和求取答案

那我们接下来看看合并的时候具体要怎么维护：

• 首先我们需要记录每个区间的右括号前缀和左括号后缀的长度（包括空隙），而中间的空隙长度就是区间长度减去前后缀
• 再次我们需要统计前后缀包含的左右括号数量，以便知道匹配情况：
  • 当左子区间左括号数量等于右子区间右括号数量的时候，新区间直接继承左子区间的前缀长度和右子区间的后缀长度，中间空隙就是新区间总长减去前后缀长度
  • 否则一定会有且仅有一边完全用尽前/后缀，贡献可以直接计算，而另一边只取部分前/后缀出来用于中间的匹配，而另这个时候我们就需要将这一段的带空隙总长求出，以左子区间的左括号后缀数量大于右子区间的右括号前缀数量 $len$ 为例，我们要取出左子区间长度为 $len$ 的左括号后缀的长度，考虑到合并的时候前后缀的括号数量是只增不减的，所以：
    • 如果左子区间的左子区间的左括号后缀数量小于 $len$ ，则长度全由其贡献，直接向此内递归
    • 否则左子区间的整个左子区间都包含在长度内，设其包含 $le{n}_1$ 个右括号与 $le{n}_2$ 个左括号，所以我们将再向左子区间的右子区间递归取 $len-le{n}_2+le{n}_1$ 大小的后缀长度
  • 左子区间的左括号后缀数量小于右子区间的右括号前缀数量同理可求
• 每次维护前后缀长度和括号数量，并且将答案与合并出的空隙大小取最值即可
• 维护一个 merge 的开销是 $\log n$ 级别的，线段树深度也为 $\log n$ ，所以单次修改的开销就是 ${\log }^{2}n$

那我们再看看求取答案的时候，其实可以视作至多 $\log n$ 个区间顺次合并并维护答案，所以我们可以按合并顺序建一个临时的树结构并逐层合并，单次查询的开销也是 ${\log }^{2}n$

至此我们可以在 $\mathrm{O}(n\log n+q{\log }^{2}n)$ 的时间复杂度内完成这道题

收获 & 反思

提升了熟练度吧，这种东西细节还是不少的，也对于单侧递归解决括号序列相关问题积累了经验

11.29 - 2 - Problem - C - Codeforces

思路

我们考虑两个区间相交或嵌套意味着什么要求：

• 对于区间相交，从中间相交部分必须保证匹配后没有剩余左右括号（否则至少会影响一侧区间）可知这等价于交出的三个区间分别要是括号序列
• 对于区间嵌套，由 (A) 是合法括号序列可知，这相当于外层括号序列中插入一个括号序列，不互相影响

所以我们相当于要求出最后总共有多少个要求的区间，对这些区间求取括号序列数（卡特兰数）再乘算得到结果，若其中某一括号序列长度为奇数则无解，这个区间划分本来觉得还挺麻烦的，但是意识到可以用异或哈希去做一个 “区间覆盖情况” 的标记，就方便很多了，标记相同的需要是一个括号序列

收获 & 反思

这个题的关键就在于异或哈希来做 “区间染色”，这其实在树上和括号序列背景的题目里相当好用和常见，需要注意应用

11.30- 1 - Problem - G - Codeforces

初见树哈希

思路

给出了根节点其实就好做很多了（其实不给也能做，换个根的事情）

看到这种判断树结构的题目，就很自然地想到可以用树哈希来做，于是光速去学了一下，发现比想象中的简单很多

于是我们就有了判断两个子树是否结构相同的手段，考虑如何判断 “对称” 呢：

• 答案很显然，使用异或，因为对称（相同）的两个子树的哈希值会被抵消，这样就可以判断是否完全两两同构（偶数个子树），或找出剩下的那个子树（哈希值等于子树集的异或和）并判断它的对称性（奇数个子树）

至此就做完了

收获 & 反思

树哈希 & 异或哈希裸题，反应不出来就该艾草了

11.30 - 2 - Problem - E - Codeforces

思路

想法很显然也很好证明，就是去构造一个内向基环树（或环退化为一个点），其中树高均不能大于 $1$ ，不难想到去枚举组成这个环的集合然后分析可行性，结果就发现卡住了：不会高效判断是否成环

那接下来就往这个方向想，子集 dp 的常见做法是枚举一个序列，所以不难想到去固定环的起点并把环断成链，维护其所有可能的末端的后继，然后考察是否存在这样一条链使得链尾可以连向起点。这个东西怎么转移呢？也很简单，既然固定了起点（为了方便和统一，设集合里的最小元素为起点）那我们就枚举最后一个被加入的节点，也就是枚举缺失某一非起点元素的集合并考察是否能连向缺少的那一个元素，如果可以，那这个元素就可以作为链尾，其连边就可以作为链尾的后继，而对于一个能成环的集合，我们只需要枚举不在集合里的元素能否直接连向集合内的元素就可以检查合法性，一旦发现一个合法的集合，就可以递归构造方案，若遍历所有集合均没有合法的集合，就可判断无解

收获 & 反思

还是子集 dp ，还是熟练度不够，没有考虑到状态（所有可能的链尾后继）也可以被状压，没有考虑到可以固定起点以减少一个维度的 dp 变量

11.30 - 3 - Problem - E - Codeforces

思路

不难意识到任何两个填充单元格之间横平竖直的路径上不能有空白的单元格，所以我们先全部填涂一遍

如果这个时候两个城市已经合并了，那么这就是最优解

否则不难发现两个城市一定不会同时出现在某一行或一列上，我们要求连接一条通路，则一定会经过他们中间的那部分，那么两个城市朝向对方的那一角就需要被填满，否则就会存在单元格与路径之间留有空白单元格（容易证明）

于是就开始愉快（痛苦）的分类讨论和小模拟

收获 & 反思

没什么好说的，观察性质加简单的证明