Codeforces 题目选讲 3

Minimum Euler Cycle

给你一个有向图 $K_n=(V,E)$ 。 $|V|=n$ 。 $|E|=\{ (u,v) \mid u,v\in E,u\ne v \}$ （有向边）。你要求出字典序最小的欧拉回路的端点序列。例如 $n=3$ 时为 $\{1,2,1,3,2,3,1\}$ 。
由于输出太大，你只需要输出一个区间 $[L,R]$ 。
$n\le 10^5,R-L\le 10^5$ 。

构造贪心

这序列一定是 $\{ \{1,i>1\},\{2,i>2\},\{3,i>3\},...,\{n,i>n\},1\}$ 。 $\{1,i>1\}$ 表示 $\{1,2,1,3,1,4,\cdots,1,n\}$ 。

于是可以简单地求出了。

代码

Divisor Paths

给你一个整数 $D$ ，要构建一个无向图 $G=(V,E)$ ： $V=\{x\mid x|d\}$ ， $E=\{(x,y)\mid x>y,y|x,\frac{x}{y}\text{ is prime}\}$ 。设 $(x,y)$ （ $x>y$ ）的边权为 $w(x,y)=\sum_{d|x}[d\nmid y]$ 。
现在 $q$ 次询问 $u,v$ 两点的最短路径数。
$D\le 10^{15},q\le 3\times 10^5,u,v\in V$ 。

数学数论盲猜

一条边 $(x,y)$ 相当于 $y$ 乘一个质数走到 $x$ 。

直觉告诉我们 $u,v$ 的最短路是 $u \to \gcd(u,v)\to v$ 的权值。相当于你可以从 $u$ 开始，除掉一些 $u$ 比 $v$ 多的质数，再乘上一些 $v$ 比 $u$ 多的质数。也可以发现最短路一定经过 $\gcd(u,v)$ 。也就是说最短路径数是 $f\left(\frac{u}{\gcd(u,v)}\right)f\left(\frac{v}{\gcd(u,v)}\right)$ （两边的路径数只和商有关，因此是一个一元函数）。

那么最短路的数量，相当于就是你乘（除）质数的顺序。那么我们只关心不同质数间的顺序。这就是个多重组合数。那么 $f(x)$ 就可以容易地计算了。

最后，由于 $u,v$ 是 $D$ 的约数。因此分解质因数的时候枚举 $D$ 的质因数即可。

时间复杂度 $O(\sqrt{D}+q\log D)$ 。

代码

Strange Function

对于整数序列 $a$ ，设 $f(a)$ 表示 $a$ 的前缀最大值序列。如 $f(\{3,1,2,7,7,3,6,7,8\})=\{3,7,8\}$ 。
给出长度为 $n$ 的序列 $a,p$ 和长度为 $m$ 的序列 $b$ 。你可以以 $p_i$ 的代价删掉 $a_i$ （代价可能是负的），要求用最小的代价删掉一些数，使得 $f(a')=b$ 。
$n\le 5\times 10^5,1\le a_i\le n,|p_i|\le 10^9, 1\le m\le n, 1\le b_{i-1}<b_i\le n$ 。

DP 线段树

设 $f(i,j)$ 表示前 $i$ 个数的最小代价使得 $f(a[1,i])=b[1,j]$ 。考虑 $a_{i+1}$ ：

若 $a_{i+1}<b_j$ 。则 $a_{i+1}$ 可以删也可以不删。因此它的代价贡献是 $\min(p_{i+1},0)$ 。
若 $a_{i+1}=b_j$ ，则 $a_{i+1}$ 可以删。也可以不删。如果不删的话，会多一种转移： $f(i,j-1)\to f(i+1,j)$ 。
若 $a_{i+1}>b_j$ 。如果选，那么必须 $a_{i+1}=b_{j+1}$ ，不然不合法；如果不选（删掉），则代价就是 $p_{i+1}$ 。

对第二维建线段树维护 DP 即可。

时间复杂度 $O((n+m)\log_2m)$ 。

代码

Substring Search

给出一个小写字母的一一映射（长度为 $26$ 的排列） $p$ 。规定字符串 $s$ 和 $t$ 匹配当且仅当：
$|s|=|t|$ ；
$\forall 1\le i\le |s|$ ， $s_i=t_i$ 或 $p_{s_i}=t_i$ 。
现在给出两个串 $s,t$ （ $|s|\le |t|$ ），求出 $s$ 在 $t$ 的每个位置是否匹配。输出长度为 $|t|-|s|+1$ 的 01 串。
$|s|\le |t|\le 2\times 10^5$ 。

多项式随机

$s_i=t_i$ 或者 $p_{s_i}=t_i$ ，等价于 $(s_i-t_i)^2(p_{s_i}-t_i)^2=0$ 。因此 $s$ 在 $i$ 处匹配的条件是

$f(i)=\sum_{j=1}^{|s|}(s_j-t_{i+j})^2(p_{s_j}-t_{i+j})^2=0$

那么我们求出 $f(0),\cdots,f(|t|-|s|)$ 即可。

如果 $f$ 是 $\sum a_ib_{i+j}$ 的形式，我们可以简单地使用 $O(n\log_2n)$ 多项式乘法计算。而上式实际上可以拆开分成 5 项，分别对应 $t_{i+j}$ 的 0 到 4 次方项。因此我们对每一项都做多项式乘法最后加起来即可。

时间复杂度 $O(n\log_2n)$ 。但这样有一个问题。就是可能被卡 NTT 模数。因此我们给每个字母分配一个随机权值。这样就行了。

代码

Edge Weight Assignment

给出一棵 $n$ 个点树。你可以给每条边一个边权。要求赋权使得任意两个叶子的路径异或和为 $0$ 。
问不同权值个数的最大值和最小值。
$3\le n\le 10^5$ 。

分类讨论构造手玩 DP

题目中的条件可以转化为，选择一个根结点。则任意叶子结点到根的异或和相等。不妨选一个非叶子结点作为根。

考虑最小值。那么容易发现同一个结点 $u$ 的所有叶子儿子的父边是权值相同的，可以直合并成一个结点。手玩发现，答案是 1 或者 3。3 的构造如下（设 $a\oplus b\oplus c=0$ ）：

也可以简单描述一下。考虑从根结点往下构造。设 $\text{C}(u,a)$ 表示构造 $u$ 的子树的边权，使得 $u$ 子树里所有叶子点到 $u$ 的异或和为 $a$ 。那么对于 $C(u,a)$ ，我们给 $u$ 的叶子儿子的父边赋权为 $a$ ，然后给 $u$ 的非叶儿子 $v$ 的父边赋权为 $b$ 并递归构造 $C(v,c)$ 。

1 的情况很平凡。

考虑最大值。经过刚才的思考过程，可以发现，两个子树是独立的，可以任意赋权。因此把叶子儿子合并后做一个简单的树形 DP 即可。

代码

Nested Rubber Bands

你有一棵 $n$ 个点树 $T=(V,E)$ 。要求你构造平面上 $n$ 个封闭图形 $a_i$ 。若 $a_u$ 和 $a_v$ 相交（边界相交），当且仅当 $(u,v)\in E$ 。问这 $n$ 个封闭图形中至多有多少个互相嵌套的图形。即找一个最大子集 $S$ ，使得 $\forall x,y\in S$ ， $a_x$ 和 $a_y$ 是包含关系。输出 $|S|$ 。
$3\le n\le 10^5$ 。

DP 手玩

考虑这样一个问题：若 $(x,y)\in E$ 且 $a_x\subset a_z$ ，那么 $a_y$ 和 $a_z$ 是什么关系？

容易发现， $a_y\subset a_z$ 、 $a_y,a_z$ 相交这两个条件有且仅有一个满足。

我们断言：一个合法的相互嵌套方案是集合 $S$ 使得：

$S$ 中任意两个点不相邻。
存在树上的一条简单路径 $P$ 使得 $S$ 中的点到 $P$ 的距离小于等于 $1$ （毛毛虫）。

证明：反证法。不妨考虑下图的情况。其他情况可以类比：

在这里 $5,6,7$ 是不分顺序的。不妨设 $a_7\subset a_6\subset a_5$ 。

那么根据刚才的小发现， $4$ 一定在被 $6$ 包含；于是 $1$ 也一定被 $6$ 包含， $2$ 也一定被 $6$ 包含。

那么 $a_2\subset a_6\subset a_5$ ，而 $a_2,a_5$ 是相交的，矛盾。

而如果不存在上图的方案，可以证明一定是毛毛虫的形式。或者说我们还可以证明，毛毛虫为什么一定合法？

这个也不难。枚举在末尾加一个子树，看子树的根结点选或者不选。然后都可以构造使得新构造的把之前的都包含了。

证完后就可以求答案了。可以直接树形 DP 或者换根。

复杂度 $O(n)$ 。

代码

Sergey’s problem

给你一个 $n$ 个点 $m$ 条边的有向图（无自环，可能有重边）。要求你求出一个点集 $Q$ 使得对于任意不在 $Q$ 中的点 $u$ ，都存在一个点 $v\in Q$ 使得 $v$ 走不超过 2 步可以到 $u$ 。可以证明一定有解。
$n,m\le 10^6$ 。

归纳法构造

如果我选了点 $u$ ，那么 $u$ 走一步能到的点就不能选。另一方面，如果走一步能到 $u$ 的某个点 $v$ 被选了，那么意味着 $u$ 和 $u$ 走一步能到的点都被 $v$ 覆盖了。因此我们可以把 $u$ 和它走一步能到的点删了，对剩下的图构造。构造完了我们再看是否有走一步能到 $u$ 的点被选。如果有，就不用选 $u$ 了。否则就选 $u$ 。

写一个 DFS 即可。

时间复杂度 $O(n+m)$ 。

代码

Large Triangle

给你二维平面上 $n$ 个点，问你是否存在三个点使得三角形面积恰好为 $S$ 。
$3\le n\le 2000,1\le S\le 2\times 10^{18}$ 。

微调

如果确定了两个点，那么把它当作一个向量，与其他点算叉积，则可以排序后二分判定。

但问题是，你选择不同的向量，顺序也不一样。每次排序的话，就是 $O(n^3\log_2n)$ 的。

不过考虑一下，如果我只是轻微旋转一下这个向量，那么只有这个向量的两个端点的顺序发生变化，两者交换一下即可。只要我们别旋转到超过下一个向量，则其他的点的顺序也是不变的。

因此把 $O(n^2)$ 个向量按斜率排序，然后按序交换并二分即可。时间复杂度 $O(n^2\log_2n)$ 。

代码

Raining season

给一棵 $n$ 个点的树，每条边的权值是一个一次函数 $a_ix+b_i$ 。给你 $m$ ，问你在 $x=0,1,\cdots,m-1$ 时树的直径是多少。输出 $m$ 个数。
$n\le 10^5,m\le 10^6,0\le a_i\le 10^5,0\le b_i\le 10^9$ 。

边分治闵可夫斯基和凸包计算几何

一条路径的权值是一次函数。

则直径的函数是半平面交的形式。

考虑边分治。首先多叉树转二叉树。

假设当前的连通块的大小是 $n$ ，考虑经过当前分治边的直径。显然可以看作是两边各选一个点的一次函数加起来，对这 $O(n^2)$ 个一次函数求半平面交。但这东西复杂度太大。

将半平面交对偶成凸包（一次函数对偶成点）。容易发现，两个一次函数的加法，就是两个点（向量）的加法。则两边的一次函数加起来的半平面交，相当于对偶后两边的点加起来的凸包。也就是两边的凸包的闵可夫斯基和。这个可以 $O(n)$ 做，而且得到的凸包的大小也是 $O(n)$ 的。

对于每个连通块我们都做一次，这样会得到总大小为 $O(n\log_2n)$ 的凸包集合。把这些点全丢一起再求一次凸包（注意是凸包合并，不是闵可夫斯基和），再对偶回去就得到直径的函数了。

然后求一下 $0,\cdots,m-1$ 的点值即可。

时间复杂度 $O(n\log_2^2n+m)$ 。

由于一般的闵可夫斯基和太容易出锅，因此代码里写的是两个上凸壳的闵可夫斯基和。这样的好处是不用极角排序，按 x 轴排序也能做。

代码

Chiori and Doll Picking (hard version)

给出一个非负整数集合 $A$ ，设
$p_i=\sum_{S\subseteq A}\left[ \text{popcount}(\oplus_{x\in S}x)=i \right]$
求 $p_0,p_1,\cdots,p_m$ 。
$n\le 2\times 10^5,m\le 53$ 。

线性基 meet in middle FWT 组合数学

先求出线性基 $B$ ，设 $B$ 能表出的数的集合为 $S(B)$ 。那么答案显然就是线性基的数的答案乘 $2^{n-|B|}$ 。

若 $|B|\le 26$ ，则我们可以暴力枚举 $S(B)$ 的数并统计答案。

若 $|B|>26$ ，构造序列 $A$ ， $A_i=[i\in S(B)]$ 。那么 $A$ 有一些性质。不妨设 $A$ 的 FWT 变换为 $\hat{A}$ 。

性质 1： $\hat{A}_i$ 的取值只能为 $0$ 或 $2^{|B|}$ 。

我们知道 $\hat{A}_i=\sum_{j}A_j(-1)^{|i\& j|}$ 。而 $A$ 中值为 $1$ 的数只有 $2^{|B|}$ 个，因此若 $\hat{A}_i=2^{|B|}$ ，则必然满足： $\forall j\in S(B)$ ， $|i\& j|$ 是偶数。

那么这样的 $i$ 一共有多少个？假设满足该条件的 $i$ 的集合为 $G$ 。那么容易发现， $\forall x,y\in G$ ， $x\oplus y\in G$ ，也就是说 $G$ 有关于异或运算的封闭性。因此可以求出 $G$ 的一个线性基 $C$ 。容易发现 $C$ 的大小是小于等于 $m-|B|$ 的！因为你确定了 $B$ 中自由元的值后，根据“偶数条件”，其他主元的值也确定了。

我们可以使用一些技巧做到 $2^{m-|B|}$ 枚举 $G$ 中的数。

那么我们再考虑 FWT 回去求答案，则

$\begin{aligned} p_x &=\sum_{i=0}^{2^m-1}[|i|=x]A_i\\ &=\sum_{i=0}^{2^m-1}[|i|=x]\frac{1}{2^m}\sum_{j\in G}\hat{A}_j(-1)^{|i\& j|}\\ &=\frac{1}{2^{m-|B|}}\sum_{j\in G}\sum_{i=0}^{2^m-1}[|i|=x](-1)^{|i\& j|} \end{aligned}$

容易发现。后面的那个式子只和 $|j|$ 有关，即 $\sum_{i}[|i|=x](-1)^{|i\& j|}=g(x,|j|)$ 。那么我们想办法预处理 $g(x,y)$ 即可。

$g(x,y)=\sum_{i=0}^{2^m-1}[|i|=x](-1)^{|i\& (2^y-1)|}=\sum_{z=0}^{\min(x,y)}\binom{y}{z}\binom{m-y}{x-z}(-1)^z$

不妨设 $f(x)=\sum_{j\in G}[|j|=x]$ ，那么原式可以化为

$p_x=\frac{1}{2^{m-|B|}}\sum_{y=0}^{m}f(y)g(x,y)$

代码

Make Symmetrical

二维平面上，要求支持 $q$ 次操作：
插入一个整点 $(x,y)$ （ $1\le x,y\le 10^5$ ），保证这个点之前没有插入过。
删除一个点（之前插入过）。
给出 $(x,y)$ （ $1\le x,y\le 10^5$ ），求至少再加入多少个点可以使整个点集关于直线 $((0,0),(x,y))$ 轴对称。
$1\le q\le 2\times 10^5$ 。

暴力

关于 $((0,0),(x,y))$ 轴对称的点，到原点的距离是相等的。而实际上满足 $x^2+y^2=C$ 在固定 $C$ 的情况下的点 $(x,y)$ 的数量是不多的。在本题中至多有 $144$ 个点。

不妨考虑，每次加入一个点的时候，我们 $O(144)$ 地更新答案。然后查询的时候直接查表即可。

值得一提的是，在计算两个点的对称轴的时候由于这两个点到原点的距离相等，因此可以直接向量加法求出（菱形）。

用 map 维护。时间复杂度 $O(q\log_2n\cdot 144))$ ，使用 unordered_map 可以更快。

代码

Make Square

如果序列 $b_1,\cdots,b_m$ 中存在两个数 $b_i,b_j$ （ $i<j$ ）使得 $b_ib_j$ 是完全平方数，则 $b$ 是好的。
对于一个序列 $b$ ，每次操作，你可以选择一个元素并乘上一个质数，或者选择一个元素并除掉一个质数。 $f(b)$ 表示最少的操作次数使得 $b$ 变成好的。
给你一个序列 $a$ ，每次询问区间的 $f(a[l,r])$ 。
$n\le 2\times 10^5,q\le 10^6,a_i\le 5\times 10^6$ 。

DP 二进制表示异或扫描

首先想到把平凡因子去掉，这样每个数就最多有 $7$ 个互不相同的质因子，即最多有 $128$ 个约数。

现在，要让 $ab$ 是完全平方数（即 $a$ 到 $b$ 的最短距离），则相当于 $a$ 要先走到 $a$ 的某个约数 $x$ ，再从 $x$ 走到 $b$ 。

考虑扫描线 DP。考虑 $a_1,\cdots,a_i$ ，设 $f(x,d)$ 表示最大的 $j$ （ $j\le i$ ）使得 $x\mid a_j$ 且 $\frac{a_j}{x}$ 有 $d$ 个质因子（即 $x$ 走 $d$ 步到 $a_j$ ）。再设 $g_x$ 表示最大（靠右）的 $j$ 使得 $[j,i]$ 的答案 $\le x$ 。

考虑如何从 $i-1$ 更新到 $i$ 。加入一个 $a_i$ ，则我们可以先枚举 $x\mid a_i$ ，用 $a_i$ 走到 $x$ 再走 $d$ 步来更新对应的 $g$ （即使 $a_i$ 到 $x$ 和 $x$ 走的 $d$ 步中有相同的质因数也没关系。因为我们求的是 $\le$ ）。更新完 $g$ 再用 $x$ 走到 $a_i$ 来更新 $f$ 。

然后我们就可以求出以 $i$ 为右端点的询问的答案了。

时间复杂度 $O(n(\sqrt{a_i}+128\cdot 7)+q\cdot 14)$ 。

代码