10月做题记录

[TOC]

1. CF1404D - Game of Pairs

题面

交互题。

Aob 和 Blice 在进行游戏，有一个正整数 $n$，首先，Aob 需要将 $1,2,\cdots,2n$ 分为 $n$ 对，接着 Blice 需要每对当中选取一个数，如果选取的数和是 $2n$ 的倍数，那么 Blice 胜，否则 Aob 胜

你的任务是，交互器会给你一个正整数 $n$，你可以选择作为 Aob 或 Blice 来玩这个游戏，并取得胜利

如果你选择了 Aob，那么你需要给出一种划分方式，将 $1,2,\cdots,2n$ 分为 $n$ 对，使得 Blice 无法获胜

如果你选择了 Blice，那么交互库会给出划分方式，而你需要从每对中选出一个数使其和为 $2n$ 的倍数

$1\le n\le5\cdot10^5$

题解

我们不妨将数列为 $0,1,\cdots,2n-1$

考虑当 $2\mid n$ 时，$n\nmid0+1+\cdots+(n-1)$。因此，我们可以在 $n$ 为偶数时，选择 Aob，并将 $i$ 与 $i+n$ 分在一组

当 $2\nmid n$ 时，$n\mid0+1+\cdots (n-1)$，所以我们可以考虑尽量选出余数互不相同的数

这样的话，我们 $i$ 与 $i+n$ 中只能够选择一个，且必须选一个，那么“选且仅选一个”关系形成了一个二分图，而一个合法的黑白染色对应着一种选法，这里我们不妨假设选出所有黑点，而我们要求的就是满足 $\ge n$ 的数有偶数个的染色方案

每个连通块有两种染色方式，两种染色方式的 $\ge n$ 的数个数的奇偶性可能为：奇奇，偶偶，奇偶。而由于 $n$ 是奇数，所以至少有一个“奇偶”，那么我们可以先将所有“奇奇”与“偶偶”选完，然后再用一个“奇偶”将奇偶性调节为偶数，剩下的“奇偶”均选择个数为偶数的选择方式

2. CF8E - Beads

题面

我们定义两个 01 串是等价的，当且仅当可以从第一个 01 串反转每一位/前后翻转/翻转并反转得到第二个 01 串。

我们将除全 0 串与全 1 串除外的所有长度为 $n$ 的 01 串分为若干组，满足同组内的 01 串都是等价的，不同组内的 01 串一定不等价，我们将这些组按其中字典序最小的串排序，求第 $k$ 组的字典序最小的串

$1\le n\le50,1\le k\le10^{16}$

题解

先把全 0 串与全 1 串加上，方便讨论

考虑什么样的串会成为组中的最小串，显然，它需要小于等于它的反转/翻转/反转翻转串，那么它的第一位一定是 0，如果末位是 0，那么它一定小于反转翻转串，只用考虑翻转串，这要求 $s[2:\lfloor\frac n2\rfloor]$ 小于等于翻转后的 $s[n-\lfloor\frac n2\rfloor+1:n-1]$，对于末位是 1 的情况同理

那么我们可以考虑直接枚举答案的前 25 位分别算有多少个串符合要求，如果和超过了 $k$，那么我们按字典序遍历这个块内的符合要求的串，找到第 $k$ 个即可

复杂度 $O(2^{\frac n2})$

3. CF11D - Simple Task

题面

给定一张 $n$ 个点 $m$ 条边的无向图，保证无重边自环，求该图的简单环个数，$1\le n\le19$

题解

考虑令 $dp[i][j][S]$ 表示从 $i$ 到 $j$，经过的点集为 $S$ 的路径数，最后统计 $\sum dp[u][v]S\in E)$，但这样显然会将环算重，因为可以从环上的任意一个节点开始走一圈回到环上与其相邻的节点，所以考虑固定起点

令 $dp[i][S]$ 表示从 $S$ 中编号最小的点到 $i$，且经过集合为 $S$ 的路径数，这样便可以 $O(n^22^n)$ 解决本题

4. CF15D - Map

题面

有一个 $n\times m$ 的网格，每个格子内都有一个数值 $a_{i,j}$，定义一个子矩阵的权值为 $\sum a_{x,y}-a_{min}$，其中 $a_{min}$ 为这个子矩阵内所有数的最小值

有一个人，要剪这个网格，每次他会从没被剪掉中选择权值最小的 $a\times b$ 的子矩阵，如果这样不唯一那么选择最靠上的，如果这样仍不唯一那么选择剩下的中最靠左的，将这个子矩阵剪掉，这样重复直到不能找出 $a\times b$ 的子矩阵为止

求每次剪掉的子矩阵的左上角坐标及子矩阵权值

$1\le a\le n\le1000,1\le b\le m\le1000$

题解

考虑我们可以通过单调队列预处理出每个 $a\times b$ 子矩阵的最小值，那么我们可以预处理出每个 $a\times b$ 子矩阵的权值，然后按题意模拟即可

5. CF1580D - Subsequence

题面

有一个长度为 $n$ 的数列 $a$，定义长度为 $m$ 的子序列 $a_{b_1},a_{b_2},\cdots,a_{b_m}$ 的权值如下：

$$\sum_{i=1}^m(m\cdot a_{b_i})-\sum_{i=1}^m\sum_{j=1}^mf(\min(b_i,b_j),\max(b_i,b_j))$$

其中 $f(i,j)$ 表示 $\min(a_i,a_{i+1},\cdots,a_j)$，求权值最大的长度为 $m$ 的子序列

题解

牛逼题。

将贡献变换：

$$=\sum_{i=1}^m\sum_{j=1}^m(a_{b_i}-f(\min(b_i,b_j),\max(b_i,b_j)))\\ =\sum_{i=1}^m\sum_{j=i+1}^m(a_i+a_j-2\min(a_i,a_{i+1},\cdots,a_j))$$

可以发现，这类似于笛卡尔树上的路径长度 $dis_u+dis_v-2dis_{LCA(u,v)}$，只要我们令每条边的权值为父亲与儿子的点权差即可，转化为笛卡尔树上的问题，树形背包求解，复杂度 $O(nm)$

6. CF19E - Fairy

题面

给定一张 $n$ 个点 $m$ 条边的无向图，求有哪些边满足删掉这条边之后可以使这个图变成二分图

$1\le n\le10^4,0\le m\le10^4$

题解

神仙题。

引理：对于一个无向图，我们找出它的任意一棵 dfs 树，那么一定可以通过只含有一条非树边的环异或得到所有简单环

证明：咕咕咕

考虑相当于我们要删一条边破坏掉所有的奇环，于是答案就是奇环的交集

但这显然没法直接求。考虑所有只含一条非树边的奇环，我们显然要破坏这些环，所以答案一定在这些环的交集上，这可以通过树上差分求出

同时，我们发现，我们删的边一定不能在只含一条非树边的偶环上，否则就会出现下图的情况

其中蓝色为偶环，红色为奇环，紫色构成了一个奇环，因此删除绿链上的边无法消除所有奇环，这是因为紫环是由蓝环异或红环得到，而绿链在这两个环中都存在，于是被抵消掉了（感性理解）

因此我们建出 dfs 树后打差分标记即可

注意处理图不连通以及本身就是二分图的情况

复杂度 $O(m\log m)$（昂，瓶颈是排序输出）

7. CF39C - Moon Craters

题面

数轴上有 $n$ 个圆，第 $i$ 个圆的圆心为 $c_i$，半径为 $r_i$，你需要选出尽可能多的圆，使得选出的圆中没有两个圆有两个交点

$1\le n\le2000$

题解

显然可以将圆转换为区间，考虑答案与具体坐标无关，所以可以离散化

令 $dp[l][r]$ 为坐标 $[l,r]$ 内的圆能够选出的数量

如果有一个圆对应的区间为 $[l,r]$，那么我们一定会选该圆，将 dp 值加一即可

如果有其他圆左端点为 $l$，那么我们依次考虑是否选择，即对于圆 $(l,k)$，转移方程为 $dp[l][r]\leftarrow dp[l][k]+dp[k][r]$

同时，我们可以舍弃所有左端点为 $l$ 的圆，并把左端点向右挪一位，$dp[l][r]\leftarrow dp[l+1][r]$

复杂度 $O(n^2)$

8. CF49E - Common Ancestor

题面

给定两个字符串 $s,t$，有 $n$ 种变换规则 $a_i\rightarrow b_ic_i$，表示可以将一个 $a_i$ 字符变为 $b_i$ 与 $c_i$

称 $S$ 是 $s,t$ 的公共祖先，当且仅当 $S$ 通过这 $n$ 种变换规则分别变成 $s$ 和 $t$，求 $S$ 的最小长度

$1\le n\le50$

题解

就这也配黑题？？？

令 $dps[l][r][x]$ 表示 $s[l:r]$ 是否能由字符 $x$ 得出，转移时枚举第一步使用的变换规则 $x\rightarrow ab$，然后枚举断点 $k$ 从 $dps[l][k][a]\&dps[k+1][r][b]$ 转移即可，这一步复杂度 $O(|s|^3n)$，对于 $t$ 同样处理出 $dpt[l][r][x]$

令 $f[i][j]$ 表示 $s[1:i]$ 与 $t[1:j]$ 的答案，这里直接暴力枚举上一个字符是由哪个区间变换而来的即可，复杂度 $O(|s|^2|t|^2n)$

9. CF73D - FreeDiv

题面

给定一张 $n$ 个点 $m$ 条边的无向图，你需要依次执行以下两步操作：

1. 在图中任意连边
2. 继续加边，需满足每个连通块所直接相连的这一步添加的边不超过 $k$ 条，且与每个点直接相连的这一步添加的边不超过 $1$ 条

要求经过这两步后图联通，求第一步最少添加的边数

$1\le n,k\le10^6,0\le m\le10^6$

题解

我们可以将每个连通块看做一个点，那么第二步的限制就相当于每个连通块的度数不超过 $k$ 且不超过这个连通块内点数

考虑将每个连通块视为一个点之后我们一定要连出一个树，那么当且仅当 $\sum_{u}\min(deg_u,k)\ge2(cnt-1)$ 的时候我们才能连出一个数，其中 $deg_i$ 表示连通块 $i$ 中包含的点数，$cnt$ 表示连通块个数

考虑没有 $\min$ 的情况，那么将某两个连通块在第一步连边时会导致 $cnt$ 减 $1$，其他的均不变，所以相当于在不等式左边减 $2$，那么我们只要一直选任意两个连通块即可

但现在有了 $\min$，我们的 $deg_u$ 超过一个值就会产生损失，而我们想让这个不等式尽快成立就需要最小化损失，我们每次取点数最少的两个连通块连在一起即可，用堆维护

复杂度 $O(n\log n)$

10. CF1017F - The Neutral Zone

题面

设整数 $x$ 的质因数分解为 $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，定义 $f(x)=Ax^3+Bx^2+Cx+D$，$\textrm{exlog}_f(x)=\alpha_1f(p_1)+\alpha_2f(p_2)+\cdots+\alpha_kf(p_k)$

给定整数 $n$，求 $\sum_{i=1}^n\textrm{exlog}_f(i)$，答案对 $2^{32}$ 取模

$1\le n\le3\times10^8$，空间 $16MB$

题解

做法 1

分块打表，将所有 $B$ 的倍数的答案打表，然后暴力计算中间的每一个 $\textrm{exlog}_f(i)$

做法 2

考虑如果我们求出了所有质数，那么我对于一个质数 $p$，可以在 $O(\log_pn)$ 的时间内求出 $p$ 对答案产生的贡献，而质数约有 $O(\frac n{\ln n})$ 个，所以这部分是 $O(n)$

使用欧拉筛空间会爆掉，所以考虑使用埃氏筛，这样我们只用存 $3\times10^8$ 个 bool，使用 bitset 存储仍然是 $37.5MB$ 左右

考虑质数一定是 $6k+1$ 与 $6k+5$ 型的，所以只用存 $10^8$ 个 bool，可以存下

做法 3

考虑分块埃筛，先筛出 $1\sim\sqrt n$ 内的质数，然后将每 $s$ 个数分为一块，对每一个块内的数用 $1\sim\sqrt n$ 的质数筛一遍，复杂度 $O(s\sqrt n+n\log\log n)$，空间复杂度 $O(s)$