Codeforces 题目选讲 1

本文主要讲解一些近期遇到的一些有启发意义的 Codeforces 题目。不定时更新。

Anu Has a Function

定义$f(x,y)=(x\operatorname{bitor}y)-y$。

给你一个长度为$n$的序列$A$，你可以随意安排顺序，最小化

$$F(A)=f(f(\cdots f(f(A_1,A_2),A_3)\cdots)A_n)$$

$n\le 10^5,A_i\le 10^9$。

摘要：理解位运算。

容易发现$f(x,y)=x\operatorname{bitand}(\operatorname{not}y)$。相当于在$x$中把属于$y$的部分挖掉。

因此$F(A)$的值只和$A_1$的值有关。

把复杂度做到$O(n\log_2n)$即可。

代码

Aerodynamic

给你一个凸多边形$A$。

定义凸多边形函数$P(A)$：

1. 随便固定一个点$(x_0,y_0)$。
2. 在保证$(x_0,y_0)\in A$（即在$A$的边界或内部）的情况下$A$随便平移，尽可能经过多的点（覆盖多的面积）。所经过的点的集合构成多边形$P(A)$。

问$A$与$P(A)$是否相似。

$n\le 10^5$。

摘要：大力猜结论。

如果$A$是正三角形的话，$P(A)$就是正六边形。

容易发现，当$n$是奇数时$P(A)$有$2n$条边，与$A$不相似。

为了不产生多余的边，就要求$A$的对边平行且相等（第$i$条边和第$i+\frac{n}{2}$条边平行且相等）。感性理解不难。

大力猜想这是重要条件。

复杂度$O(n)$。

代码

Water Balance

给你一个长度为$n$的序列$A$。每次你可以把$A[l,r]$的元素都变成$\frac{1}{r-l+1}\sum_{i=l}^r A_i$（变成平均数）。

问能操作出的字典序最小的$A$序列是啥。

$n\le 10^6,a_i\le 10^6$。

摘要：贪心，复杂度均摊。

由于是字典序最小，因此我们从前往后依次考虑。

如果$A_i\le A_{i+1}$就不管。

如果$A_i>A_{i+1}$，显然我们一定会以$A_i$为左端点做一次操作。但是这次操作的区间有多长？我们可以一直向右延伸，如果平均值变小就延伸，如果变大就停止延伸，然后把这段区间给操作一次。

操作完之后，我们还可以找到$A_{i-1}$，如果$A_{i-1}>A_i$，就把左端点往左延伸一点然后进行一次操作。毕竟我们要求字典序最小。直到不存在$A_{i-1}>A_i$的情况位置。

然后我们跳过这一段区间做后面的事。

但事实上这么做了一轮之后不一定字典序就最小了。还可以做第二轮第三轮。

可以使用链表缩点优化。

稍作感知，认为做的次数不会很多。

代码

Animal Observation

题面较长。但样例的图十分可读。

摘要：DP 优化。

设$f(i,j)$表示前$i$行，其中第$i$行选择从第$j$列开始的矩形（占据$i,i+1$两行）的最大值。

$f(i)$从$f(i-1)$转移。

$f(i,j)$从$f(i-1,k)$转移。根据$|j-k|$的关系可以分类讨论。

容易发现，使用前缀$\max$，后缀$\max$和单调队列就可以分别优化了。

时间复杂度$O(nm)$。

代码

Cow and Fields

给你一个$n$个点$m$条边的无向简单图。有$k$个关键点。要求你必须在$k$个关键点中选择两个点连一条边。

最大化$1$到$n$的最短路。

$n\le 2\times 10^5,n-1\le m\le 2\times 10^5,2\le k\le n$。

摘要：转化为数学模型。

设$p_u$表示$1$到$u$的最短路，$q_u$表示$u$到$n$的最短路。

对于两个关键点$x,y$，如果加入并强制走$(x,y)$这条边，则最短路是$\min(p_x+q_y,p_y+q_x)$。

因此我们要求的是

$$\max_{x,y}\min(p_x+q_y,p_y+q_x)$$

不妨设$p_x+q_y\le p_y+q_x$，即$p_x-q_x\le p_y-q_y$，则我们要求的是

$$\max_{p_x-q_x\le p_y-q_y}\{p_x+q_y\}$$

可以前缀后缀$\max$在$O(k\log_2k)$的时间统计出来（算上了排序的时间）

然后再和$p_n$比较一下即可。

时间复杂度$O(n+k\log_2k)$。

代码

Cow and Treats

题面较长

摘要：观察，分析，发现左边和右边不能相交。于是枚举分割位置然后计算。

观察发现：

1. 同一种颜色（sweetness）最多选 2 头牛（分别从左右两个方向出发）。
2. 左边走的最远的牛和右边走的最远的牛不能碰面。
3. 一但安排好了两个集合，只要满足上面两个条件，那么一定可以按要求使得所有牛都睡觉。

于是我们枚举左边的牛走的最远的走到哪里。然后对每个颜色统计放的最多的方案数并更新答案即可。

代码

Cow and Vacation

给一个$n$个点的树，有$r$个休息点（关键点）。你在不休息的情况下最多连续走$k$条边。你走到一个休息点后就可以休息好，继续走最多$k$条边。$q$次询问，能否从$a_i$走到$b_i$。

摘要：两边 BFS，并查集。

一开始想了一个虚树 + 并查集 + 点分治的思路，难想又难写。所以就不讲了。

基本的思路是：我们把距离休息点$\frac{k}{2}$以内的点和休息点 merge。那么如果两个休息点距离小于等于$k$，他们就会 merge 到一起。询问的时候先判距离以及是否在同一个集合。否则就相向而行各走$\frac{k}{2}$步。如果走到这里了都不能走到一个集合里，说明不行（注意，我们是把距离休息点$\frac{k}{2}$以内的点和休息点 merge 过的，因此如果走$\frac{k}{2}$步后不能走到一个休息点上，就说明不行）。

merge 就用并查集做。我们事先把每条边中间加一个二度点（距离乘$2$），这样就不用考虑$k$的奇偶性了。然后走$k$步的时候相当于倍增跳祖先。

时间复杂度$O((n+q)\log n)$。

代码

Reachable Strings

对于一个 01 串你可以进行以下两种操作：

1. 选择一个110并将其替换为011；
2. 选择一个011并将其替换为110；

给你一个串$S$，有$q$次询问$(l_1,l_2,len)$，问你$S[l_1,l_1+len-1]$能否通过若干次操作变成$S[l_2,l_2+len-1]$。

$n\le 2\times 10^5$。

摘要：根据一段 1 个数的奇偶性给 0 分段。然后做字符串匹配（哈希或者 SA）。

上面的操作可以理解为是，一段偶数个 1 可以随意穿梭在 0 之中。因此我们把连续的偶数个 1 可以直接删掉。那么就剩下了一个 01 串使得每一段连续的 1 只有一个 1。

那么我们把每段 0 的个数写成一个序列，这就等价于问你两个序列是否相等。

可以使用 SA 或者哈希计算。

时间复杂度$O(n\log_2n)$或$O(n)$。

考场上抽风，写了一个线段树 + 哈希，最后还没交上去，不知道在想啥。

代码 仅供对拍，不建议学习。

Treeland and Viruses

题面较长。

摘要：建虚树，跑多源最短路。

注意，最短路以到达时间（不是路程）为第一关键字，病毒编号为第二关键字。

代码

Kuroni and the Score Distribution

给出$n,m$。构造长度为$n$的序列$a$满足：

1. $1\le a_1<a_2<\cdots<a_n\le 10^9$。
2. $(\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n [a_i+a_j=a_k]) = m$。

$n\le 5000,m\le 10^9$。

摘要：构造。

当时做这题时，读错题了，以为是求构造的方案数。把我自闭了半小时。

首先思考，如何构造使得最大化$\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n [a_i+a_j=a_k]$？构造$\{1,2,\cdots,n\}$即可。

因此我们依次构造，让$a_i+a_j=a_k$的数量接近$m$。然后把下一个数字稍微改一下使得刚好凑出$m$。然后我们要求剩下的数字不能有任何$a_i+a_j=a_k$的情况出现。那么构造$a_i=10^9-5000n+5000i$即可。乘$5000$的原因是避免与前面构造的产生$a_i+a_j=a_k$。

无解的情况稍微判一下。

代码

Kuroni and the Punishment

给出长度为$n$的序列$a$，要求你构造长度为$n$的正整数序列$b$使得$\gcd_{i=1}^n\{b_i\} >1$，且最小化$C=\sum_{i=1}^n |a_i-b_i|$。

求出这个最小化的$C$。

$1\le a_i\le 10^{12},n\le 2\times 10^5$。

摘要：乱搞。

如果确定了$g=\gcd_{i=1}^n\{b_i\}$，那么我们可以$O(n)$求出最小的$C$。

令$g=2$，易得$C\le n$。因此若$g>2$，$g$一定是某个$a_i$的约数。同时易证，存在$g$是质数（质因子）的最优解。

好接下来开始乱搞。我们的大致思路是随机几个质数$g$出来更新答案。但是不能乱随。

由于$C\le n$，因此我们就随机几个$a_i$，把$a_i-1,a_i,a_i+1$的质因子都拿出来更新答案。

可以证明，错误的概率是指数级减小的（$2^{-k}$）。

要去重后再更新。

代码

Kuroni and Antihype

有$n$个数$a_i$和一个集合$S$。你可以进行两种操作：

1. 把$x$（$1\le x\le n$）加入$S$，没有奖励；
2. 选择$S$中的一个数$x$和不在$S$中的一个数$y$，且$a_x\operatorname{and}a_y=0$，把$y$加入$S$，奖励为$a_x$。

要求你把$\{1,2,\cdots,n\}$都加入到$S$中，求出最大化的奖励的和。

$1\le n\le 2\times 10^5,0\le a_i\le 2\times 10^5$。

设$a_0=0$，一开始$S$中有$0$。那么所有的 1 操作可以转化为$x=0$的 2 操作。

容易发现，所有的 2 操作构成一个以$0$为根的有根树。

设树上结点的度为$d_i$。那么我们的奖励显然为$\sum_{i=0}^n(d_i-1)a_i$。

注意到$\sum_{i=0}^n(d_i-1)a_i=\sum_{i=0}^nd_ia_i-\sum_{i=0}^na_i$。

考虑最大化$\sum_{i=0}^nd_ia_i$。这等价于加权无向图

$$\begin{aligned} G &= (V,E)\\ V &=\{0,1,\cdots,n\}\\ E &=\{(i,j) | 0\le i<j\le n,a_i\operatorname{bitand}a_j=0 \}\\ w(i,j) &=a_i+a_j \end{aligned}$$

中的最大生成树的边权和（注意，这和上文中的有根树没有任何关系，因为我们已经把问题转化为最大化$\sum_{i=0}^nd_ia_i$了）。

考虑使用 Boruvka 算法 求最大生成树。

那么我们的问题转化为，如何求与$i$相邻的权值最大的边$(i,j)$且$i,j$不在同一连通块。可以使用子集前缀和解决，记$c_x$表示满足$y_1\operatorname{and}x=y_1$且$a_{y_1}$最大的$y_1$，$d_x$表示次大的，记作$y_2$，且$y_1,y_2$不在同一连通块。这个可以 FMT 求出。然后我们就可以$O(1)$求出与$i$相邻的权值最大的边$(i,j)$了。

时间复杂度$O(W\log_2W\log n)$，其中$W=2^{18}$，表示值域。

代码