【题解】2024 UESTC 暑假集训 第二轮

收录了二轮集训的部分题解。

抛一点链接，方便日后跳转。

7.31 https://codeforces.com/gym/537696（2024 HDU 多校 6）

8.1 https://codeforces.com/gym/539789（SEERC 2020）

8.2 https://codeforces.com/gym/540037（2023 江苏省赛/ CCPC Hunan）

8.3 https://codeforces.com/gym/540187（2020 CCPC Weihai）

8.4 https://codeforces.com/gym/105173（2024 东北四省赛 / CCPC Northeast）

8.5 https://codeforces.com/gym/540735（2023 Nanjing Regional / Ucup 2-11）

8.6 https://codeforces.com/gym/541036（UKIEPC 2023）

8.7 https://codeforces.com/gym/541235（NEERC 2019-2020）

8.8 https://codeforces.com/gym/541365（2024 上海市赛）

8.9 https://codeforces.com/gym/541786（2024 陕西省赛）

8.10 https://codeforces.com/gym/541891（2024 吉林省赛 / CCPC Changchun）

8.11 https://codeforces.com/gym/104976（2023 Hangzhou Regional / Ucup 2-22）

8.12 https://codeforces.com/gym/542320（毒瘤 psk / 998244353）

8.13 https://codeforces.com/gym/541594（SEERC 2022）

8.14 https://codeforces.com/gym/542837（ECNA 2022）

8.15 https://codeforces.com/gym/543029（2022 CCPC Weihai）

8.16 https://codeforces.com/gym/543323（NWERC 2019）

8.17 https://codeforces.com/gym/543433（2020 CCPC Changchun）

8.18 被赶出清水河

8.22 https://codeforces.com/gym/105231（2024 江西省赛）

8.23 https://codeforces.com/gym/102822（2020 CCPC Mianyang）

8.24 https://codeforces.com/gym/102769（2020 CCPC Qinhuangdao）

8.25 https://codeforces.com/gym/104252（2022-2023 Latin American Regional）

8.26 https://codeforces.com/gym/103081（SWERC 2020）

8.28 https://codeforces.com/gym/104064（NWERC 2021）

8.29 https://codeforces.com/gym/104787（2023 CCPC Qinhuangdao / Ucup 2-9）

8.30 https://codeforces.com/gym/104945（SWERC 2023）

2024 HDU 多校 第6场

B. 造花（困难版）【分类讨论】

给定一张无重边无自环不保证联通的无向图，若删去某个点后整个图被分为若干菊花图，则称这个点为混沌点。升序输出所有混沌点编号，或报告不存在。

\(1 \le n, m \le 2\cdot 10^6\)。

首先可以暴力 check（通过度数判断）这张图的每个连通分量是不是菊花图。若有两个及以上的连通分量不是菊花图，则无解；否则我们只考虑不是菊花图的那个连通分量。

分两种情况考虑：

  • 这个连通分量是一棵树。通过以下步骤可以 \(O(n)\) check 每个点是不是混沌点：
    • 对于每个点 \(x\)，新建变量 sum = 0，遍历 \(x\) 的邻接点 \(y\)。若 \(y\) 的度数为 \(2\)，则继续遍历 \(y\) 的邻接点 \(z\)（\(z \neq x\)），sum += deg[z] + 1；否则 sum += deg[y]。若删去 \(x\) 该树被分为两个菊花图，那么此时度数统计完全，应有 sum == n - 1。这里 \(n\) 是连通分量的大小。
  • 这个联通分量不是树（有环）。此时有两个性质可以手玩出来：
    1. 若存在混沌点，该连通分量所有环的大小最多是四元环。
    2. 若有多个环，混沌点只能是所有环的交集。

由结论 \(2\)，我们只需要随便从这个连通分量中找一个环，此时所有可能的混沌点都在这个环上。又由结论 \(1\)，可以暴力 check 这些可能的混沌点，最多 check 不超过 \(4\) 次。

时间复杂度 \(O(n)\)。

G. 树上 MEX 问题【dp】

定义一张图的 MEX 为：图中所有点的点权构成的集合中，最小的没有出现过的非负整数。

给定一棵 \(n\) 个点的树，点有点权 \(a_i\)，保证点权互不相同。求这棵树的所有联通导出子图的 MEX 之和，对 998244353 取模。

\(1 \le n \le 10 ^6\)，\(0 \le a_i < n\)。

设 \(T_i\) 为由点权为 \(0\sim i\) 的点构成的极小联通子图，\(cnt_i\) 为包含 \(T_i\) 的联通子图个数。

则有结论：\(ans = \sum_\limits{i = 0}^{n - 1}cnt_i\)。

  • 证明：子图 \(T_i\) 的 mex 为 \(i + 1\)，且 \(T_i\) 一定包含 \(T_0\sim T_{i - 1}\)，故 mex 恰好为 \(i + 1\) 的联通子图个数为 \(cnt_i - cnt_{i + 1}\)，有： \[\large \begin{align}ans &=\sum_{i = 0}^{n - 1}(i + 1)(cnt_i-cnt_{i + 1})\\&=(cnt_{0}-cnt_{1})+2(cnt_1 - cnt_2)+3(cnt_2-cnt_3)+\cdots \\&=\sum_{i = 0}^{n - 1}cnt_i\end{align}\]

于是仅需求出 \(cnt_i\)。

接下来考虑如何对连通子图进行计数。

令 \(f_i\) 代表节点 \(i\) 可选可不选时以 \(i\) 为根的子树中以 \(i\) 为根的联通子图个数；

令 \(g_i\) 代表限定节点 \(i\) 必须选时以 \(i\) 为根的子树中以 \(i\) 为根的联通子图个数，则： \[\large\begin{cases}g_x = \prod_{y\in son_x}f_y\\f_x = g_x + 1\end{cases}\] 显然 \(cnt_0=g_0\)。

再考虑如何从 \(cnt_{i - 1}\) 转移到 \(cnt_i\)。发现每次由 \(T_{i - 1}\) 变为 \(T_i\) 时，原来必选的点现在仍然必选，同时多出来了一些必选的点，称为目标点集。不难发现目标点集构成一条链，即点权为 \(0\sim {i}\) 的路径上 \(T_{i - 1}\) 中的非必选点。

我们用一个 vis 数组标记已经访问过的点，遍历到 \(i\) 时，若 !vis[i]，就一直跳父亲（以点权为 \(0\) 的点为根），直到 vis 为 \(1\)。途径的点即目标点集。

每次新增一个必选点 \(x\) 时，有 \(cnt \leftarrow cnt \times \dfrac{g_x}{f_x}\)，对目标点集中的每个点更新即可。

时间复杂度 \(O(n\log m)\)，\(m\) 为模数。

K. 天天爱跑步【基环树，单调队列，线段树】

给定一棵 \(n\) 个点的基环树。对 \(i\in[1, n]\) 求经过第 \(i\) 个点的最长简单路径长度。

\(1 \le n \le 5\cdot 10^5\)。

基环树的结构可概括为：一个环，然后环上的每个点向下延伸出子树。

以下是一些约定：

令 \(h_i\) 代表点 \(i\) 属于环上哪个点的子树。

令 \(dep_i\) 代表点 \(i\) 在子树内的深度。（\(h_i\) 深度为 \(1\)）

令 \(a_i\) 代表环上的点 \(i\) 向下延伸出的最长链长度。

令 \(len_i\) 代表经过点 \(i\) 且仅在 \(h_i\) 子树内的最长链长度。

令 \(f_{i, 0/1}\) 代表点 \(i\) 向子树内延伸出的最长链/次长链长度。

令 \(g_{i, 0/1}\) 代表点 \(i\) 向子树内延伸出的最长链/次长链对应的子节点。

令 \(\text{ano}\text{side}_i\) 代表环上的点 \(i\) 向该点子树外延伸出的最长链长度。（包括环上的一段以及环上另一点向其子树延伸出的最长链）

根据点 \(i\) 在基环树中的位置可以分为两种情况：点 \(i\) 在环上和点 \(i\) 在子树中。

点 \(i\) 在环上时，我们要找的是 \(\max(a_i+\text{anoside}_i)=\max(a_i+a_j+i-j)\)。破环成链，则 \(i-j\) 代表环上的一段满足 \(i-j<m\) 的 \([j, i]\)。

首先，我们可以用单调队列求出这个最大值。具体地，按顺序遍历环，每次往双端队列中压入 \(i\)，弹出队首不满足 \(i-j< m\) 的 \(j\)，弹出队尾不满足 \(a_j-j\ge a_i-i\) 的 \(j\)。

求出最大值后，我们可以用线段树维护对应区间 \([j,i]\) 上的答案，每次用最大值与这个区间的值取 \(\max\)。

注意，对环上的两个方向都要分别跑单调队列，同样更新答案。

点 \(i\) 在子树中时，答案为： \[\large \max(len_i,f_{i, 0}+dep_i-1+\text{anoside}_{h_i})\] 前者为不经过环上的点的答案，后者为经过环上的点的答案。

对于一个子树，\(f_{i,0/1}\) 可以一次 dfs 求出，同时处理出 \(g_{i,0/1}\) 用于换根，求出 \(len_i\)。

具体地，换根时令 \(d_i\) 代表 \(i\) 所在的子树外不经过环的最长链，有： \[\large{d_x=\max\begin{cases}d_{fa}+1\\f_{fa,0}+1 &,g_{fa,0}\neq x\\f_{fa,1}+1 &,g_{fa,0}=x\end{cases}}\] \[\large{len_x=f_{x,0}+\max(f_{x,1},d_x)}\]

时间复杂度：\(O(n\log n)\)。

SEERC 2020

B. Reverse Game【博弈，逆序对】

给定一个 \(01\) 串 \(s\)，\(\text{Alice}\) 和 \(\text{Bob}\) 进行回合制博弈。轮到一个人时，该名玩家可以从 \(s\) 中任选一个恰为 \(10,110,100\) 或 \(1010\) 的子串，并将其翻转。无法进行操作的玩家输，问先手是否有必胜策略。

\(1 \le |s| \le 10^6\)。

很考验 Insight 的题。

注意到 \(s\) 的最后形态必然为 \(0\cdots01\cdots1\)（因为有 \(10\) 就可以翻转），特点是逆序对为 \(0\)。

而每次翻转操作可以将 \(s\) 的逆序对数减少 \(1\) 或 \(2\)，并且手玩发现若 \(s\) 的逆序对数 \(\ge 2\)，则子串中一定有 \(110,100,1010\) 中的一种。

根据必胜必败态定理，后手总存在策略使得一个轮次中 \(s\) 的逆序对数减少 \(3\)（即先手减 \(1\) 后手减 \(2\)，先手减 \(2\) 后手减 \(1\)）。

因此当 \(s\) 的逆序对数 \(\bmod 3 = 0\) 时，后手必胜；否则先手必胜。

时间复杂度 \(O(n)\)。

A. Archeologists【反悔贪心】

你在玩一个寻宝类游戏，一共有 \(n\) 个格子，编号为 \(1 \sim n\)。你每在第 \(i\) 号格子上下挖一层便会获得 \(a_i\) 的价值，你需要保证每个格子与其相邻格子的下挖深度不超过 \(1\)（注意此时 \(1\) 和 \(n\) 号点最多只能挖一层），求最大价值。

\(1 \le n \le 2.5\cdot 10^5\)，\(-10^6 \le a_i \le 10^6\)。

有一类用反悔贪心解决的经典问题：有一样物品，第 \(i\) 天价值为 \(v_i\)，每一天你可以买入一件或卖出一件，问最大收益。

解决步骤是维护一个小根堆，然后遍历 \(v_i\)，若 \(v_i\) 比堆顶 \(v_u\) 大，则收益加上 \(v_i - v_u\)，弹出堆顶，并再向堆中塞入一个 \(v_i\)。这样下次再卖出时（假设为第 \(j\) 天），若定位到为第 \(i\) 天买入，就赚了 \(v_j - v_i\)，加上之前赚的 \(v_i-v_u\)，一共赚了 \(v_j-v_u\)，等价于在第 \(u\) 天买入第 \(j\) 天卖出。以此涵盖了在任意天买入和卖出的情况。

priority_queue<int, vector<int>, greater<int>> q;
int ans = 0;
for (int i = 0; i < n; i++) {
	if (!q.empty() && q.top() < a[i]) {
		ans += a[i] - q.top();
		q.pop();
		q.push(a[i]);
	}
	q.push(a[i]);
}
cout << ans << "\n";

对于本题，令 \(b_i\) 为第 \(i\) 个格子的下挖深度，由于相邻项相差不超过 \(1\)，因此其差分数组的每一项只可能是 \(-1, 0, 1\)。

将 \(1\) 看成一次买入，\(-1\) 看成一次卖出，就与经典题等价了。

将题给的 \(a_i\) 求前缀和作为物品的价值，跑反悔贪心即可。

时间复杂度 \(O(n \log n)\)。

H. AND = OR【线段树，位运算】

对于一个序列 \(\{b\}\)，若可以将 \(\{b\}\) 划分为两个非空的子序列，满足其中一个子序列中所有元素的 \(\text{And}\) 与另一个子序列中所有元素的 \(OR\) 相等，则称 \(\{b\}\) 是 good 的。

给定一个长为 \(n\) 的数组 \(\{a\}\)，以及 \(q\) 次询问。每次询问 \(\{a\}\) 的一个区间 \([l, r]\) 是否 good。

\(1 \le n,q \le 10^5\)，\(0\le a_i < 2^{30}\)。

先考虑单个询问。设 \([l,r]\) 中的数被划分成 \(A,B\) 两个集合，\(A\) 集合的 \(\text{OR}\) 和 \(B\) 集合的 \(\text{And}\) 相等，均为 \(X\)。

那么宏观上有：\(A\) 中的所有数 \(\le X\)，\(B\) 中的所有数 \(\ge X\)。因此把 \([l,r]\) 内的所有数升序排序，\(A\) 中的数一定是一段前缀，\(B\) 中的数一定是一段后缀，枚举分段点即可。

还能按位来看：设 \(p(x)=\text{popcount}(x)\)，\(p(X)=k\)，那么 \(\forall x\in A,p(x)\le k\)，\(\forall x \in B,p(x)\ge k\)。

此时可以枚举分段点 \(g\)，两种情况：

\[\Large\begin{cases}\text{And}_{x\in[l, r],p(x)\le g} = \text{Or}_{x\in[l,r],p(x)>g} &, g\in [0,30)\\\text{And}_{x\in[l, r],p(x)\le g}= \text{Or}_{x \in[l,r], p(x)\ge g} &, g \in[0,30]\end{cases}\]

对于第二种情况，可以证明若能划分，那么满足 \(p(x)=g\) 的所有 \(x\) 必须相等。\((\alpha)\)

  • 证明：假设存在 \(a,b\) 满足 \(p(a)=g,p(b)=g\)，且 \(a\) 被划分进 \(A\)，\(b\) 被划分进 \(B\)。那么：

\[\Large\begin{cases}a \text{ | }X=X \\ b \ \& \ X = X\end{cases}\to a \ \&\ b = b \xrightarrow{p(a)=p(b)} a= b\]

至此，我们可以用 \(30\) 个线段树或 \(30\) 个 st 表维护二进制下每一位 \(\{a\}\) 的区间按位或和区间按位与。对于一个询问 \([l,r]\)，查询这个区间每一位的 \(\text{Or}\) 值（\(\text{Or}[g]\)）和 \(\text{And}\) 值（\(\text{And}[g]\)），并对前者做前缀和，后者做后缀和（即 \(\text{SOr}[g]\) 代表区间内满足 \(p(x)\in[0,g]\) 的所有 \(x\) 的 \(\text{Or}\) 值，\(\text{SAnd}[g]\) 代表区间内满足 \(p(x)\in[g,30]\) 的所有 \(x\) 的 \(\text{And}\) 值），对上文两种情况分别 \(\text{check}\) 即可。

此外还要注意 \(\text{check}\) 两个集合必须非空，可以对每一位额外维护一个前缀和相同处理。

而 \((\alpha)\) 条件等价于判断 \(\text{Or}[g]=\text{And}[g]\)，不用额外处理。

最开始写的 st 表没卡过，换了线段树过的。时间复杂度 \(O(30n+30q\log n)\)。

2023 江苏省赛/ CCPC Hunan

B. Honkai in TAIKULA【拆点，缩点，全源最短路】

给定一张 \(n\) 个节点 \(m\) 条边的有向带权图，对每个节点，报告是否存在经过该点的奇权圈（可经过重复顶点、重复边、若经过重复边，边权计多次）。若存在，输出最小奇权圈的权值（或报告为负无穷）。

\(1\le n \le 1000\)，\(1 \le m \le 10^4\)，\(0\le x_i,y_i < n\)，\(|w_i| \le 10^7\)。

处理带权图的边权奇偶性问题常用缩点：把一个点 \(x\) 拆成一个奇点 \(\text{Odd}_x\)、一个偶点 \(\text{Even}_x\)。

  • 若存在 \(x\xrightarrow{w} y\)，\(w\) 为奇数。则连 \(\text{Odd}_x \to \text{Even}_y\)，\(\text{Even}_x \to \text{Odd}_y\)。
  • 若存在 \(x \xrightarrow{w} y\)，\(w\) 为偶数。则连 \(\text{Odd}_x\to \text{Odd}_y\)，\(\text{Even}_x\to \text{Even}_y\)。

若存在一个经过点 \(x\) 的奇权圈，等价于存在一条 \(\text{Odd}_x \to \text{Even}_x\) 的路径。（或 \(\text{Even}_x \to \text{Odd}_x\)，钦定一种即可）

接着，由于环只存在于单个强连通分量内，所以考虑缩点得到一张有向无环图 \(G\)。

注意到只要存在一条路径从 \(x\) 出发，经过负环，再回到 \(x\)。那么最小奇权圈的权值就是负无穷，因为可以再负环上无限绕再返回 \(x\)。所以对 \(G\) 中每个点代表的子图都跑 SPFA 算法判断负环。

设 \(\text{Odd}_x\) 和 \(\text{Even}_x\) 所在的 SCC 编号分别为 \(A\) 和 \(B\)。利用 dfs 判断 \(G\) 中是否存在 \(A\to B\) 的路径，路径上又是否有标记为负环的点即可完成无解和负无穷解的判断。

接下来是有解的情况。在未缩点的原图上跑 Johnson 全源最短路即可，注意避开 “位于被标记负环的 SCC 中” 的所有点。

时间复杂度 \(O(nm\log m)\)。

Funfact：有人拓扑图上 dfs 不用标记数组标记走过的点，狂 T 两小时QAQ。

L. Architect【思维，扫描线】

给定 \(n\) 个长方体，询问其是否能拼接成一个 \(W\times H\times L\) 的立方体，没有重叠和空隙，所有长方体都要用到。

\(1\le n \le 10^5\)，\(1\le W, H, L \le 10^9\)。

一种绝世聪明的想法是 “只需判断 \(n\) 个立方体的体积和是否 \(=\) \(W\times H\times L\)，且八个角的出现次数是否是偶数次即可”。

体积一样限定了这 \(n\) 个立方体不能有重叠。

八个角出现了偶数次限定了这 \(n\) 个立方体与大立方体间没有空隙。

注意 \(10^9\cdot 10^9\cdot 10^9=10^{27}\)，需要开 __int128。

时间复杂度 \(O(8n\log n)\)。

另一种朴素但也颇具技巧性的方法是扫描线。

先将 \(n\) 个小立方体的底面看作 \(1\)，顶面看作 \(-1\)；大立方体的底面看作 \(-1\)，顶面看作 \(1\)。

如果每个表面紧紧贴合，那么代数和为 \(0\)。

接着不断降维，同样的思想能判断线是否紧密贴合，点是否紧密贴合。

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

2020 CCPC Weihai

B. Labyrinth【bfs】

给定一个 \(n\times m\) 的网格图，有 \(k\) 个格子有障碍不能通行。\(q\) 次询问，每次询问两点间的最短路长度。

\(1\le n,m\le2\cdot 10^5\)，\(1\le n\cdot m\le 2\cdot 10^5\)，\(0\le k \le 42\)，\(1\le q\le 10^5\)。

对于一组询问，假设询问的两个点是 \((x_1,y_1)\) 和 \((x_2, y_2)\)。

那么当 \((x_1,y_1)\) 和 \((x_2,y_2)\) 作为对角线的两个端点围成的矩形中没有一个障碍时，答案就是这两点间的曼哈顿距离；否则可以想象到最短路一定经过某个障碍周围四格中的某一格。

把所有障碍的四联通预处理出来并去重，以每个点为起点跑 bfs 求出其到所有格子的最短路。

询问时枚举一下这 \(O(4k)\) 个点作为中转点的最短路，取 \(\min\) 即可。

时间复杂度 \(O(knm)-O(k)\)。

C. Rencontre【结论，期望】

给定一棵 \(n\) 个点的树，边有边权 \(w_i\)。给定三个点集，从三个点集中分别随机选出 \(u_1,u_2,u_3\)，问以下式子的期望： \[f(u_1,u_2,u_3)=\min_{i\in[1,n]}(dis(u_1,i)+dis(u_2,i)+dis(u_3,i))\] 其中 \(dis(x,y)\) 代表点 \(x,y\) 间的树上距离。

\(1\le n \le 2 \cdot 10^5\)，\(1\le w \le 1000\)。

结论题。所给式子等价于： \[f(u_1,u_2,u_3)=\frac{1}{2}(dis(u_1,u_2)+dis(u_2,u_3)+dis(u_1,u_3))\] 根据期望的线性性，只需分别求出这三项每一项的期望再相加。

以 \(dis(u_1,u_2)\) 举例，考虑拆贡献：对于一条边 \(x\leftrightarrow y\)，设 \(x\) 一侧有 \(A_x\) 个点属于点集一，\(B_x\) 个点属于点集二；\(y\) 一侧有 \(A_y\) 个点属于点集一，\(B_y\) 个点属于点集二。

那么该条边的贡献为 \(w\cdot \dfrac{A_x B_y+A_yB_x}{|A||B|}\)，\(|A|\) 和 \(|B|\) 分别为点集一和点集二的大小。最终贡献就是所有边的贡献之和。

dfs 简单处理，时间复杂度 \(O(n)\)。

G. Caesar Cipher【线段树维护哈希值】

维护一个序列 \(\{a\}\)，支持两种操作：

  • 1 l r：\(\forall i\in[l, r]\)，\(a_i=(a_i+1)\bmod 65536\).
  • 2 x y L：询问区间 \([x,x+L-1]\) 和区间 \([y,y+L-1]\) 是否完全相同。

\(1\le n,q\le 5\cdot10^5\)。

经典题，线段树维护哈希值。

预处理出 pow[i] 代表 \(\text{base}^i\)，pre[i] 代表 \(\sum_{j=0}^{i}\text{base}^j\)。

区间合并时，左区间的哈希值需要乘 pow[r - mid] 再加上右区间的哈希值。

区间修改时，相当于区间加 pre[r - l]。

区间查询时，合并答案需要左区间答案乘 pow[max(0, min(r, qr) - mid)] 再加上右区间答案。

这道题的创新点是操作一需要模一个数。

注意到值溢出（即 \(\ge 65536\)）的次数不超过 \(\frac{nq}{65536}\approx 4\cdot10^6\) 次，可以维护区间最大值，每次定位到那个溢出的点然后单点修改。

时间复杂度 \(O(\frac{nq\log n}{65536}+q\log n)\)。时限给了 10s，实际上 1s 多一点就跑完了。

J. Steins;Game【博弈，SG函数，线性基】

现定义一种博弈游戏：有 \(n\) 堆石子，每堆石子被涂成了黑色或白色。双方轮流从以下两种取石子方式中选择一种并操作：

  • 从石子数最少的黑色堆中取任意个石子。这里“最少”是与其它黑色堆比较。
  • 从任意白色堆中取任意个石子。

轮到某一方时无石子可取则败。

现在这 \(n\) 堆石子每一堆的数量 \(a_i\) 固定，但并未上色。

求有多少种上色方案，使得先手必败。方案数对 \(10^9+7\) 取模。

\(1\le n \le 10^5\)，\(1 \le a_i \le 10^{18}\)。

将白色堆和黑色堆分开来看，称为白色游戏和黑色游戏。

当白色游戏的 SG 值和黑色游戏的 SG 值异或为 \(0\) 时，先手必败。

白色游戏即 nim 游戏——当所有白色堆石子数目的异或和为 \(0\) 时，先手必败。

接着尝试求出黑色游戏的 SG 值，可以打表找规律。

结论是： \[\text{SG}_{黑色游戏}=\text{最小堆石子数量}-(有多少堆石子数最少+[所有堆石子数相同])\bmod2\] 然后是计数。将 \(a_i\) 排序，预处理出前缀异或和 \(\text{pre}_i\)，后缀异或和 \(\text{suf}_i\)，有 \(\text{tot}_i\) 堆石子数为 \(i\)，以及第 \(i\sim n\) 堆中有 \(\text{same}_i\) 堆石子数为 \(a_i\)。在以下过程中，相同石子数的堆可以先被当成无标号来做，最后再乘上组合数转为有标号。

从后向前扫 \(\{a\}\)，设当前扫到第 \(i\) 堆，钦定第 \(i\) 堆为黑色且在黑色堆中石子数量最少。此时第 \(1\sim (i-1)\) 堆只能是黑色，异或和为 \(X=\text{pre}_{i-1}\)。然后分 "所有黑色堆石子数是否相同" 来讨论第 \((i + 1) \sim n\) 堆。

若选出的黑色堆要满足石子数相同，则第 \(i\sim (i+\text{same}_i-1)\) 堆为黑色（因为是从后往前扫，所以涵盖了该连续段所有后缀为黑色堆的情况），第 \((i+\text{same}_i)\sim n\) 堆为白色。它们的 SG 值可以用上述公式以及后缀异或和快速求。

若选出的黑色堆不需要满足石子数相同，那么黑色游戏的 SG 为 \(Y=a_{i}-\text{same}_i \bmod 2\)。此时需要从后面的堆中选出若干白色堆使得它们的异或和是 \(X\oplus Y\)，方案数可以用线性基求出。

具体地，设线性基 \(S\) 的大小为 \(|S|\)，此前插入了 \(x\) 个数。若 \(X\oplus Y\) 能被线性基表示出来，则方案数为 \(2^{x-|S|}\)。

最后，别忘了乘组合数 \(\dbinom{\text{tot}_i}{\text{same}_i}\) 再累加到答案中。

时间复杂度 \(O(n\log w)\)，\(w\) 为值域。

2024 东北四省赛 / CCPC Northeast

H. Meet【树上差分，分类讨论】

给定一棵 \(n\) 个点的树，以及 \(m\) 组点对构成的集合 \(S\)。你需要选定一个点作为根节点，使得 \(\max_\limits{(x, y)\in S} \max(\text{dis}(x, \text{lca}_{x, y}), \text{dis}(y, \text{lca}_{x, y}))\) 最小，输出这个最小值。

\(1 \le n, m \le 10^5\)。

二分答案，设二分出的答案为 \(d\)。

对于每一组点对 \((x, y)\)，可以确定一个点集（一个树上连通块），使得以该点集中的点为根时，答案 \(\le d\)。接着只需要用树上差分判断这 \(m\) 个点集是否有交即可。

需要纸上分几种情况讨论，红温了挺久。

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

K. Tasks【贪心】

有 \(n\) 个区间，定义一个区间的烦躁度等于所有包含它的区间的最大烦躁值 \(+1\)（如果没有包含它的区间，则烦躁值为 \(0\)）。

现在你知道这 \(n\) 个区间的左端点 \(l_i\) 和烦躁值 \(b_i\)，你需要构造对应的右端点以满足条件，或报告 \(-1\)。

特别规定给出的构造需要满足没有两个完全相同的区间且没有一个右端点 \(> 10^6\)。

\(1\le n \le 10^5\)，\(1 \le l_i \le 10^6\)。

把 \(b_i\) 相同的区间看作一层，从 \(b_i=0\) 开始从低层向高层构造。

对于同一层，若存在两个区间左端点相同，那么无解；否则必要条件是每个区间都要被一个上一层的区间包含。

那么有如下贪心的构造：从右向左考虑当前层的左端点，设当前左端点为 \(l\)，那肯定是选上一层中左端点 \(<l\) 且离 \(l\) 最近的区间来被包含。若有多个左端点满足，则选右端点最靠右的，这样能给下一层留够最多的空间。这个过程可以通过 std::lower_bound 简单实现。

如遇区间完全相同，右端点向左缩一位即可。

时间复杂度 \(O(n\log n)\)。

B. Charging Station【最大权闭合子图】

有 \(3n\) 个能源站，分为三级，每级 \(n\) 个，从高级向低级编号为 \(1\sim n\)，\(n\sim 2n\)，\(2n\sim 3n\)。

每个能源站有三种状态：不工作、供能、吸能。供能有供能功率 \(a_i\)，吸能有吸能功率 \(b_i\)。

有 \(m\) 个限制关系，每一条形如 “能源站 \(x\) 要处于供能状态当且仅当低一级的能源站 \(y\) 在吸能状态”。

问最大总供能功率。

\(1\le n, m\le 10^5\)，\(1\le a_i,b_i\le 10^9\)。

假设只有两级，并且低级能源站都处于吸能状态，那么就是经典的最大权闭合子图问题。

具体地，将供能站视作左部点，吸能站视作右部点。

源点 \(S\) 向左部点连收益大小的边，左部点向右部点连正无穷的边，右部点向汇点 \(T\) 连代价大小的边，最大供能功率就是 左部点权值之和 \(-\) 最小割。

现在考虑这个三级模型。最高级的能源站只能处在供能或不工作状态，最低级的能源站只能处在供能或吸能状态（不工作还不如供能），中级能源站的状态则取决于上下两级。

假设这么一个初始状态：中级能源站供能，高级能源站不工作，低级能源站吸能。

当低级能源站由吸能 \(\to\) 供能时，中级能源站只能供能 \(\to\) 不工作；当高级能源站由不工作 \(\to\) 供能时，中级能源站只能不工作 \(\to\) 吸能。

于是我们把中级能源站拆成两个点，分别为 "供能 \(\to\) 不工作" 和 "不工作 \(\to\) 吸能"，对应的代价恰好为 \(a_i\) 和 \(b_i\)。建图如下：

id

其中，\(S\) 向低级能源站连 \(a_i+b_i\) 的边是因为只考虑从吸能状态转换为供能状态带来的总收益。

时间复杂度 \(O(m\sqrt{n})\)。

G. Diamond【根号分治】

给定一个长为 \(n\) 的序列 \(\{a\}\)。有 \(m\) 次询问，每次指定 \(l, r, p, q\) 四个参数，问若只保留下标在 \([l, r]\) 内且值为 \(p\) 或者 \(q\) 的数，其它数全部删除，此时剩下序列的逆序对数量。询问间相互独立。

\(2\le n \le 10^5\)，\(1 \le m \le 10^5\)，\(1\le a_i \le n\)。

较为明显的根号分治。把每个数的出现位置存到 std::vector 中，记为 pos。

若 \(p,q\) 的出现次数都 \(\le\sqrt{n}\)，直接在 pos 上暴跳计算贡献，\(O(\sqrt{n})\)。

否则 \(p, q\) 中至少有一个出现次数 \(>\sqrt{n}\)。由于这样的数（设为 \(X\)）不超过 \(\dfrac{n}{\sqrt{n}}=\sqrt{n}\) 个，我们可以对 \(1\sim n\) 的每一个位置 \(i\) 处理出 count[i][j] 代表 \(1\sim i\) 中值 \(j\in X\) 出现了多少次。

那么对于一个区间 \([l, r]\)，不妨设 \(p<q\)，答案就是： \[\left(\sum_{i\in[l,r],a[i]=p}\text{count}[i][q]\right)-\text{occ}[l-1][q]\times\left(\text{occ}[r][p]-\text{occ}[l-1][p]\right)\] 其中 occ[i][j] 代表 \(1\sim i\) 中 \(j\in[1,n]\) 的出现次数，这里只是为方便说明，实际存不下，可修改为 occ[i] 代表 \(1\sim i\) 中 \(a[i]\) 的出现次数，然后二分查询。

至于第一项，可以预处理出 count[i][j] 的前缀和，然后二分出 \(j\) 在 \([l, r]\) 中第一次出现和最后一次出现的位置 \(O(1)\) 回答。

那如果 \(p>q\) 且 \(q\) 的出现次数 \(\le \sqrt{n}\) 呢？我们没处理出这样的 count[i][q]，但可以把 \(p,q\) swap 一下求出顺序对的数量，然后容斥。

时间复杂度 \(O((n+q)\sqrt{n})\)。

2023 Nanjing Regional / Ucup 2-11

M. Trapping Rain Water【吉司机线段树】

给定长为 \(n\) 的序列 \(\{a\}\)，有 \(q\) 次修改，每次将 \(a_{x_i}\) 加上 \(v_i\)。令 \(f_i=\max(a_1,a_2,\cdots,a_i)\)，\(g_i=\max(a_i,a_{i + 1},\cdots,a_n)\)，你需要在每次修改后回答： \[\sum_{i=1}^{n}(\min(f_i,g_i)-a_i)\] \(1\le n, q \le 10^6\)，\(1\le a_i \le 10^6\)，\(1\le v_i \le 10^6\)。

这题最关键的观察是 \(\max(f_i,g_i)=\max a_i\)，即 \(\min(f_i,g_i)=f_i+g_i-\max a_i\)。

于是式子化为 \(\sum f_i+\sum g_i -n\cdot\max a_i-\sum a_i\).

后两项在修改时很容易维护，主要考虑前两项，这里以 \(\sum f_i\) 为例。

根据 \(f_i\) 的定义，设当前将 \(a_i\) 增加至 \(x\)，则相当于给 \(f_{i\sim n}\) 中的每一项与 \(x\) 取 \(\max\)。

吉司机线段树处理即可。

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

D. Red Black Tree【dp，凸序列】

现存网上的任何一篇题解都看得不是很明白，占坑。

E. Extending Distance【网络流，对偶图】

有一个 \(n\) 行 \(m\) 列的网格图，相邻格点之间有边，边有边权。

你可以进行任意次操作，每次操作可以使某条边的边权增加 \(1\)。

求一种操作次数最少的方案使得从第一列任意一个点出发到最后一列任意一个点的最短路恰好增加 \(K\)，输出方案。

\(1 \le n\cdot m \le 5000\)，\(1 \le K\le 100\)。

网格图是一种特殊的平面图。所谓平面图，是指能画在平面上，满足任何两条边没有交叉。

将平面图 \(G\) 的每个面看作一个点，\(G\) 中每条边两侧的两个面（可以是同一个面）进行连边，就得到了一个对偶图。

一个经典的题目是 “P4001 狼抓兔子”，它展示了一种平面图最小割转对偶图最短路的思想，不再赘述。

同样地，对本题中的网格图进行对偶，那么原图的最短路等价于对偶图的最小割。

建图，将原图中的边费用设为 \(0\)，流量设为边权；再对每条边建费用为 \(1\)，流量为 \(+\infty\) 的额外边。

此时题目等价于找一条流量为 \(D+K\) 的费用最小的流，其中 \(D\) 为原图的最短路。

分两步处理：

  • 先只连费用为 \(0\) 的边，不连额外边。跑从源点 \(S\) 流向汇点 \(T\) 的最大流。
  • 对每条边连额外边，再连一条从 super 源点 \(P\) 向源点 \(S\) 费用为 \(0\) 流量为 \(K\) 的边。跑从 super 源点 \(P\) 流向汇点 \(T\) 的最大流。此时跑出来的费用即为最小操作次数。

至于方案，可以遍历残量网络上费用为 \(1\) 的边，检查剩余流量。这条边的操作次数就是原始流量和剩余流量的差。

时间复杂度 \(O(n^2m^2k)\)。

一种较为简洁的网格图转对偶图建图方法：

auto id = [&] (int x, int y) {
	if (x == 0) {
		return S;
	} 
	if (x == n) {
		return T;
	}
	return (x - 1) * (m - 1) + y;
};
for (int i = 1; i <= n; i++) {
	for (int j = 1; j < m; j++) {
		int x = id(i - 1, j);
		int y = id(i, j);
        // x -> y
	}
}	
for (int i = 1; i < n; i++) {
	for (int j = 1; j <= m; j++) {
		if (j == 1 || j == m) {
			continue;
		}
		int x = id(i, j - 1);
		int y = id(i, j);
        // x -> y
	}
}

UKIEPC 2023

G. Glacier Travel【计算几何】

给定平面上 \(n\) 个点 \((x_i,y_i)\)，按顺序依次连成折线段。两个人一前一后沿着折线移动，它们的路程差固定为 \(s\)，问移动过程中两人的最短距离。

\(2\le n\le 10^6\)，\(-10^6\le x_i,y_i\le 10^6\)，\(1\le s \le 1000\)。

可以从折线段的起点开始维护一对双指针，每次从状态 \(\{(x_A,y_A),(x_B,y_B)\}\) 转移到状态 \(\{(x_A',y_A'),(x_B',y_B')\}\) 当且仅当 \((x_A',y_A')\) 或 \((x_B',y_B')\) 为某条线段的一个端点。

至于计算距离，有一个能使码量简单许多的转化：相对速度。

首先，两个人在同一条线段上移动肯定不优。否则假定 \(A\) 不动，根据速度的合成法则，此时 \(B\) 的运动轨迹是一条线段，于是可以三分或直接运用点到线段的距离公式计算。

具体地，答案是点 \((0,0)\) 到线段 \((x_B-x_A,y_B-y_A)\sim(x_B'-x_A',y_B'-y_A')\) 的距离。

时间复杂度 \(O(n)\)。

H. History in Numbers【线段树】

维护长为 \(n\) 的序列 \(\{a\}\)，并有 \(m\) 次操作，每次可能是以下两种之一。

update l r d：\(\forall i\in [l, r]\)，\(a_i := a_i+d\)。

check l r：查询区间 \([l, r]\) 的局部最小值序列是否严格递增。

区间 \([l,r]\) 的局部最小值序列：将 \([l, r]\) 中相邻且相同的元素只保留一个后，数值上小于两侧元素的数构成的集合。

\(1 \le n,m \le 3\cdot 10^5\)，\(-10^8\le a_i,d\le 10^8\)。

线段树板题，就是维护起来细节比较多。

线段树维护七个值：

  • l1：区间左起第一个数。
  • l2：区间左起和 l1 不同的第二个数。
  • r1：区间右起第一个数。
  • r2：区间右起和 r1 不同的第二个数。
  • f1：区间左起第一个局部最小值的值。
  • f2：区间右起第一个局部最小值的值。
  • ok：该区间的局部最小值序列是否递增。

然后就是分类讨论了，代码里我分区间去重后只有一个值，只有两个值，超过两个值讨论了一下。

注意区间左右两侧的边界情况需要特判。

时间复杂度 \(O((n+m)\log n)\)。

NEERC 2019-2020

L. Lengths and Periods【后缀自动机】

SAM 真是人类智慧的结晶啊！占坑。

2024 上海市赛

F. 羁绊大师【bitset 优化背包】

有 \(n\) 个英雄，每个英雄有 \(a_i,b_i\) 两种羁绊，且不存在 \(i,j\in[1,n]\) 使得 \(a_i=a_j\land b_i=b_j\)。

共有 \(m\) 种羁绊，每种羁绊至多只有两个英雄拥有。当上阵英雄中有两个英雄拥有此羁绊时，该羁绊为激活状态。

对 \(k\in[1,n]\) 分别回答当有 \(k\) 个英雄上阵时，激活羁绊的最大数量。

\(1\le n \le 10^5\)，\(n \le m \le 2n\)，\(1\le a_i < b_i \le m\)。

将英雄看成点，羁绊看成边，拥有相同羁绊的两个英雄连边，问题转化为对 \(k\in [1,n]\) 分别回答选中 \(k\) 个点时导出子图的最大边数。

这个图具有特殊性质——每个点的度数至多是 \(2\)，因此图中只包含环或链。

对于同样数目的点，选环比选链更具性价比，而对于两条链，优先选更长的链肯定也不劣。于是推断出以下策略：

  • 选择一些环使得这些环的总点数 \(x\le k\) 且 \(x\) 尽可能大。
  • 按链的长度降序选择直到剩下的 \(k-x\) 个点用完。

第一步可以做 \(01\) 背包 \(O(n^2)\) 地解决。又因为这是存在性背包，于是可以用 std::bitset 优化到 \(O(\frac{n^2}{w})\)。

第二步用一个指针维护当前选择的边数即可。

时间复杂度 \(O(\frac{n^2}{w})\)。

D. 咸鱼跑酷【线段树】

长为 \(n\) 的操作序列，每个位置有两种操作，形如 +x 或 *x。

给定 \(q\) 组询问，每次给定 u l r，问以初值 \(u\)，执行 \(l\to r\) 的操作序列，每个位置可以选择两种给定操作中的一种，最后能得到的最大数值。答案对 998244353 取模。

\(1\le n,q \le 10^5\)，\(1\le x,u \le 10^9\)。

对于一个位置，如果都是 + 或都是 *，那么一定选数字大的那个；否则一加一乘，且只有乘的数 \(>1\) 时才有选择的可能，我们称这样的位置为关键位置。

注意到 \(1\le x \le 10^9\)，故当当前 \(u>10^9\) 时，选乘一定比选加更优。

又因为每次经过一个关键位置，数字大小至少\(\times 2\)，故经过 \(O(\log W)\) 个关键位置之后当前数字就会超过临界值。

于是我们预处理出下一个关键位置的坐标，暴力跳 \(O(\log W)\) 个段。由于段间都为 + 操作，故维护一个前缀和即可。

当跳到数值 \(>10^9\)，之后的选择就固定了。用线段树维护一段区间累计乘了多少，累计加了多少，就能快速计算。

pushup 的方式：

Mul[p] = Mul[p << 1] * Mul[p << 1 | 1]
Add[p] = Add[p << 1] * Mul[p << 1 | 1] + Add[p << 1 | 1]

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

SEERC 2022

I. Inadequate Operation【贪心、单调栈】

给定长为 \(n\) 的非负序列 \(\{a\}\)，每次操作你可以选择一个 \(i\in[1,n)\)，满足 \(\max(a_i,a_{i+1}) >0\)，然后用 \(\max(a_i,a_{i + 1})-1\) 替换 \(a_i\) 和 \(a_{i+1}\)。问使得序列所有元素变为 \(0\) 的最小操作次数。

\(2 \le n \le 2\cdot 10^5\)，\(0\le a_i\le 10^9\)。

略微诈骗。因为这个操作每次最多让两个位置 \(-1\)（即 \(a_i=a_{i+1}\) 时），就算你让一个位置 \(-1\)，另一个位置被拉高，你继续操作这个下标操作次数也不会更劣。于是策略就是贪心地从大到小删。

对于一个相同高度长为 \(L\) 的连续段，删掉它需要 \(\lceil \frac{L}{2}\rceil\) 次操作。形式化地，答案是： \[\sum_{i=1}^{mx}\left(\left\lceil\frac{L_{i1}}{2}\right\rceil +\left\lceil\frac{L_{i2}}{2}\right\rceil +\cdots\right)\] 其中 \(L_i\) 是指考虑所有 \(\ge i\) 的元素，它们形成的若干连续段长度。

进一步地，记 \(l_i\) 为 \(i\) 左侧第一个 \(<a_i\) 的位置，\(r_i\) 为 \(i\) 右侧第一个 \(<a_i\) 的位置。式子可以化成： \[\sum_{i=1}^{n}\left\lceil\frac{r_i-l_i-1}{2}\right\rceil(a_i-\max(a_{l_i},a_{r_i}))\] 实现的时候，可以维护一个内部递增的单调栈，扫一遍就能求出 \(l_i\) 和 \(r_i\)。

时间复杂度 \(O(n)\)。

K. Knowledge Testing Problem【整体二分】

给定一个 \(n\) 个点 \(m\) 条边的无向图，边有边权 \(w_i\)。其中任意一条边 \(x_i\to y_i\) 都满足 \(|x_i-y_i|\le 10\)。给定 \(q\) 组询问，每次询问两个点问最短路。

\(1 \le n \le 10^5\)，\(1\le m \le 2\cdot 10^5\)，\(1\le q \le 2.5\cdot 10^4\)，\(1 \le w_i \le 10^9\)。

考虑整体二分。

对于当前区间 \([l, r]\)，设中点为 \(m\)，取中点周围 \([m-4,m+5]\) 共 \(10\) 个点，并以这些点为起点跑单源最短路（经过的点必须在 \([l,r]\) 内，即只连两个端点都在 \([l, r]\) 内的边），然后再以这些点为中转点分治下去。

对于一个询问 \(x,y\)，若 \(\max(x,y)<m-4\)，就把它放到 \([l,m-4)\) 里继续更新；若 \(\min(x,y)>m+5\)，就把它放到 \((m+5,r]\) 里继续更新；否则此次更新完后不用继续更新，因为必然以 \(x,y\) 中的至少一个点为起点跑了单源最短路。

保证正确性的根据是：对于一个询问 \(x,y\)（不妨设 \(x<y<m-4\)），如果最短路需要经过 \(m+5\) 右侧的点，就必然经过 \([m-4,m+5]\) 中的某一个（因为任意一条边两侧的点编号相差 \(\le 10\)），故以这 \(10\) 个点为中转点更新出的最短路能覆盖所有的情况。

假设 \(n,m\) 同级，时间复杂度 \(O(nd\log^2n)\)，\(d=10\)。

NWERC 2021

H. Heating Up【双向链表】

有 \(n\) 个辣椒，第 \(i\) 个辣度为 \(a_i\)，排成环形（即 \(1\) 和 \(n\) 看作相邻）。你要吃光这些辣椒，你可以任意选择一个辣椒开始，并在之后每一步选择"已选择辣椒"中的一个相邻辣椒吃下。你初始有忍耐度 \(f\)，你吃下一个辣度为 \(k\) 的辣椒当且仅当 \(f\ge k\)，并且当你吃掉它后你的忍耐值会增加 \(k\) 个单位。问吃光所有辣椒所需的最小初始忍耐值。

\(3\le n \le 5\cdot 10^5\)，\(0\le a_i \le 10^{13}\)。

二分答案，设二分出的答案为 \(s\)，问题转化为判定初始忍耐值为 \(s\) 时是否能吃完所有辣椒。

拆环成链，用一个双向链表操作以下过程：

  • 遍历 \(i\in[1,2n]\)，若 \(a_i>s\)，跳过；否则以点 \(i\) 为中心向两侧尝试扩张。
  • 对每一个连续段维护这个段 \(a_i\) 的最小值 \(b\)，当忍耐值不小于这个值时，就可以吞并这个段，新的 \(b\) 即两段取 \(\min\)。
  • 这个被合并的段有贡献 \(\sum a_i\)，合并时可以另开一个数组 \(c\) 维护。
  • 判定成功当且仅当链表合并到最后只剩一个元素，即删除了 \(2n-1\) 个元素。

时间复杂度 \(O(n\log w)\)，\(w\) 为二分值域。具体实现见代码。

SWERC 2023

G. Favourite Dish【凸包】

有 \(n\) 道菜，第 \(i\) 道菜有属性 \(a_i\) 和 \(b_i\)。有 \(m\) 个客人，第 \(i\) 个人有属性 \(c_{i}\) 和 \(d_i\)。

第 \(i\) 个人对第 \(j\) 道菜的喜爱度为 \(\dfrac{c_ia_j+d_ib_j}{c_i+d_i}\)，即加权平均值。你需要对每个人求出他最喜欢的菜品编号（若对两道菜的喜爱度相同，取编号较小者）。保证有序对 \((a_i,b_i)\) 两两不同，\((c_i,d_i)\) 两两不同。

\(1\le n,m\le 5\cdot 10^5\)，\(0\le a_i,b_i,c_i,d_i\le 10^6\)。

把每个人看作一个询问。对于单个询问，\(c+d\) 固定，衡量指标是 \(ac+bd\)。

问题转化为给定 \(n\) 个点 \((a, b)\)，每次询问一个 \((c, d)\)，问 \(ac+bd\) 取到最大值时对应点的编号。

这是一个经典问题。令 \(w=ac+bd\)，两边除以 \(d\)： \[\frac{w}{d}=\frac{ac}{d}+b\longrightarrow b=(-\frac{c}{d})a+\frac{w}{d}\] 这是一个 \(y=kx+b\) 形式的直线方程，让 \(w\) 最大，即让这条直线的截距 \(\left(\dfrac{w}{d}\right)\) 最大。

由于 \(a,b,c,d\) 均为非负整数，我们可以求出这 \(n\) 个点 \((a, b)\) 在第一象限的上凸壳，将询问按斜率 \(\left(-\dfrac{c}{d}\right)\) 排序，用一对双指针即可维护。（一个在凸壳上顺时针扫，一个按直线斜率从大到小扫）

时间复杂度 \(O(n\log n+m\log m)\)。

\(1.0\cdot \text{int}=\text{double}\)

\(1.0L\cdot \text{int}=\text{long double}\)

望周知 (QwQ)。

Competitive Programming > other
#ICPC #UESTC
【题解】2024 UESTC 暑假集训 第二轮
https://kisuraop.github.io/posts/70be1dc7.html
作者
KisuraOP
发布于
2024年9月2日
许可协议