往年 GD 省选练习。

2021 D1T1 卡牌游戏

<<<<<<< HEAD
<<<<<<< HEAD

简单二分题，由于误记了 RMQ 的复杂度而与正解失之交臂。

一道简单二分题，由于误记了 RMQ 的复杂度而与正解失之交臂。

>>>>>>> 0ba721313a0b44445d4541e4245f1de71c394482

一道简单二分题，由于误记了 RMQ 的复杂度而与正解失之交臂。

0ba721313a0b44445d4541e4245f1de71c394482

一定要留心静态可能导致的复杂度的降低。

题意

给定 $n$ 张牌，正反面各有一个数字，一开始正面朝上。试在不超过 $m$ 次翻转牌的操作内，最小化朝上数字的极差。

$n\le 10^6$，值域 $[1,10^9]$，$2n$ 个数互不相同，输入时已按照正面数字排序。

link: https://uoj.ac/problem/624

思路

首先二分答案，这是 $\Theta(\log n)$ 的，由于本题较为卡常，$\Theta(\log w)$ 不一定能过；

对于判定，考虑使用双指针从左往右维护无需翻转的卡牌区间，对于剩下的判断背面的数字是否都在卡牌区间内（使用 ST 表），如果是就更新当前答案。

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

代码：https://uoj.ac/submission/542476

<<<<<<< HEAD

=======

0ba721313a0b44445d4541e4245f1de71c394482

2021 D1T2 矩阵游戏

一道巧妙的思维题。其中将构造问题变为转化问题的思想值得学习。

题意

给定一个 $(n-1)\times (m-1)$ 的矩阵 $b{i,j}$，请构造出 $n\times m$ 的矩阵 $a{i,j}$ 满足 $\forall i\in[1,n),j\in[1,m):b{i,j}=a{i,j}+a{i,j+1}+a{i+1,j}+a{i+1,j+1}$，要求矩阵 $a{i,j}$ 的每一个数都在 $[0,10^6]$ 内。如果无解则输出 NO。

多测，$T\le 10$，$2\le n,m\le 300$，$0\le b_{i,j}\le 4\times 10^6$，输入的数都是整数。

link: https://uoj.ac/problem/625

思路

若除去 $[0,10^6]$ 的限制，构造将是平凡的：只需将了第一行、第一列的都置为 $0$，剩下的差分一下即可。通过观察可以发现：将矩阵 $a{i,j}$ 一行/一列的每个元素依次 $+\delta,-\delta,+\delta,-\delta,\dots$ 后，矩阵 $a{i,j}$ 依然满足性质。

设一开始构造的矩阵为 $d{i,j}$，第 $i$ 行的 $\delta$ 为 $r_i$，第 $j$ 列的 $\delta $ 为 $c_i$，则 $a{i,j}=d{i,j}+(-1)^{j+1}r_i+(-1)^{i+1}c_j$。如果 $r_i$ 和 $c_j$ 的符号不同，就是简单的差分约束系统，问题是有相同的符号情况。解决也非常的容易：将偶数列、奇数行的 $\delta$ 变号，那么 $a{i,j}=d_{i,j}+(-1)^{i+j+1}r_i+(-1)^{i+j}c_i$。差分约束即可。

时间复杂度 $O(Tnm(n+m))$。

代码：https://uoj.ac/submission/542585

2021 D1T3 图函数

一道简单图论题。删边变加边的思路应用很广。

题意

给定一张有向图 $G$，点有标号。对于其上一点 $u$，定义 $f(u,G)$ 如下：

首先初始化计数器 $c\gets 0$，并令 $G’\gets G$；
接着按编号从小到大枚举顶点 $v$，如果 $u$ 和 $v$ 双联通则 $c\gets c+1$，并从 $G’$ 中删去 $v$ 及其联通的边。
$f(u,G)$ 就是最终 $c$ 的值。

给定一张有向图 $G$，点、边皆有标号，定义 $h(G)=\sum\limits_{u\in V}f(u,G)$。求 $h(G)$。

进一步地，定义 $G_i$ 为删去第 $1$ 到第 $i$ 条边的图，对每个 $i\in[1,|E|]$ 求 $h(G_i)$。

$|V|\le 1000$，$|E|\le 2\times 10^5$。

link: https://uoj.ac/problem/626

思路

首先考虑 $f(u,G)$ 的意义：对于每个 $[1,u]$ 中的 $v$，是否存在不经过 $[1,v)$ 的、$u\to v$ 和 $v\to u$ 的路径。考虑建 $n$ 张图 $H_i$，第 $i$ 张图表示仅保留 $G$ 中 $[i,n]$ 的点所构成的子图。我们考虑 $h(G)$，先枚举 $v$ 后枚举 $u$，即对每个 $i$ 统计 $H_i$ 中 $i$ 与多少个点双联通。再建 $n$ 张图 $H_i’$，$H_i’$ 为 $H_i$ 的反图，那么只需要考虑 $H_i$ 和 $H_i’$ 中 $i$ 能到达的点集的交集大小。

然后考虑删边。删边后连通性维护比较难，但是加边后连通性维护非常容易。如果加了一条边 $i\to j$，如果 $i$ 能从起点到达而 $j$ 不能，就从 $j$ 开始 BFS 一边，标记上所有的点。这样复杂度是 $O(n+m)$ 的。

于是我们只需要枚举 $v$，然后倒序加边，每次加边如果需要暴力 BFS 就直接上，否则不管。注意要维护新打标记的点，如果 $H_i$ 和 $H_i’$ 都有新的点被打标记，新增的合法点数要减去同时在两张图里被新打标记的点，因为它们被统计了两次。

时间复杂度 $O(n(n+m))$，常数可能比较大，邻接表跑不过，用了链式前向星才过的。

代码：https://uoj.ac/submission/548580

2021 D2T1 宝石

一道简单树上问题。注意这种 DFS 中实时维护树上询问的方法。

题意

给定一棵树，点有点权 $w_i$，给定一个序列 ${P_c}$。共有 $q$ 组询问，每次询问给出一条有向简单路径 $u\to v$，设所经过的结点的点权组成的序列 $p_i$，求 ${P_c}$ 的最长的、为 $p_i$ 子序列的前缀的长度。

$n,q\le 2\times 10^5$，$1\le c,w_i\le 5\times 10^4$，$1\le P_i\le \max{w_i}$，$P_i$ 互不相同，TL 2s。

link: https://uoj.ac/problem/628

思路 1

首先为了方便，将 $w_i$ 重排使得 $P_i=i$。

先考虑链上的做法。维护每个 $w_i< c$ 的结点 $i$ 的向后的最近的比它恰多 $1$ 的点的位置 $nxt_i$，然后倍增预处理 $nxt$，对于 $[l,r]$ 的查询，先找到 $l$ 后面的最近的 $1$（可线性预处理），然后再从那个 $1$ 倍增地、不超过 $r$ 地往后跳。

对于树上的做法，我们分开上链 $u\to l$ 和下链 $l\to v$ 分别考虑。上链可以直接照搬链上的做法，预处理只需要维护 $\max{w_i}$ 个栈，DFS 一遍即可找到祖先中最近的 $1$、祖先中最近的后继。

对于下链，考虑二分答案。假设当前需要验证的答案为 $ans_t$，那么首先找到 $v$ 的祖先中最近的 $ans_t$，接着不断的往上跳，看是否能跳到 $preans+1$，其中 $preans$ 是上链的答案。（也先线性预处理祖先中最近的前驱）

问题是怎么找到祖先中最近的 $ans_t$。只需对每个点开一个可持久化权值线段树，每个点的树都是父亲的树在 $w_i$ 位置上修改为 $i$ 所得到的。查询直接在 $v$ 的树上查 $ans_t$ 的值即可。

时间复杂度 $O(n\log n+q\log n\cdot\log m)$，空间复杂度 $O(n\log n)$。虽然复杂度较劣且常数较大，但是仍然可以通过此题。

代码：https://uoj.ac/submission/549220

思路 2

仍然沿用上面的做法，但是不建可持久化权值线段树。处理下链的时候仍然在 DFS 过程中维护栈，DFS 到 $v$ 的时候就处理 $v$ 的询问。

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

2021 D2T2 滚榜

一道简单状态压缩 DP 题。注意这种“费用提前计算” trick。

题意

给定一个长为 $n$ 的正整数序列 $a_i$，有 $i$ 条对其的操作，第 $i$ 条为 $a_i\gets a_i+b_i$。对于下标 $i$ 和 $j$（$i\ne j$），定义序 $i\succ j$ 当且仅当 $a_i> a_j$，或 $a_i=a_j$ 且 $i< j$。现在自然数 $b_i$ 可以在 $\sum\limits_ib_i=m$ 的前提下任意改变，操作的顺序可以在 $b_i$ 不严格递增的前提下任意重排，但要求每次对 $k$ 操作后 $k$ 是在序 $\succ$ 下的最前值。

求最后所有 $i\in[1,n]\cap\mathbb Z$ 在 $\succ$ 下排列的结果的本质不同的种类数。

$n\le 13$，$m\le 500$，$a_i\le 10^4$。

link: https://uoj.ac/problem/629

思路

首先看到 $n\le 13$ 容易知道会使用状态压缩 DP。朴素地设状态 $f_{S,lmax,maxi,rest}$ 表示不合法的种类数，$S$ 为当前还未操作的下标集，$lmax$ 为当前操作前最大值，$maxi$ 为操作前最大值的下标，$rest$ 为最初的 $m$ 还剩多少可以给余下的 $b_i$。状态数不小于 $2^{13}\times 10^4\times 13\times 500$，而我们知道 $\log_2(13!)\approx 32.536$，因而至少需要 $1.97\text{ TiB}$ 的空间，无法通过此题 $512\text{ MiB}$ 的空间限制。

考虑优化：设初始最大值为 $\max_0$，则注意到在 $b_i$ 的最优分配（尽可能有解）的情况下每次操作最多使最大值增加 $1$，因而 $lmax$ 的可能取值只有 $14$ 个，空间可以被优化到 $2.82\text{ GiB}$，但仍然无法通过。

写出转移式后容易发现，如果知道当前枚举的操作的下标 $i$ 所需的 $bi$ 相较 $b{maxi}$ 相差多少，那么就可以在每次增加 $b_i$ 的时候将 $rest$ 事先为后操作的所有下标都提前减去值。经过推导不难发现，如果当前最大值下标为 $i$，而将要操作的下标为 $j$，则 $b_j$ 的所需值与 $b_i$ 的所需值为定值 $\max{a_i-a_j+[i< j],0}$。若设之为 $d(i,j)$，则可以省去 $lmax$ 这一维，转移方程如下：

$f_{S,maxi,rest}\gets \sum\limits_{u\in S} \begin{cases} f_{S-\{u\},u,rest-|S|\cdot d(i,j)}&\text{if }rest\ge |S|\cdot d(i,j)\\ (|S|-1)!&\text{otherwise} \end{cases}$

边界情况为 $f{\varnothing,maxi,rest}\gets 0$，最终答案为 $n!-f{[1,n],\max_0,m}$。

时间复杂度 $O(2^nn^2m)$，空间复杂度 $O(2^nnm)$，实际存储可以使用 64 位整数存储 $2^{13}\times 13\times 501$ 个状态，共约 $407\text{ MiB}$，可以通过此题。

实现上还需注意常数，有两种方法：

在枚举 $u$ 时不从 $1$ 到 $n$ 枚举后再判断是否在 $S$ 内，而是仅枚举 $S$ 内的元素，具体实现可以不断地取 $\operatorname{lowbit}(S)$ 得到，理论上能让常数变为 $\dfrac12$ 倍；
在从小到大枚举 $rest$ 的时候若 $f_{S,maxi,rest}=0$ 则不再继续枚举更大的 $rest$，实测仅此优化能通过此题。

代码：https://uoj.ac/submission/549614

2021 D2T3 支配

一道简单图论题。

题意

给定一个 $n$ 个点、$m$ 条边的有向图 $G$，定义顶点 $u$ 支配顶点 $v$ 当且仅当在 $G$ 中删去 $u$ 及与其相关的边后 $1$ 无法到达 $v$。特别地，$u$ 恒支配 $u$。设支配 $u$ 的点集为 $D_u$，现有 $q$ 次互相独立的询问，每次询问给出 $u$，$v$，问在 $G$ 中添加 $u\to v$ 这条边后有多少个点 $i$ 的 $D_i$ 发生了变化。

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

link: https://uoj.ac/problem/630

思路

为了方便表述，用 $u\rightarrowtail v$ 描述 $u$ 支配 $v$，用 $u \rightsquigarrow v$ 描述 $u$ 到 $v$ 的一条路径。

首先容易注意到支配关系的以下性质：

传递性：若 $u\rightarrowtail v$，$v\rightarrowtail w$，则 $u\rightarrowtail w$；
若以 $\rightarrowtail $ 为序给 $Du$ 排序为 $k_1,k_2,\dots,k_i$，$k_i=u$，则所有能到达 $u$ 的点所构成的子图一定呈 $1\to G_0\to k_1\to G_1\to k_2\cdots k{i-1}\to G{i-1}\to k_i$，且 $k_j$ 支配 $G_j,G{j+1},\dots,G_{i-1}$ 内的所有点。

考虑增加边 $u\to v$ 会对哪些点的受支配集发生变化。假设 $t$ 原先不被 $k$ 支配，加边后被 $k$ 支配，这是不可能的，因为加边不会使得原先 $1\rightsquigarrow t$ 的路径断掉，若原先存在不经过 $k$ 的路径加边后也会存在。

于是只有这种情况：$t$ 原先被 $k$ 支配，加边后不被 $k$ 支配。即，加边后存在一条 $1\rightsquigarrow u\to v\rightsquigarrow t$ 的路径不经过 $k$。于是若 $1$ 无法到达 $u$ 可以直接输出 $0$。

考虑枚举 $u$ 的可达点 $t$，每次判断是否存在一个 $u\to v$ 能“绕过”的支配点 $k$。注意到如果 $k$ 支配 $u$ 则 $u\to v$ 一定无法“绕过”，若 $k$ 不支配 $v$ 也无法绕过，因而 $k$ 是一个支配 $v$ 但不支配 $u$ 的点。注意到如果 $k’$ 和 $k$ 都满足这个性质且 $k\ne k’$，则 $k\rightarrowtail k’$ 和 $k’\rightarrowtail k$ 一定有且仅有一个成立。容易知道，在这里 $k\rightarrowtail k’$ 的充要条件是 $|Dk|< |D{k’}|$。于是仅需在支配 $v$ 且不支配 $u$ 的点中寻找受支配集最小的点即可。

假设寻找到了 $k$，只需检查在 $v$ 能在不经过 $k$ 的情况下到达的结点数即可。以 $v$ 为起点，不经过 $k$ 地 BFS，最后检查可达的结点即可。

注意实现细节：直接开 $n^2$ 的数组存储支配信息、支配集，不要使用 std::set/std::unordered_set 存储。

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

代码：https://uoj.ac/submission/549893

<<<<<<< HEAD

>>>>>>> 0ba721313a0b44445d4541e4245f1de71c394482

0ba721313a0b44445d4541e4245f1de71c394482