【总结】联合省选题目选做

省选联考 $2021$

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

题目描述

Alice 有 $n$ 张卡牌，第 $i$（$1 \le i \le n$）张卡牌的正面有数字 $a_i$，背面有数字 $b_i$，初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 $m$ 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 $n$ 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。

数据范围

\(3\le n\le 10^6,1\le m 。

key idea : 极差的本质是限定值域大小，$\forall a_i\in [l,r],r-l+1\le len$ 。

题解 1 （二分 + 双指针）：

首先，在最优解中我们只会翻一个前缀 / 后缀，若我们翻了位置 $1 且没有翻 \(i-1$,$i+1$ 那么对其造成的影响要么是最大的变大，要么就是最小的变小。

考虑二分答案，每次 check 是否存在一种合法的翻牌方案使得极差小于等于 $val$ 。

直接枚举翻牌方案，很难确定合法的翻牌的后缀。

问题的本质是，我们要找到一种翻牌方案，使得朝上的数字均在值域 $[l,r],r-l+1\le val$ 内。

对于固定的值域，在值域内的 $a$ 我们是不需要翻的，剩下的我们只需要看要翻的位置的 $b$ 是否在值域内。

因此，我们的值域越大越好，因此枚举值域左端点一定可以唯一确定值域最大的右端点。

将所有的 $a$ 和 $b$ 排序之后，对于每次 check 枚举值域即可。

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

题解 2 （排序 + 双指针）：

我们考虑将所有的 $a$ 和 $b$ 排序后，预处理 $b$ 的前后缀 $\min,\max$ ，每次在值域上双指针。

双指针正确的前提：

如果值域 $[l_1,r_1]$ 是合法的值域，那么值域 $[l_2,r_2] ,l_2\le l_1 \le r_1\le r_2$ 一定也是合法的值域。

双指针求最优解：

初始化 $l,r$ 为包含 $a,b$ 的极大值域。
枚举值域左端点，因为要求最优解所以右指针不应当向右移动，$r$ 移动到最左的满足 $l,r$ 是合法值域的位置。

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

P7515 [省选联考 2021 A 卷] 矩阵游戏

题目描述

Alice 有一个 $n \times m$ 的矩阵 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le m$），其每个元素为大小不超过 ${10}^6$ 的非负整数。

Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i, j}$（$1 \le i \le n - 1$，$1 \le j \le m - 1$），每个元素的生成公式为

\[b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1} \]

现在 Alice 忘记了矩阵 $a_{i, j}$，请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。

数据范围

$1\le T \le 10,2\le n,m\le 300,0\le b_{i,j}\le 4\times 10^6$ 。

题解（差分约束）：

key idea : 对于这种 $2\times 2$ 的子矩阵的限制可以考虑确定第一行与第一列的状态，从而（唯一）确定整个矩阵。

不考虑 $a_{i,j}$ 元素大小的限制，我们考虑直接确定 $a$ 的第一行元素和第一列元素。

这样，我们就可以唯一确定所有的 $a_{i,j}$ 。

我们发现确定第一行元素和第一列元素和满足 $b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}$ 的矩阵 $a$ 是双射关系。

我们发现，如果我们要给第一行或第一列的某一个位置 $+1$ 或 $-1$ 对整个矩阵的影响为：

选一行或者一列 $+1 - 1 + 1 - 1 ...$ 或者 $-1 +1 -1 +1 ....$ 。

令目标方案为 $c_{1,1},c_{1,2}...c_{1,m}$ 与 $c_{1,1},c_{2,1},...,c_{n,1}$ ，当前方案为 $a_{1,1},a_{1,2}...a_{1,m}$ 与 $a_{1,1},a_{2,1},...,a_{n,1}$

我们可以通过如下步骤将任意一个确定第一行与第一列的方案，“调整” 成目标方案：

先通过将第一行与第一列进行 $+1 - 1 + 1 - 1 ...$ 或 $-1 +1 -1 +1 ....$ 。
接下来对其余行与列对应的行 / 列进行 $+1 - 1 + 1 - 1 ...$ 或 $-1 +1 -1 +1 ....$ 。

可以发现在第二步中，不同的行列相互不影响。

注意到，对于任意一个位置 $(i,j)$ 只会被 “调整” 两次。

那么 $a_{i,j}$ 调整后的取值 $c_{i,j}=a_{i,j} \pm P_i \pm Q_j$ 。

那么有不等式组：$0\le a_{i,j} \pm P_i \pm Q_j \le 10^6$ 。

然而这并不仅有我们熟知的 差分约束 ，还有 “和分约束”，并且符号我们是确定不了的，怎么办呢？

一种理想的确定符号的方式是棋盘黑白染色：

\[\text{行} \begin{bmatrix} + & - & + & -\\ - & + & - & +\\ + & - & + & -\\ - & + & - & +\\ \end{bmatrix} \]

\[\text{列} \begin{bmatrix} - & + & - & +\\ + & - & + & -\\ - & + & - & +\\ + & - & + & -\\ \end{bmatrix} \]

但是这样是否能够达到任意状态呢？

如果没有差分约束 $\forall x\ge 0$ 或者 $\forall x\le 0$ 的限制，其是很好证明的（因为不同的行和列是独立的）。

引理：对于一组形如 $x_i-x_j\le a_k$ 的不等式组存在一组解，那么一定可以用差分约束求解出一组 $\forall x \ge 0$ 或 $\forall x \le 0$ 的一组解。

黑白染色后，可以保证其符号是不同的。

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

P7516 [省选联考 2021 A/B 卷] 图函数

题目描述

对于一张 $n$ 个点 $m$ 条边的有向图 $G$（顶点从 $1 \sim n$ 编号），定义函数 $f(u, G)$：

初始化返回值 $cnt = 0$，图 $G' = G$。
从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G'$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt + 1$，并在图 $G'$ 中删去顶点 $v$ 以及与它相关的边。
第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 $G$，请你求出 $h(G) = f(1, G) + f(2, G) + \cdots + f(n, G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1 \le i \le m$），请你求出所有 $h(G_i)$ 的值。

数据范围

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

题解 ( $O(n^3)$ 动态加边传递闭包 )

我们将计算 $f(u,G)$ 的过程重新描述一下：

初始化返回值 $cnt = 0$，图 $G' = G$ ，集合 $S_{u,G} = \emptyset$。
从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G'$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt + 1$，$S_{u,G} \gets S_{u,G} \cup $ , 其中  是有序点对，并在图 $G'$ 中删去顶点 $v$ 以及与它相关的边。
对于任一有序点对 $\in S_{u,G}$ ，一定有 $v\le u$ 。
有 $f(u,G)=cnt=|S_u,G|$ 。
因为任意两个不同的 $u$ ,$S_{u,G}$ 不交，所以有 $h(G)=|\bigcup_{1\le u\le n} S_{u,G}|$ 。
定义集合 $H(G)=\bigcup_{1\le u\le n} S_{u,G}$ 。

考虑点对 $ \in H(G)$ 的条件：

当且仅当图 $G$ 中存在路径 $u\to v$ 满足路径上编号最小的点的编号为 $v$ ，且存在路径 $v\to u$ 满足路径上编号最小的点的编号为 $v$ 。

动态删边不是一个好做的条件，我们将其转化为倒着加边。

令 $f[x][y]$ 为点 $x$ 到点 $y$ 路径上编号最小的点的编号最大是多少。

动态加边更新这个数组即可。复杂度 $O(n^2m)$ 可以拿到 $44$ 分。

但是这个做法接着往下想是很没用前途的。

令图 $G_i'\gets G_{m-i+1}$ 。

我们考虑一个点对  哪些集合 $H(G_i')$ 中。

我们考虑固定 $G$ 去求 $H(G)$ 的暴力做法：

从后往前枚举 $v$ 每次枚举一个 $u$ 查询 $v$ 是否可以到达 $u$ , $u$ 是否可以到达 $v$ 。

而对于 “只有加边的动态传递闭包问题” 中，我们有一个建图技巧：

对于第 $i$ 条插入的边 $(u_i,v_i)$ ，建边 $(u_i,v_i,i)$ 。

那么每次相当于 $u$ 到 $v$ 路径上最大的边权最小是多少。

对于该问题，我们采用类似地建边方法，即将边 $(u_i,v_i)$ 建成 $(u_i,v_i,i)$ 。

那么跑动态加点的 $\text{floyd}$ 即可（复杂度 $O(n^3)$ ），卡卡常可以过。

卡常小技巧（可以节约近一半的常数）：

for (int x = n; x >= 1; x--) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= (i>x?x:n); j++)
			f[i][j] = std::max(f[i][j],std::min(f[i][x],f[x][j]));
}

P7519 [省选联考 2021 A/B 卷] 滚榜

题目描述

封榜是 ICPC 系列竞赛中的一个特色机制。ICPC 竞赛是实时反馈提交结果的程序设计竞赛，参赛选手与场外观众可以通过排行榜实时查看每个参赛队伍的过题数与排名。竞赛的最后一小时会进行“封榜”，即排行榜上将隐藏最后一小时内的提交的结果。赛后通过滚榜环节将最后一小时的结果（即每只队伍最后一小时的过题数）公布。

Alice 围观了一场 ICPC 竞赛的滚榜环节。本次竞赛共有 $n$ 支队伍参赛，队伍从 $1 \sim n$ 编号，$i$ 号队伍在封榜前通过的题数为 $a_i$。排行榜上队伍按照过题数从大到小进行排名，若两支队伍过题数相同，则编号小的队伍排名靠前。

滚榜时主办方以 $b_i$ 不降的顺序依次公布了每支队伍在封榜后的过题数 $b_i$（最终该队伍总过题数为 $a_i + b_i$），并且每公布一支队伍的结果，排行榜上就会实时更新排名。Alice 并不记得队伍被公布的顺序，也不记得最终排行榜上的排名情况，只记得每次公布后，本次被公布结果的队伍都成为了新排行榜上的第一名，以及所有队伍在封榜后一共通过了 $m$ 道题（即 $\sum_{i = 1}^{n} b_i = m$）。

现在 Alice 想请你帮她算算，最终排行榜上队伍的排名情况可能有多少种。

数据范围

$1\le n\le 13,1\le m\le 500,0\le a_i\le 10^4$ 。

题解 1 （60pts 枚举排列 + 贪心）

key idea:对于 $\sum b_i =m$ 的限制考虑转化为 $\sum b_i \le m$ 的限制从而转化成求最小的 $\sum b_i$ 。

考虑 $O(n!)$ 枚举排列，每次 check 是否存在一种方案满足最后排名情况为该排列。

若我们当前枚举的排列为 $p$ ，注意到，最终公布的 $b_{p_i}$ 随 $i$ 单调不增，且公布顺序为最终结果的倒序。

对于 $b$ 的限制有两条：

最终公布的 $b_{p_i}$ 随 $i$ 单调不增。
$\sum b_i =m$ 。

而如果存在一种方案满足 $\sum b_i \le m$ 那么，我们一定可以通过给 $b_{p+1}$ 疯狂叠加给调整到 $\sum b_i =m$ 。

因此该限制我们可以转化成：$\sum b_i \le m$ 。

我们考虑贪心求出 “满足该排列要求以及满足最终公布的 $b_{p_i}$ 随 $i$ 单调不增的 $b$ ， $\sum b_i$ 最小是多少” 。

我们发现正着求很难求，考虑倒着求。

我们发现，我们是能够倒着唯一确定每个位置放的最小的 $b$ 。

复杂度 $O(n\times n!)$ 。

题解 2 （ $O(2^nn^2m)$ 状压 DP + 费用提前）

容易想到一个 $O(2^nn^2m^2)$ 的 DP ：令 $f[S,i,j,sum]$ 为有多少种 $S$ 内元素构成的排列使得 $p_{1}=i$,$b_{p_{|S|}}=j$ 且 $\min (\sum b_i)=sum$ 的方案数。

容易证明（类归纳法），最终状态任意两个不同的状态的方案数不交。

key idea : 数组 $a$ 单调不降等价其差分数组 $d_i=d_{i}-d_{i-1},\forall d_i \ge 0$ 。

我们可以简单确定以下性质：

如果我们确定了 $b_n$ 且满足 $a_n+b_n= \max(a_{p_i}+[p_i ，我们倒着确定 \(b$ 只需要满足 $a_{p_i}+b_{p_i}=a_{p_{i+1}}+[p_{i+1} ，就能同时满足排名和每次公布 \(b$ 时排名第一的限制。

令 $f[S,i,sum]$ 为考虑 $S$ 内的元素，有多少种 $p_{|S|}$ 排列满足存在一种分配 $b$ 的方案满足：

$\sum b_i=sum$
每个队伍公布 $b$ 时成为榜一即：
- \(a_{p_i}+b_{p_i}\ge a_{p_{i+1}}+[p_{i+1}
- $a_{p_i}+b_{p_i}\ge a_j+[j
- \(a_{p_i}+b_{p_i}\ge a_{p_j}+[p_j

而对于每个队伍公布 $b$ 时成为榜一的限制我们可以化简成如下两个限制：

\(a_{p_n}+b_{p_n} \ge a_j+[j
\(a_{p_i}+b_{p_i}\ge a_{p_{i+1}}+[p_{i+1}

我们在 DP 的时候直接考虑第 $|S|$ 位的取值十分困难，但是我们可以很简单的知道 $b_{p_{1}}-b_{p_{2}}$ 在最优情况下的取值，因此我们考虑每次去决策差分数组的取值，将费用提前，即在决策差分数组第 $i$ 位 $d_i$ 时，将其贡献看成 $d_i\times (n-i+1)$ 。

一个直观的感受就是：每次给一个后缀加上相同的权值 (DP横条变成DP竖条)。

key idea:将费用提前，DP 中的费用转化成所有位置对费用贡献和。

复杂度 $O(2^nn^2m)$ ，

P7520 [省选联考 2021 A 卷] 支配

题目描述

给定一张 $n$ 个点 $m$ 条边的有向图 $G$，其顶点从 $1$ 到 $n$ 编号。

对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。

对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。

现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。

数据范围

$1\le n\le 3000,1\le m\le 2\times n,1\le q\le 2\times 10^4$ 。

题解（支配树）

关于有向图的支配问题有以下基本性质：

支配的传递性关系：若 $x$ 支配 $y$ , $y$ 支配 $z$ ，那么一定有 $x$ 支配 $z$ 。
支配的链式关系：若 $x$ 支配 $z$ ，$y$ 支配 $z$ ，一定有 $x$ 支配 $y$ 或者 $y$ 支配 $x$ 。
支配树：$x$ 的在支配树中的父亲 $fa_x\in D_x$ 且满足 $D_y=D_x\cup x$ 。

根据支配的树中对于父亲的定义，不难想到一个 $O(n^2)$ 的支配树建树方法：

令 $f[x,y]\in \{0,1\}$ 表示删除点 $x$ 后点 $1$ 是否能够到达点 $y$ 。对于该数组我们可以在 $O(n^2)$ 的时间内暴力 DFS 求出。
$x$ 支配 $y$ 等价于 $f[x,y] = 0$ 。
根据支配树的定义，遍历每个点的 受支配集 找到其在支配树中的父亲。

加入一条边 $s\to t$ 之后的基本性质：

一个点的受支配集要么变小，要么不变。因为这条边使整张图 “ 更加联通 ”。
$x$ 的受支配集变化有两种情况：
- $D_{fa_x}$ 发生变化。
- $fa_x$ 不再支配 $x$ 。

因此，我们可以直观的看出受支配集发生变化的点集一定是支配树上若干个子树的不交并。

而 $fa_x$ 不再支配 $x$ 等价于删除 $fa_x$ 后 $1$ 可以到达 $s$ 且 $t$ 可以到达 $x$ ，$O(n^2)$ 预处理即可。

每次询问在支配树上 DFS 一遍即可，复杂度 $O(n^2+nq)$ 。

P7517 [省选联考 2021 B 卷] 数对

题目描述

给定 $n$ 个正整数 $a_i$，请你求出有多少个数对 $(i, j)$ 满足 $1 \le i \le n$，$1 \le j \le n$，$i \ne j$ 且 $a_i$ 是 $a_j$ 的倍数。

数据范围

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

题解

开个桶维护每种数的个数之后 $O(n\ln n)$ 枚举倍数即可。

一些需要注意的地方：

因为没有保证 $a_i$ 互不相同 ，所以这样写复杂度是错的，如果 $\forall a_i=1$ 就可以卡满：

rep(i,1,n) {
	for (int j = 2; j * a[i] <= 500000; j++) ans += cnt[j*a[i]];
}

正确写法：

rep(i,1,500000) {
	if (!cnt[i]) continue;
	for (int j = 2; j * i <= 500000; j++) ans += cnt[i] * cnt[i*j];
}

P7518 [省选联考 2021 A/B 卷] 宝石

题目描述

欧艾大陆上有 $n$ 座城市，城市从 $1 \sim n$ 编号，所有城市经由 $n - 1$ 条无向道路互相连通，即 $n$ 座城市与 $n - 1$ 条道路构成了一棵树。

每座城市的集市上都会出售宝石，总共有 $m$ 种不同的宝石，用 $1 \sim m$ 编号。$i$ 号城市的集市出售的是第 $w_i$ 种宝石，一种宝石可能会在多座城市的集市出售。

K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多 $c$ 颗宝石，其收集宝石的顺序为：$P_1, P_2, \ldots , P_c$。更具体地，收集器需要先放入第 $P_1$ 种宝石，然后才能再放入第 $P_2$ 种宝石，之后再能放入第 $P_3$ 种宝石，以此类推。其中 $P_1, P_2, \ldots , P_c$ 互不相等。

K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。

现在 K 神给了你 $q$ 次询问，每次给出起点 $s_i$ 与终点 $t_i$，他想知道如果从 $s_i$ 号城市出发，沿最短路线走到 $t_i$ 号城市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）

数据范围

$1\le n,q\le 2\times 10^5,1\le c\le m\le 5\times 10^4,1\le w_i\le m$ 。

题解（倍增+二分+主席树 / 离线）

若 $w_i=j,P_k=j,w_i\gets k$ 。

令 $f[u][j]$ 为收集 $[w_u,w_u+2^j]$ 内的宝石需要 “向上爬” 爬到的最深的点是哪个点。

预处理的时候，我们 DFS 动态维护当前 DFS 到的点上面第一个 $w_j=k$ 的点的编号。

我们将 $s\to t$ 差分为 $s\to lca(s,t),lca(s,t)\to t$ 。

每次询问 $(s,t)$ 对于 $s\to lca(s,t)$ ，我们可以先跳到 $s$ 上面第一个 $w_j=1$ 的点 $pos$ ，然后在 $pos$ 倍增（向上暴跳）。

而对于向下的部分，我们可以每次二分答案，每次 check 也可以用倍增维护：

令 $g[u][j]$ 为 “反向收集” $[w_u-2^j,w_u]$ 内的宝石，向上最深爬到的点的编号。

我们每次，check 需要知道 $t$ 上面第一个 $w_j=k$ 的点的编号，有两种做法：

可持久化线段树
离线之后再二分

复杂度 $O(n\log ^2 n)$ 。

总结省选

【总结】联合省选题目选做

省选联考 \(2021\)

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

题目描述

数据范围

题解 1 （二分 + 双指针）：

题解 2 （排序 + 双指针）：

P7515 [省选联考 2021 A 卷] 矩阵游戏

题目描述

数据范围

题解（差分约束）：

P7516 [省选联考 2021 A/B 卷] 图函数

题目描述

数据范围

题解 ( \(O(n^3)\) 动态加边传递闭包 )

P7519 [省选联考 2021 A/B 卷] 滚榜

题目描述

数据范围

题解 1 （60pts 枚举排列 + 贪心）

题解 2 （ \(O(2^nn^2m)\) 状压 DP + 费用提前）

P7520 [省选联考 2021 A 卷] 支配

题目描述

数据范围

题解（支配树）

P7517 [省选联考 2021 B 卷] 数对

题目描述

数据范围

题解

P7518 [省选联考 2021 A/B 卷] 宝石

题目描述

数据范围

题解（倍增+二分+主席树 / 离线）

相关