Codeforces7月解题报告

不定期更新

EDU Round 132

A、B水题

C. Recover an RBS

题意

给定一个长度为 $n$ 的包含"(" 、 ")“和”?“的括号序列，”?"可以转换成左括号或右括号，问是否有唯一对应的合法括号序列。

分析

统计出原括号序列中左右括号的数量$a,b$，则问号"?"要转换成的左右括号数量分别为$c=n/2-a,d=n/2-b$，那么将前$c$个问号都变成左括号，后$d$个问号都变成右括号是最优的。

之后考虑是否唯一。令左括号的权值为$1$，右括号的权值为$-1$，那么一个合法的括号序列满足任意一个位置前缀和$\geq 0$。

若将由问号变成的左括号$l$和右括号$r$交换位置，那么区间$[l,r-1]$之间的的前缀和都会减少$2$。交换最后一个左括号和第一个右括号产生的影响最小，最有可能成为第二个合法括号序列。check问号产生的最后一个左括号和第一个右括号交换产生的括号序列是否合法。

D. Rorororobot

题意

有大小为$n \times m$的棋盘（$n \leq 10^9, m\leq 2*10^5$），第$i$列的$[1,a_i]$行是禁区。若干个询问，给定初始位置和目标位置$s,t$和数字$k$，每次必须往一个方向走$k$步(不能走入禁区也不能走出棋盘外)，问是否能够停留在终点。

分析

由于禁区都是在较低的位置，那么首先从起点开始往上走到最高处，移动到终点对应列后往下走。判断能否走到终点对应列就是一个查询区间最值问题，线段树或RMQ都可解决。注意还要求列距离差和行距离差都是k的倍数。

E. XOR Tree

题意

大小为$n$的树，点权为$a_i$。定义一条路径$p$的权值为路径上所有点权的异或和。

要求修改最少个点的权值，使得不存在权值为$0$的路径。

分析

令$1$为树的根，定义$sum[u]$为：$u$到根路径上的点权的异或和。如果$(u,v)$两点路径的权值为$0$，则$sum[u] \bigoplus sum[v] \bigoplus a[lca]$

从下往上找权值为$0$的路径，如果我们修改$(u,v)$的lca的权值为$2^{inf}$，那么以$lca$为根的子树将无法和子树外的点构成权值为$0$的路径，因此是最优的。

从下往上找，使用set来保存子树中的$sum[v]$，如果某个点$u$的两个子树中存在$sum[v_1] \bigoplus sum[v_2] = a[u]$，那么修改掉$u$的权值，并且$u$不会对子树外构成影响，清空掉set[u]中的点。启发式合并子树，复杂度为$O(nlog^2n)$

F. Multiset of Strings

根据题意，可以建立一棵$01trie$字典树来解决。长度为$n$的字符串都是字典树的叶子。对于一个$01$字符串$s$和对应的$c_s$，在字典树上找到$s$对应的节点$u$，$u$的$c_s$表示子树中最多有$c_s$个叶子被选中。

定义状态$f[u][c]$表示：$u$节点的子树中设置限制的方案数使得恰好$c$个叶子被选中。有转移$(a, b, c)f[u][min(a, b + c)] += f[v_1][b] * f[v_2][c]$，a，b，c分别为$u$，$v_1$，$v_2$的限制$c_s$。这样转移的复杂度显然是不行的。
观察到$f[v_1][b]*f[v_2][c]$和$b+c$类似一个卷积形式，将两个子节点的$f$数组卷到$g$中，$g[d]$就表示不考虑点$u$的限制，子树中$d$个叶子被选中的方案数。之后通过前缀和优化来求出$f[u]$。这部分的复杂度为$O(flogf)$。考虑到字典树每一层的节点之间状态都是相同的，故只要做$n$次操作，复杂度为$O(nflogf)$。

---

CodeForces Round #810

A水题

B. Party

题意

原题等价于在图G中删去尽量少的点，使得边的数量为偶数。

分析

分类讨论

• 如果原图中边数为偶数，则不用删点
• 原图中的边数为奇数
  • 存在度数为奇数的点，删掉一个即可
  • 若不删去度数为奇数的点，则必须删掉两个相邻的度数为偶数的点，这样就能使得删去的边数为奇数。

在这些方案中取min

C. Color the Picture

又是一道讨论题。
根据样例提示发现，要满足条件，一种颜色必须占据连续的至少两行或两列。
这里只考虑列的情况，所有颜色能够占据的列数（只能占据一列的颜色不算）之和必须大于等于网格列数。
特殊情况：所有颜色都只能占据两列，并且网格列数为奇数，这种情况下有一种颜色必须占一列，不满足条件。

D. Rain

题意

在一维数轴上，分$n$天下雨。每天都以$x_i$为中心下雨，雨量为$p_i$，它对位置$j$水量的贡献为$max(0, p_i - |x_i - j|)$。一个地区的水位为$n$天的水量和。如果某个地区的水量超过$m$，则会发生洪水。
求让某一天不下雨，能够使得所有地区都不会发生洪水。

分析

我的做法比较复杂

很显然的结论：水位的最高处一定是某个$x_i$，那么我们只要让$n$个位置的水平不超过$m$。
先求出下$n$天雨后$n$个地区的水位。对于$j < x_i$，贡献为$max(0, p_i - x_i + j)$，将$p_i-x_i$放入$set$中，并反向统计，即可得到$j$位置后面的降雨对$j$的贡献。对于$j > x_i$，贡献为$max(0, p_i + x_i - j)$，将$p_i + x_i$放入$set$中，正向统计，即可得到$j$位置前面的降雨对$j$的贡献。

下一步就是枚举让第$i$天不降雨，求出所有地区的最大降水。我们可以类比上一步。这里将地区分为三个部分。1. 在$x_i$前面且降水受影响：$j < x_i \& j > x_i - p_i$, 2. 在$x_i$后面且降水受影响：$j > x_i \& j < x_i + p_i$, 3. 降水不受影响。这三部分都可以用线段树来维护。

E. XOR Triangle

题意

求$(a, b, c)$的数量，满足$0 \leq a, b, c \leq n$，并且$a \bigoplus b , b \bigoplus c, a \bigoplus c$能够组成三角形。

分析

显然$x \bigoplus y \leq x + y$。
若要形成三角形，必然满足其中一个条件：

$a \bigoplus b + b \bigoplus c > a \bigoplus c = a \bigoplus b \bigoplus b \bigoplus c$

那么肯定存在位$j$,$(a \bigoplus b)_j = (b \bigoplus c)_j=1$
有以下几种情况，满足一个即可

1. $a_j=c_j=1$, $b_j = 0$
2. $a_j=c_j=0$, $b_j = 1$

另外两对边的限制得出的结论同理。一共三组条件，必须满足三组条件（一组的子条件满足一个即可）才能形成三角形。

之后开始数位dp。$f[i][j][k]$表示第$i$位，$a,b,c$的上限$j$，三个条件的满足情况为$k$的数量。复杂度$O(N \times 8 \times 8 \times 8)$