2022-01-07~¶
CF1620F¶
题意¶
给定一个排列 \(a_1,a_2,\ldots,a_n\)，构造一个方案，将一些位置上的数变为相反数，设新得到的序列为 \(b_1,b_2,\ldots,b_n\)，满足下面的图为二分图：
- 边 \((i,j)\) 存在当且仅当 \(i<j\) 且 \(b_i > b_j\)。
(\(1 \le n \le 10^6\))
题解¶
结论：这样的图是二分图 \(\Leftrightarrow\) 不存在长度为 \(3\) 的下降子序列。
\(\Rightarrow\)：若存在子序列 \(b_i,b_j,b_k\) (\(i<j<k\)) 递减，则这是一个三元环，该图不是二分图。
\(\Leftarrow\)：只需证不存在大于 \(3\) 的奇环，若有这样的环，和环上一个点 \(i\) 相连的两个点 \(j,k\) 必然在 \(i\) 的一侧，即要么都大于 \(i\) 要么都小于 \(i\)，否则会产生长度为 \(3\) 的下降子序列。考虑对所有边计数，在所有 \(i>j\) 且 \(i>k\) 的 \(i\) 处给这两条边 \((i,j)\) 和 \((i,k)\) 计数，这样所有边都被恰好算了一次，且总数量是偶数，与奇环矛盾。
一个暴力 dp，设 \(f_{i,j,k}\) 为前 \(i\) 个数，长度为 \(1,2\) 的下降子序列最后一个数的最大值分别为 \(j,k\) 是否可行，复杂度是 \(O\left(n^3\right)\)。
利用 dp 的值，而不是只存储布尔值，设 \(f_{i,j}\) 为前 \(i\) 个数，长度为 \(1\) 的下降子序列最后一个数的最大值为 \(j\)，长度为 \(2\) 的下降子序列最后一个数的最大值最小能是多少，复杂度是 \(O\left(n^2\right)\)。
继续通过转移的性质优化：
可以看到 \(j\) 和 \(f_{i,j}\) 至少有一个是 \(\pm a_i\)，那么可以将状态简化为 \(g_{i,0/1,0/1}\) 表示 \(j/f_{i,j}=a_i/-a_i\) 时另一个值 (\(f_{i,j}/j\)) 的最小值，转移同上，时间复杂度为 \(O(n)\)。输出方案在转移时记录一下即可，\(g\) 中已经记录了当前 \(a_i\) 的正负，只需从哪一个状态转移过来的即可。
CF1622F¶
题意¶
求 \(\{1,2,\ldots,n\}\) 的最大子集 \(S\) 使得 \(\displaystyle \prod _{x \in S} x!\) 是完全平方数。(\(1 \le n \le 10^6\))
题解¶
需要先观察/打表出最多从 \(S\) 中删掉 \(3\) 个数：
- 如果 \(n\) 是偶数，注意到 \((2i-1)!\) 和 \((2i)!\) 乘起来除了 \(2i\) 都被抵消了 (即不影响是否是完全平方数)，因此只需保证 \(\displaystyle \prod _{i=1}^{\frac{n}{2}}2i\) 是完全平方数，即 \(\displaystyle 2^{\frac{n}{2}}\left(\frac{n}{2}\right)!\) 是完全平方数，若 \(\dfrac{n}{2}\) 是偶数，从 \(S\) 中删掉 \(\dfrac{n}{2}\) 即可；否则从 \(S\) 中删掉 \(\dfrac{n}{2}\) 和 \(2\) 即可。
- 如果 \(n\) 是奇数，把 \(n\) 删掉就可以转化到上面的情况，最多从 \(S\) 中删掉 \(3\) 个数。
接下来只需要判断能否删 \(< 3\) 个数。将 \(\displaystyle \prod _{x \in S} x!\) 表示为一个 \(01\) 串，代表每个质因子是否为奇数次幂，若 \(n\) 是偶数只需算 \(\displaystyle \prod _{i=1}^{\frac{n}{2}}2i\)，否则先算 \((n-1)!\) 再单独算 \(n!\) 的贡献。
若全为 \(0\) 则已经是完全平方数，答案为 \(0\)；否则将 \(01\) 串哈希设为 \(h\)，接着从小到大遍历 \(i!\) 计算其对应的 \(01\) 串，若有一个哈希值和 \(h\) 相同，则答案为 \(1\)；否则将每个 \(i!\) 对应 \(01\) 串的哈希值放入 map，通过 \(h\) 算出另一个 \(01\) 串及其哈希值，在 map 里寻找即可。
若都没有，则答案一定为 \(3\)，且为上面所述的情况。时间复杂度为 \(O(n\log n)\)。
CF1625D¶
题意¶
给定一个 \(n\) 个元素的集合，选取一个最大的子集，使得子集中任意两个数异或值 \(\ge k\)。(\(2 \le n \le 3 \times 10^5\))
题解¶
我的辣鸡做法：
将所有数放到从高位到低位的 Trie 上，dfs 回溯时：
- 如果左右子树内只能选一个点，而存在一种方案左右各选一个，就选这两个，并标记该子树是 ok 的；否则说明该子树内只能选一个点，继续往上传。
- 如果左右子树一个是 ok 的，另一个内只能选一个点，就随便选一个点，并标记整个子树是 ok 的。
- 如果左右子树都是 ok 的，则该子树也是 ok 的。
- 如果没有左儿子或没有右儿子，则继承另一个的属性继续上传。
第一种情况找异或值最大的点对时，枚举左子树所有点，按位贪心在右子树上跑，每个点最多被找 \(O(\log V)\) 次，找的树高也是 \(O(\log V)\)，总复杂度即为 \(O\left(n \log ^2 V\right)\)，\(V\) 是值域。
正确性可以感性理解，一方面为每棵只能选一个点的子树尽可能选定点，避免进一步合并，另一方面子树外的点和子树内点异或一定会更大，因为更高位会出现 \(1\)。
题解的正经做法：
将集合中中的元素排序后，设序列为 \(a_1,a_2,\ldots,a_n\)，那么 \(a_i \oplus a_j > a_i \oplus a_k\) (\(k < j < i\))，即距离越远异或值越大，证明可以从 Trie 上找 LCA、再将两个子树合并继续找 LCA 来理解。
因此只需要保证相邻元素异或值 \(\ge k\)，得到一个 \(O\left(n^2\right)\) 的做法。将 dp 改为 Trie 上，根据和 \(k\) 的大小依次确定每一位，利用 Trie 上子树最大值，即可做到 \(O(n \log V)\)，\(V\) 是值域。
CF1625E¶
题意¶
给定一个长度为 \(n\) 的括号序列字符串，共有 \(q\) 次操作：
- 给定 \(l,r\)，保证字符串中 \(l\) 到 \(r\) 形如 \((....)\)，将两端的括号变成 \(.\)
- 给定 \(l,r\)，保证字符串中 \(l\) 到 \(r\) 的子串是一个好字符串，问字符串中 \(l\) 到 \(r\) 的子串中，有多少个子串是好字符串。
好字符串是指这个字符串删掉所有 \(.\) 后是一个合法括号序，且开头结尾不是 \(.\)
(\(2 \le n \le 3 \times 10^5\)，\(1 \le q \le 3 \times 10^5\))
题解¶
所有 \(.\) 都是没有意义的，第一个操作相当于删掉一个 \(()\)，第二个操作相当于问一个合法括号序中有多少个子串是合法括号序。
初始字符串不一定是一个合法括号序，注意到每次都是删除 \(()\) 且询问都是问合法括号序，因此一开始没匹配上的括号一定不会被删也不会被询问。通过一次简单的模拟找到哪些括号可以被匹配，剩下的标记为删除。
忽略所有删除的括号，剩下串是一个合法括号序，建出这个括号序对应的树。具体来说，初始有一个节点，遇到左括号就新建一个节点作为它的儿子，这个节点就代表这一对括号；遇到右括号就跳回父亲。
可以发现，所有是合法序列的子串，对应到数个极大的子树上，这些子树的根节点的父亲一定是相同的，否则一定会出现父节点的左括号或右括号匹配不上的情况。
因此，一个节点子树对应合法括号序的合法序列子串数量即为子树中每个点 \(\dfrac{x(x+1)}{2}\) 的和，\(x\) 是对应节点的儿子数量，即上述说的数个极大的子树和某一结点的数个连续儿子一一对应。
询问的合法括号序可能对应 \(c\) 个子树，此时答案即为这些子树的答案加上 \(\dfrac{c(c+1)}{2}\)。
维护子树中 \(\dfrac{x(x+1)}{2}\) 的和以及修改操作使用树状数组 + dfn 序即可完成，得到上述的 \(c\) 则需要判断每个节点是父亲的第几个节点，为每个父亲节点开一个树状数组记录每个子节点之前有多少个子节点被删了即可解决。
总时间复杂度为 \(O(n \log n)\)。
CF1626E¶
题意¶
给定一棵 \(n\) 个节点的树，节点颜色分为黑白，至少有两个黑点。若你当前处于 \(x\)，\(y\) 是一个黑点，则你可以沿 \(x\) 到 \(y\) 的唯一路径移动一条边，两次连续移动不能选择同一个 \(y\)。问起点设置在哪些点最终可以移动到黑点上 (已经是黑点则显然可以)。(\(3 \le n \le 3 \times 10^5\))
题解¶
定义一次移动 \(x \to y\) 是有效的，当其满足：
- \(y\) 是黑点。
- 或下一次移动可以不选择 \(y \to x\)。
如果不满足这两个条件，下一次一定会移动回 \(x\)，相当于没有移动。
因此我们找到所有有效移动，连有向边 \(x \to y\)，那么在新的有向图上所有能到黑点的点都是合法的。
建反图多起点 bfs 即可，时间复杂度为 \(O(n)\)。
CF1626F¶
题意¶
给定序列 \(a_0,a_1,\ldots,a_{n-1}\)，依次进行 \(k\) 次操作，第 \(i\) 次操作为：
- 等概率选择一个元素 \(a_x\)，将 \(a_x\) 累加到答案中，之后将 \(a_x\) 变为 \(a_x-a_x \bmod i\)。
问答案的期望是多少。(\(1 \le n \le 10^7\)，\(0 \le a_i < 998244353\)，\(1 \le k \le 17\))
题解¶
每次操作为将 \(a_x\) 变为最大的不超过 \(a_x\) 的是 \(i\) 倍数的数，设 \(L=\operatorname{lcm}(1,2,\ldots,k)\)，则 \(a_i\) 永远不会小于 \(a_i-a_i \bmod L\)。
因此先将 \(a_i-a_i \bmod L\) 的部分统计一下，每个数被选都一定会加这么多，因此对期望的贡献为 \(\displaystyle \frac{k}{n}\sum_{i=0}^{n-1}(a_i-a_i \bmod L)\)。
接着将每个 \(a_i\) 变为 \(a_i \bmod L\)，通过简单 dp 求出 \(f_{i,j}\) 表示第 \(i\) 次操作前 \(a\) 中为 \(j\) 的元素的期望数量，再计算对答案的贡献即可。
总时间复杂度为 \(O(n + L \log L)\)，\(k=17\) 时 \(L\) 约为 \(10^7\)。
CF1627D¶
题意¶
给定 \(\left\{1,2,\ldots,10^6\right\}\) 的一个子集，每次可以选两个数将其 \(\gcd\) 加入集合，问能加多少个数。
题解¶
赛时方法是莫比乌斯反演，从大到小考虑每个数最终能否出现在集合中：
- 如果一开始就有，那显然可以。
- 否则，计算所有是它倍数那些数是否存在两个数 \(\gcd\) 是它。设这个数为 \(i\)，\(f_n\) 为是 \(n\) 倍数中能出现在集合中数的数量，则满足 \(\gcd(x,y)=i\) 的二元组 \((x,y)\) 数量即为 \(\displaystyle \sum_{i \mid j}\binom{f_j}{2}\mu\left(\frac{j}{i}\right)\)。
- 若一个数可以，遍历因子更新 \(f\) 即可。
设 \(n=10^6\)，时间复杂度为 \(O(n \log n)\)。
正解做法为，上述第二种情况不需要这么复杂，显然把 \(i\) 所有倍数放一起取 \(\gcd\) 能得到数的最小值就是 \(i\)，若这个数是 \(i\) 则可以得到 \(i\)，否则无论如何不会出现 \(i\)，因此全部取 \(\gcd\) 即可。时间复杂度看上去是 \(O\left(n \log ^2 n\right)\) 的，但其实常数非常小，也可以用 \(O(1)\) gcd 把复杂度变为严格 \(O(n \log n)\) 但没必要。
CF1627F¶
题意¶
\(k \times k\) 的方格图，\(k\) 是偶数，有 \(n\) 个边相邻的格子对。你需要将方格图用一条水平和垂直的折线段划分为两部分，要求这两部分的图形全等。在此基础上最大化在同一部分的格子对数量。(\(1 \le n \le 10^5\)，\(2 \le k \le 500\))
题解¶
可以证明想要全等划分线一定是中心对称的。（具体证明还没懂
模拟划分线一端和中心对称另一端的行程，一端从上边界和左边界出发 (多个起点)，每次可以上下左右走，另一端往反方向走，只有不出边界，每经过一条边就加上对应格子对的数量，到达中心点的最短路设为 \(x\)，则答案为 \(n-x\)。
注意到最优解一定在其中，只不过一些不合法解也可能被算进去，具体是指折线可能绕回来相交，但这样答案一定不会更优，因此算法是正确的。
总时间复杂度为 \(O\left(n+k^2 \log k\right)\)。
ABC234H¶
题意¶
二维平面上 \(n\) 个点，输出所有欧氏距离不超过 \(k\) 的点对，保证数量不超过 \(4 \times 10^5\)。(\(1 \le n \le 2 \times 10^5\))
题解¶
赛时做法是 KD-Tree 暴力找每个圆内所有点，可以卡过去。
设点对数量为 \(m\)，题解给出的 \(O(n+m)\) 的做法如下：
\(k \times k\) 画格子，那么合法点对一定在同一格子或在相邻格子。暴力枚举所有可能，复杂度是对的。
对于前者，假设一个格子内有 \(n\) 个点，计算量为 \(n^2\)，可以证明格子内合法点对的数量的下界是 \(\Omega\left(n^2\right)\) 的，考虑用四个 \(\dfrac{k}{\sqrt 2} \times \dfrac{k}{\sqrt 2}\) 的小正方形完全覆盖 \(k \times k\) 的格子 (中间有重合的地方)，那么一定存在 \(\left\lceil\dfrac{n}{4}\right\rceil\) 个点在同一个小正方形内，它们两两之间的距离均不超过 \(k\)，从而数量是 \(\Omega\left(n^2\right)\) 的，也就是说这 \(n^2\) 的计算量至少会找到 \(\Omega\left(n^2\right)\) 对点对。
对于后者，设两个格子分别各有 \(n,m\) 个点，计算量为 \(nm\)，而 \(nm \le \dfrac{1}{2}\left(n^2+m^2\right)\)，且一个格子至多和四个格子相邻，因此相当于每个格子计算量的 \(n^2\) 乘以了一个常数倍，不影响复杂度。