省选联考 2021 A卷

2021 联合省选解题报告 A卷

D2T3 给咕了

卡牌游戏（card）

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

$n$ 张牌，第 $i$ 张牌正面为 $a_i$，反面为 $b_i$，最多 $m$ 次翻牌（使某张牌反面向上）。最小化朝上面数字的极差。

保证 $2n$ 个数互不相同。$m < n \le 10^6,1\le a_i,b_i\le 10^9$

题解

考虑枚举答案（极差），我们把所有 $a_i,b_i$ 丢在一起排序，如果确定了极差，我们枚举最小值，最大值可以用双指针维护，并且维护这段区间是否每个位置都有、翻牌次数是否超过限制。。

考虑枚举的极差越大，那双指针维护的区间会越宽，更易满足条件。具备单调性，二分即可。

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

CODE

矩阵游戏（matrix）

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

$n\times m$ 的矩阵 $a_{i,j}$ 满足 $0\le a_{i,j}\le 10^6$ ，$(n-1)\times(m-1)$ 的矩阵满足 $b_{i,j}=a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}$ 给你矩阵 $b$，让你还原 $a$，或输出无解

$$n,m\le 300$$

20pts

$n,m\le 3$ ：手模，先使公共格尽量大。

50pts

$m=2$ ：令 $x_i=a_{i,1}+a_{i,2}$ ，只要能满足 $0\le x_i\le 2\times 10^6$ 即可，会有 $n-1$ 个限制：$x_i+x_{i+1}=b_{i,1}$ 。将 $x_1$ 当做变量，$x_{i}(i>1)$ 都可以用 $x_1$ 表示出了，再用 $0\le x_i\le 2\times 10^6$ 这个限制可以算出 $x_1$ 的范围，最后填回去。

正解

如果不考虑 $0\le a_{i,j}\le 10^6$ 的限制，只满足和为 $b$，随便搞搞。考虑此时对一行或一列按顺序 $+1,-1,+1,-1\dots$ 还是满足 $b$ 的。

且若答案存在，通过这些操作一定能使当前局面变成答案。

证明：两个满足 $b$ 限制的矩阵，只要第一行和第一列相同那么这两矩阵相同（第一行第一列确定了，其它块都可以通过 $b$ 矩阵推出来）。那么我们只要把第一行和第一列整成和答案矩阵一样就行了，这个显然是可以的（第一行每个位置用列操作整，第一列每个位置用行操作整）。

那么设某行、某列操作次数为 $x_i$ 。差分约束。（注意需要保证每个格子行和列的符号是相反的，这样才能差分约束）。注意卡常，邻接矩阵显然比链式向前星要快（寻址连续）

CODE

图函数（graph）

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

题解

考虑一个 $f(u,G)$ 能有贡献的点 $v$ 必然在 $[1,u]$ 中（$u$ 必然和自己联通，删除 $u$ 后它和谁都不联通了）。

整一个结论：不需要真的删点，一个点 $v$ 有贡献只要它不经过 $[1,v-1]$ 中的点与 $u$ 联通即可。

证明：考虑点 $x\in[1,v-1]$，要么它与 $u$ 不联通，那么 $v$ 不可能经过 $x$ 到 $u$；如果它与 $u$ 联通，那它早被删掉了。

题意转化：题目中要我们求的 $h(G)$ 相当于我们在 $G$ 中找有多少点对 $(x,y)$ 满足只经过 $[x,n]$ 的点 $x$ 能到 $y$ 且 $y$ 能到 $x$。

做法一

考虑一个点对 $(u,v)$ 在 $G_i$ 中出现必然在 $G_j(j<i)$ 中出现，即对答案的前缀有贡献。更具体的，$x$ 为 $u\to v,v\to u$ 中最小编号的边，$(u,v)$ 对 $G_{0},G_1,\dots,G_x$ 有一的贡献。那么需要最大化两点间路径上最小边 $x$ ，对答案数组差分一下。可以用 Floyd （$O(n^3)$） 或者 Dijkstra （$O(mn\log n)$），正反图都跑一遍。

注意点对 $(u,v)$ 要满足经过的点在 $[u,n]$ 范围内，如果用 Dijkstra，枚举点 $u$ 作为起点，忽略所有 $<u$ 的即可。如果用 Floyd，中转点 $k$ 倒着枚举就是了（考虑 Floyd 原理）。

做法二

先考虑一个挺暴力的做法，我们统计一个每张图中，一个点 $v$ 对所有 $f(u,G)$ 的贡献，显然只要将 $[v,n]$ 中点的正图、反图拉出来跑 BFS 就行了，但这样复杂度为 $O(mn(n+m))$ 。

考虑一个优化（我怎么想不到呢QAQ）,对于一个点 $v$，考虑倒着枚举那 $m$ 个图，也就是每次加一条边，记为 $s\to t$。可以继承上一次 BFS 的结果，若 $s$ 被访问过 $t$ 没有被访问则 $\mathrm{BFS}(t)$，否则只需在图中插入这条边，因为访问过的点再访问没有意义。这样每条边每个点都最多访问一次，BFS 复杂度均摊 $O(n+m)$，总复杂度 $O(n(n+m))$ 。

CODE

宝石（gem）

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

题解

转化一下题意， 若 $w_u=P_i$ 令 $\mathit{val}_u=i$ 否则 $\mathit{val}_u=0$。每次询问 $s$ 到 $t$ 最长的 $\mathit{val}$ 从 $1$ 开始严格 $+1$ 的子序列的长度。

有点像 「神J上树」 。

如果是一条链，只要维护每个点向左/向右 $\mathit{val}_{v}=\mathit{val}_u+1$ 的第一个位置，再倍增即可。

放到树上呢，向上跳的时候同样直接倍增即可，向下怎么办（没有方向），同「神J上树」，树剖就行了，每条链里方向是确定的。

剩下一个问题：如何切换重链。假设当前的 $\mathit{val}=x$，那么需要在新链的某处 向下/向上 寻找第一个 $val=x+1$ 的点，这玩意显然主席树可以搞定，那完事了。

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

显然这样写代码臭长无比……

CODE

滚榜（ranklist）

60pts

$n\le 10$，答案上界 $n!$ 显然，考虑暴搜公布顺序（倒过来就是最后排名），对于当前队伍贪心分配最少的 $b$ 使其超过所有队伍，只要搜完后 $b$ 的总和小于等于 $m$ 则该顺序可行。$O(n!\times n)$ 的暴搜。

正解

$n\le 13$， $O(n!)$ 显然不行，那就 $O(2^n\times \square)$ 状压吧。

设 $f(S,c,r)$ 表示 $i\in S$ 的队伍已经被公布，上一次公布的队伍为 $c(c\in S)$，分配了 $r$ 分的方案数。

跟暴力一样考虑贪心分配 $b$，且按公布顺序 $b_i$ 单调不降，可以费用提前计算，每次 $r$ 加上 $b$ 的差值乘剩余未公布的队伍数。

$$f\left(S+\{x\},x,r+\mathit{calc}\times(n-|S|)\right) \gets f(S,c,r)$$

$\mathit{calc}$ 表示计算 $b_x-b_c$。想清楚一件事，除了第一个队伍要超过所有人，后面每个队伍只要超过前一个队伍就行了。所以只需要考虑 $x$ 的总分超 $c$ 的总分，且已有限制 $b_x\ge b_c$ ，转化为考虑 $a_x+\mathit{calc}$ 超过 $a_c$ 就行了。

复杂度 $O(2^nn^2m)$ （如果精确点算最坏 $2^{n-2}n(n-1)m$，1e8 左右开 O2 显然是能过的）

CODE