Codeforces 题目选讲 2

Present

给出长度为$n$的序列$a$，求

$$\begin{aligned} \bigoplus_{1\le i<j\le n}(a_i+a_j) =&(a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ &\oplus (a_2 + a_3) \oplus \cdots \oplus (a_2 + a_n) \\ &\cdots \\ &\oplus (a_{n-1} + a_n) \\ \end{aligned}$$

$n\le 4\times 10^5,1\le a_i\le 10^7$。

摘要：逐位计算。

考虑按位计算答案。考虑计算答案的二进制第$k$位是否为$1$（$k$从$0$计数）。由于高于$k$的位不影响第$k$位的数，不妨设$a_i<2^{k+1}$。因此$a_i+a_j<2^{k+2}$。那么我们要计算的就是

$$\sum_{1\le i<j\le n}[2^k\le a_i+a_j<2^{k+1}]\text{ or }[2^{k+1}+2^k\le a_i+a_j<2^{k+2}]$$

的奇偶性。

不妨将$a$排序。枚举$j$，在序列上二分查找即可。

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

可以使用双指针 + 归并排序优化到$O(n\log_2n)$。

代码

Instant Noodles

给你一个$2n$个点的二分图，左部右部各$n$个点。有$m$条边。右部的点点权为$c_i$。

定义$f(S)$表示左部点集$S$的邻居集合（显然都是右部的点）定义$g(S)$表示$f(S)$中的点的点权和。

求$\gcd_{S\subseteq[n]}\{g(S)\}$。

$n,m\le 5\times 10^5,c_i\le 10^{12}$。

摘要：哈希判邻居集合是否相等。

由于是和的 GCD，因此我们关系的是：对于两个右部点$u,v$，他们是否同步出现（要么同时出现，要么同时不出现）。

如果两个点同步出现，那么我们就只用考虑它们的和。

推广之。若右部点集合$S$中的点均同步出现，则我们只用考虑$S$的点权和。

因此答案就是所有同步点集合的点权和的 GCD。

要判断右部点两个点是否同步出现，只需要判断它们的邻居集合是否相同即可。

若两个点的邻居集合不同，那么一定存在一个左部点集合使得这两个点没有同步出现。

使用哈希，时间复杂度$O(n+m)$。

代码

Reality Show

给出长度为$n$的序列$s$和$l$，给出一个长度为$n+m$的序列$c$。

你可以构造一个长度为$k(k\le n)$的序列$p$满足：

1. $1\le p_i<p_{i+1}\le n$（单增）；
2. $l_{p_i}\ge l_{p_{i+1}}$（非严格单减）。

然后你需要对$p$和一个集合$S$做这样的操作：以$i=1,2,\cdots,k$的顺序考虑$x=l_{p_i}$：

1. 你会获得$c_x$的奖励；
2. 若$x\notin S$，把$x$加入$S$并结束这次操作；否则把$x$从$S$中删除，并令$x\gets x+1$。

你的得分是奖励之和减去$\sum_{i=1}^k s_{p_i}$。

请构造满足条件的$p$并最大化得分。输出得分。

$1\le n,m\le 2000,1\le l_i\le m,0\le s_i\le 5000,|c_i|\le 5000$。

摘要：倒序 DP。

首先注意到在第二步操作的时候，你以任意顺序操作$l_{p_i}$，得分不变。

而我们操作的过程实际上可以看做是二进制的进位过程。

那么我们考虑倒着构造$p$。那么我们每次构造的就是当前序列中$l_{p_i}$最大的元素。

考虑 DP。设$f(i,j)$表示$l_{p_x}$最大值为$i$，且$l_{p_x}=i$的人有$j$个时的最大得分。

若我们在$p$的开头插入$i$（即新的$p_1=i$），那么就可以对$f(l_i,j)$做一次背包：

$$f(l_i,j)\gets f(l_i,j-1)-s_i+c_{l_i}$$

另一方面，$f(x,j)$在$j>1$的时候可以进位到$f(x+1,\lfloor\frac{j}{2}\rfloor)$。但是不是所有$f(x,j)$都需要进位。因为我们只改变了$f(l_i,j)$，因此只需要对$x\ge l_i$的部分进位即可。另一个事情是，$f(l_i,j)$会贡献到$f(l_i+1,\lfloor\frac{j}{2}\rfloor)$，则$j$的范围每次除以 2。因此 DP 转移的复杂度是$O(n+m)$的。

总复杂度$O(n(n+m))$。

代码

AND Segments

给出$n,k,m$和$m$个限制$(l_i,r_i,x_i)$。问有多少长度为$n$的序列$a$满足

1. $0\le a_i<2^k$；
2. $\forall1\le i\le m, a_{l_i}\operatorname{bitand} a_{l_i+1}\operatorname{bitand}\cdots\operatorname{bitand}a_{r_i}=x_i$；

$1\le n\le 5\times 10^5,1\le k\le 30,0\le m\le 5\times 10^5$。

按位考虑。限制转化为，一段区间全 1，一段区间至少有一个 0。设$f(i)$表示前$i$个数且满足与前$i$个位置相交的限制的方案数。转移时枚举上一个$0$的位置即可。可以前缀和优化。复杂度$O(nk)$。

然而要注意的是，有关区间包含的去重问题一定要三思。千万记住：不要只比相邻的！不要 ban 掉前面的，应该是 ban 掉你当前的这个区间。注意枚举顺序。

代码

Bombs

你有一个排列$p_i$。你有一个 01 序列$v_i$。对$(p,v)$进行一次操作为：考虑$i=1,2,\cdots,n$：

1. 把$p_i$插入到集合中；
2. 如果$v_i=1$，就把集合中最大的数删除。

最后集合中剩下的数就是操作结果（如果有）。

现在给出排列$p$和$q$。设序列$v_i$初始为$0$，要求你对$i=1,2,\cdots,n$：

1. 求出$(p,v)$操作的结果并输出；
2. 令$v_{q_{i}}\gets 1$（増加一个 bomb）。

$n\le 3\times 10^5,1\le p_i,q_i\le n$。

随着 bomb 的增加，答案是不会增加的（不可能有数字复活）。

考虑排列中一个数$x$，假设$p_u=x$。那么在什么条件下答案$<x$？

所有大于等于$x$的数都被删。也就说，$p$中最靠右的$\ge x$的数的右边至少有一个 bomb，第二靠右的$\ge x$的数右边至少有 2 个 bomb，以此类推。

可以把$\ge x$的数的位置 +1，bomb 出现的位置 -1。那么条件就转化为，所有的后缀和都小于等于$0$。

如果答案$<x$，那么我们就把$x$减 1 并继续检查答案是否小于$x$。

线段树维护后缀和即可。

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

代码

Wise Men

给一个$n$个点简单无向图$G=(V,E)$。

对于长度为$n$的排列$p$，我们可以构造一个长度为$n-1$的 01 串$s(p)$：$\forall 1\le i<n,s_i=[(p_i,p_{i+1})\in E]$。

现在对于所有$2^{n-1}$个长度为$n-1$的 01 串$S$，求$s(p)=S$的排列$p$的个数。

$2\le n\le 18$。

考虑容斥。容斥 01 串中的 0，用无限制减去强制为 1 的情况。也就是说，$f(S)$表示答案，则$g(S)=\sum_{S\subseteq T}f(T)$。我们考虑求$g(S)$。

$g(S)$可以理解为是，用若干条路径覆盖$n$个点的方案数。其中每条路径的长度的给定的。比如$g(11001011)$表示用长度分别为$1,2,3,3$的路径覆盖$n$个点的方案数（换一种说法，就是$g(11001011)=g(11010011)$，因为他们对应的路径长度集合都是$\{1,2,3,3\}$）。

因此$g(S)=G(A)$，其中$A$表示路径长度集合。我们可以考虑求$G(A)$。$A$的个数是拆分数，而$P(18)=385$，复杂度可以接受。

不妨先求出$f(x,S)$，表示用长度为$x$的路径精确覆盖点集$S$的方案数（哈密尔顿路径）。这个可以 DP 求出。那么$G(A)$可以理解为是$\prod f(x,S_i)$，其中$x\in A$，且$S_i(1\le i\le |A|)$精确覆盖全集$[n]$。由于的精确覆盖，因此本能地想到是不相交的或卷积。然而注意到我们只需要知道$2^n-1$处的点值，因此普通的或卷积也是足够的（如果集合出现交集，则这种方案无法对$2^n-1$的点值做贡献）。

因此$G(A)$就是$f(x)(x\in A)$的或卷积的$2^n-1$处的点值。这样我们对于每个路径长度集合$A$都可以计算出答案。

然后我们再枚举 01 串，求出它的路径集合即可。

最后容斥（FMT）回去。

时间复杂度$O((?\times P(n)+n^2)2^n)$。$?$表示拆分出的部分的个数。能过。当然，也是可以优化的。优化就是在 DFS 枚举集合的时候顺便 FMT。

代码

Sum of Prefix Sums

给你一棵带点权无根树$T=(G,E)$。点权为$a_i$。定义一条路径$P(u,v)=\{i_1=u,i_2,\cdots,i_k=v\}$的权值为$\sum_{j=1}^k a_{i_j}j$。求权值最大的路径的权值。

$2\le n\le 150000,1\le a_i\le 10^6$。

摘要：点分治，李超树。

考虑点分治。

容易想到把路径$i_1,\cdots,i_k$分成前后两部分：$i_1,\cdots,i_m$和$i_{m+1},\cdots,i_k$。那么两部分的权值分别为$\sum_{j=1}^ma_{i_j}j$和$m\cdot \sum_{j=1}^{k-m}a_{i_{m+j}}+\sum_{j=1}^{k-m}a_{i_{m+j}}j$。前者可以用$(x_1=\sum_{j=1}^ma_{i_j}j,y_1=m)$表示，后者可以用$(x_2=\sum_{j=1}^{k-m}a_{i_{m+j}},y_2=\sum_{j=1}^{k-m}a_{i_{m+j}}j)$表示。因此整条路径的权值为$x_1+y_1x_2+y_2$。

对于每个结点我们都可以计算出它到分治中心的路径对应的$(x_1,y_1)$和$(x_2,y_2)$。因此我们要选择两个不同子树的$(x_1,y_1)$和$(x_2,y_2)$来更新答案。

考虑用数据结构维护$(x_2,y_2)$的集合。然后用$y_1$查询。那么这就是维护若干个一次函数，查询单点最大值的问题。可以使用李超树。可以标记永久化。

同时我们要求是不同子树。因此对于一个子树，先查再插入即可。然后再倒着做一遍处理反向的情况。

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

李超树的复杂度：在一个线段树区间上插入一条直线的复杂度是$O(\log_2n)$的。但是我们每次都是在根结点的区间上插入。因此总复杂度是$O(n\log_2^2n)$的。

代码

No Monotone Triples

对于一个序列$a$，如果$\forall 1\le i<|a|, a_i\le a_{i+1}$或者$\forall 1\le i<|a|, a_i\ge a_{i+1}$，那么称$a$是单调序列。

若序列$a$不含长度大于等于$3$的单调子序列，则称$a$是 no-triple 序列。

给出长度为$n$的序列$a$。$q$次询问$(L,R)$，询问区间$[L,R]$的最长 no-triple 子序列。

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

手玩一下可以发现，no-triple 的长度最大为 4。

考虑对于每个$i$（$1\le i\le n$），求出最小的$j$使得$[i,j]$里有长度为 4 的 no-triple（长度为 3 的 no-triple 是类似的）。

那么条件可以转化为，求出最小的$j$使得$[i,j]$中存在$i<x,y<j,x\ne y$使得$a_x>\max(a_i,a_j)$，$a_y<\min(a_i,a_j)$。

首先我们找到$a_i$右边第一个比$i$大的数。记为$a_p$。

并且找到$a_i$右边第一个比$i$小的数。记为$a_q$。

那么显然，$j>\max(p,q)$。

另一方面，我们维护$i$的两个非严格单调栈。设$P_i$表示$a_i$右边第一个大于等于$a_i$的位置（即$P_i = \min \{j\mid a_j\ge a_i,j\ge i\}$）。$Q_i$表示第一个小于等于。那么第一个栈中存储的就是$\{i,P_i,P_{P_i},\cdots,P^{\circ k}_i \}$，第二个栈中存的就是$\{i,Q_i,Q_{Q_i},\cdots,Q^{\circ k}_i \}$。

显然$j$不能在任何一个栈中。不然就找不到比$a_j$大的（或者找不到比$a_j$小的）数了。

上面的这两个条件，是否是$j$的充分条件？是的。

也就是说只要满足这两个条件，就一定能在$[i,j]$中找到$x,y$满足 no-triple 的条件。

因此我们只需要找到满足这两个条件的最小的$j$即可。

构造方案：容易发现，一定存在方案使得$x,y$分别在两个栈中。因此在栈上二分即可。

长度的 3 的 no-triple 是类似的。

然后我们离线，后缀$\min$即可。

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

代码

Dreamoon Likes Strings

你有一个字符串$s$。每次你可以删除$s$的一个子串$t$，满足$t$中不存在相邻相同字符。删完后两边自动拼在一起。问最少多少次可以把$s$删完。并输出方案。

$|s|\le 2\times 10^5$。

考虑把$s$中相邻相同字符都写下来。比如abbccddacdbbb可以写出bcdbb，记为$s'$。那么你删一个子串肯定是删一个极长的子串。于是可以发现，你的删除操作等价于：

1. 在$s'$中删除开头或者末位一个字符；
2. 在$s'$中删除两个相邻但不同的字符；
3. 在$s'$中删除一个字符，且这个字符旁边存在与它相同的字符。

如果$s'=\varnothing$，那么我们就可以再删一次把$s$删光。

那么我们肯定会先尽量使用 2 操作，多删几个字符。然后使用 1 操作。这就转化为一个经典问题：每次匹配两个不同类型的元素。问最多匹配多少个。设总数为$x$，同类的最大数量为$y$。则答案显然为$\max(\lfloor\frac{x}{2}\rfloor,y)$。而现在的问题是我们还需要构造出方案。

1. 如果$2y\ge x$，那么很容易构造方案。我们把其他的都往$y$上“贴”就行。
2. 如果$2y<x$。那么我们可以先随便搞。即遍历一遍，遇到相邻不同字符就双双删除。直到$2y=x$或者$2y=x-1$的时候就 break。这时就转化为了情况 1 了，于是再构造一下剩余的方案即可（当然在删除过程中，可能有别的类会变成$y$）。

要注意细节的处理。

代码

On the Bench

给你一个长度为$n$的序列$a$。问有多少个长度为$n$的排列$p$满足$\forall 1\le i<n$，$a_{p_i}a_{p_{i+1}}$不是完全平方数。

$n\le 300,a_i\le 10^9$。

首先注意到，若$ab$和$bc$都是完全平方数，则$ac$也是完全平方数（传递性）。

因此问题转化为：有$n$个带标号的球，每个球有一个颜色。你要把他们排成一排且相邻的球颜色不同。求方案数。

考虑容斥。同色不相邻 = 无限制 - 同色相邻。而同色相邻，可以理解为是把两个球捆在一起。

考虑 DP。设$f(i,j)$表示前$i$种球，有$j$个同色相邻的方案数。答案就是$\sum f(m,i)(-1)^i$（假设一共$m$种颜色）。

设第$i$种球有$x$个。那么我们可以枚举颜色$i$的相邻的个数，假设是$k$。那么这样的方案数是$\binom{x-1}{k}x!$。然后考虑背包的合并，相当于把$x$个球插板。

时间复杂度$O(n^2)$。

代码

Kate and imperfection

设$S=\{1,2,\cdots,n\}$。

对于$S$的子集$T$，设$f(T)=\max \{\gcd(x,y)\mid x,y\in T,x\ne y\}$。

对于$i$（$1<i\le n$），求出$S$的所有大小为$i$的子集$T$中，$f(T)$的最大值。

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

考虑$f(T)\ne x$的条件是什么？必要条件：$x,2x,\cdots,\lfloor\frac{n}{x}\rfloor x$中至多有一个数在$T$中。如果要选一个数，显然我们会贪心地保留$x$，删掉$x$的倍数。

因此如果我们想删掉尽量少的数使得$f(T)\ne x$，则$x$的倍数必须全部被删。

因此如果要求$f(T)<x$，则$x,x+1,\cdots,n$的倍数都要被删。不妨计算出$b_i$表示要让$f(T)<i$，至少要删掉多少个数。即，要让$f(T)<i$，最多存在多少个数。

充分性：另一方面，如果存在$x$和$x$的倍数，那么$f(T)$至少是$x$。

然后就简单遍历一遍统计答案即可。

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

代码

Road to 1600

把$1,2,\cdots,n^2$依次填入$n\times n$的方格中。然后你需要访问每个格子恰好一次。有两种访问方式。

Rook 式：

1. 从$1$所在方格开始；
2. 如果与它同行 / 同列中存在未被访问过的格子，选择一数字最小的格子走过去；
3. 否则，从未访问过的方格中选择一个数字最小的方格并走过去。花费$1$个代价。

Queen 式：

1. 从$1$所在方格开始；
2. 如果与它同行 / 同列 / 同对角线（两个方向）中存在未被访问过的格子，选择一数字最小的格子走过去；
3. 否则，从未访问过的方格中选择一个数字最小的方格并走过去。花费$1$个代价。

现在要求你构造一种填数方案，使得 Rook 式的代价严格小于 Queen 式的代价。

$n\le 500$。

考虑暴搜出小方格的情况。然后其他地方你构造成 Queen 和 Rook 走一样的路线。最后引导到这个小方格即可。

暴搜就随机一个$n^2$的排列然后 check。

暴搜代码

代码