2021 省选联考 A 卷解题报告

宝石

有一个长度为$c$的元素互不相同的序列$a$，一棵$n$个点带点权的无根树。$q$次询问$(u, v)$，求最大的$i$，使得$a_1, \ldots, a_i$在$u$到$v$的简单路径的点权构成的序列中作为子序列出现过。

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

倍增 二分

有一个高妙的单 log 做法

我的做法是，首先把$a$序列变成$1, 2, \ldots, c$的样子，点权跟着改。把路径按照 lca 分成前后两段。

前半段可以倍增。然后我们在$v$上打一个形如$(\text{lca}(u, v), x, i)$的标记，表示从$\text{lca}(u, v)$到$v$的路径以权值$x$开始，且这是第$i$个询问。

对于后半段，我们二分一下路径结尾的权值，然后倒着往上走到 lca 的位置（倍增）。

因此总复杂度$O(n\log n + q\log ^2n)$。

代码

滚榜

状圧 DP 费用提前

容易想到状圧 DP。

设$a_i$，$b_i$表示第$i$个被公布的队伍的封榜前过题数和封榜后过题数。我们借此分析本题的状态空间与相关优化。

那么可以用于描述一个局面的朴素状态有：

• 已经公布结果的队伍集合。
• 已公布队伍的$b_i$的和。
• 当前的榜首过的题数。
• 当前榜首的$b_i$。

考虑压缩状态。

实际上我们不需要记榜首过的题数，只需要记榜首的编号和$b_i$即可计算出它的过题数。

这样的状态数就是$O(2^nnm^2)$，难以通过。

分析一下状态空间，我们发现状态的第四维仅用于维护$b_i$的偏序。换言之，它维护的是「$b_i$不降」的条件。考虑修改 DP 的方式，把这一条件消除。

「$b_i$不降」等价于「$\Delta b_i\ge 0$」（$\Delta b_i$表示其差分），后者显然是一个不需要计入状态空间的条件。那么我们能否用$\Delta b_i$完成 DP？

原题的滚榜过程是：每次$a_i \to a_i + b_i$，同时它会变成榜首。

• 第一个被公布的队伍需要超越$a_{\max}$才能成为榜首。
• 除此之外，第$i$个被公布的队伍（$i > 1$）需要超过$a_{i - 1} + b_{i - 1}$才能成为榜首。

注意到第二个过程等价于：

• 第$i$个被公布的队伍（$i > 1$）只要能超过$a_{i - 1} + b_{i - 1}$就能成为榜首。

于是 「$a_i + b_i \ge a_{i - 1} + b_{i - 1}$」等价于「$\Delta b_i \ge a_{i - 1} - a_i$」。

而$\sum b_i = m$等价于$\sum \Delta b_i (n - i + 1) = m$。

因此我们完全可以用$\Delta b_i$完成 DP，而且可以把第四维消除。其组合意义就是费用提前计算。

于是设$f(S, i, j)$表示已公布的队伍集合，最后一个被公布的队伍编号，已经被公布的队伍的$\sum \Delta b_i (n - i + 1)$的和，对应的方案数。

状态数$O(2^nnm)$，时间复杂度$O(2^nn^2m)$。

代码

卡牌游戏

有一个高妙的线性做法。

本题的算法趋向不明显，需要静下心来分析。

假设$a_i$是最小值。那么$1, \ldots, i - 1$就必须翻面，且我们要求$\min_{1\le j < i} \{ b_j \} > a_i$。那么我们还剩$m - (i - 1)$次翻牌机会。显然我们会从$a_n$开始倒着翻，使最大值最小。但是如果我们遇到了$a_x < b_x$或者$b_x < a_i$的牌就不用翻了。综上，这部分时间复杂度$O(n)$。

假设$b_i$是最小值。那么不妨从小到大枚举$b_i$。那么与上述过程是类似的，只不过多了一步寻找最大的$x$使得$a_x < b_i$的过程。

各种指针前缀后缀最小最大值扫一下就行。

瓶颈是排序。

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

代码

矩阵游戏

差分约束

先考虑构造一组解，满足$b_{i, j} = a_{i, j} + a_{i + 1, j} + a_{i, j + 1} + a_{i + 1, j +1}$的限制。

然后考虑调整$a_{i, j}$满足值域限制。

容易想到对于第$i$行，我们令$a_{i, j} \gets a_{i, j} + (-1) ^ jx$，仍然是满足等式限制的。列同理。

盲猜一下，任意局面都可以通过行调整和列调整得到。而矩阵的每个元素恰好受一个行调整和列调整的影响。因此问题转化为若干个二元不等式的问题，容易想到差分约束。

为了构造差分约束，我们定义变量$r_1, \ldots, r_n$和$c_1, \ldots, c_m$分别表示行调整和列调整的系数。然后令$a_{i, j} \gets a_{i, j} + (r_i - c_j)(-1)^{i+j}$。容易证明这个构造满足等式性质。

然后使用 Bellman-Ford 寻找一组解即可。若有负环则无解。

注意：和约束是不能做的。

注意：判负环是判断入队次数$\ge n$，而非松弛次数。

代码

图函数

Floyd 最短路

Floyd 可能不是个复杂度正确的算法，但是想要让 Floyd 过还是需要一些技巧的。

首先我们发现原题很复杂。需要转化。分析可以发现，在计算$f(u, G)$的过程中，当第二步枚举到$v$（$v < u$）的时候，$u$和$v$互相可达当且仅当存在一个包含$u, v$的环，使得环上的结点编号都$\ge v$。

证明

对于结点$x$（$x < v$），若$x$在之前被删掉了，那么显然不在此环上。

若没被删掉，那么必不可能在此环上，否则它就会在之前被删掉，矛盾。

因此我们设$g(u, v)$（$u > v$） 表示是否存在一个包含$u, v$的环，使得环上的结点编号都$\ge v$。那么有$h(G) = \sum_{v\le u}g(u, v)$。这样就转化为了一个纯计数问题。

计算$g(u, v)$可以有很多做法。但本题还要求计算在删除前$i$条边后的$h(G_i)$。不难想到计算每个$g(u, v)$的贡献。因此我们设$t(u, v)$表示使得$g(u, v) = 1$的最大的$i$。考虑 Floyd 算法，我们从大到小枚举中间点来保证环上的结点编号$\ge v$。而一条路径的权值就是这条路径上最早的被删除的边的时间。

这样我们就得到了一个$\Theta(n^3 + m)$的算法。它可以获得$44$分。

Floyd 转移的部分大概长这样：

ROF(k, n, 1) {
  FOR(i, 1, n) FOR(j, 1, n) {
    if(w[i][j] < min(w[i][k], w[k][j]))
      w[i][j] = min(w[i][k], w[k][j]);
  }
  FOR(i, k, n) {
    int x = min(w[i][k], w[k][i]);
    x = min(m + 1, x);
    if(x > 0) ans[x - 1] ++; // 答案的差分数组
  }
}

考虑优化。分析发现$w(i, k) = 0$的转移其实是无效的。把这种情况判掉可以得到$80$分（因为$80$分的边数较少）。

仔细思考，实际上$i > k < j$的转移也是无用的。因为满足$i > k < j$的$w(i, j)$不会对$w(i, k)$和$w(k, i)$的值造成影响。也不会对后续点对的最短路有影响。所以当$i > k$时我们只枚举$j < k$的部分做转移。

这样可以获得$100$分。

代码

支配

支配树

性质 1：支配关系构成树的结构。

证明：如果$u,v$都支配$z$，且$u, v$互不支配，那么我可以找到一条从$1$到$z$经过$v$但不经过$u$的路。矛盾。

性质 2：若$u$的受支配集改变，那么$u$在支配树上的子树里的结点的受支配集也跟着改变。

证明：$u$的受支配集显然是它在支配树上的祖先结点。得证。

性质 3：$u$受支配集的改变只会是删除其中的元素。

一个朴素的想法是：对每个结点$u$判断它的受支配集是否变化，如果变化就给它的子树都打上标记。最后统计标记的个数。

将祖先转化为父亲。也就是说对每个结点$u$判断它的受支配集中$u$的父亲是否被删除。如果有就给子树打上标记。容易证明这样是可以覆盖到所有的受支配集发生变化的结点的。

上述问题等价于：是否存在一条$1\to (s_i, t_i)\to u$的路径不经过$u$在支配树上的父亲。

等价于：$u$的父亲不是$1\to s_i$的必经点，且$t_i$能不经过$u$的父亲到达$u$。

预处理$h(u, v)$表示$v$不经过$u$的父亲能否到达$u$。这样可以在$O(n)$的时间内回答询问。

在$O(nm)$的时间内建立支配树即可。建支配树相当于是给支配关系做拓扑排序。

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

代码