ADPC26sp WriteUp
2026年度第七届全国大学生算法设计与编程挑战赛（春季赛）
2026.05
转工管群ISGSNSG在本场比赛中共解出8题并获得了大学A组铜奖。感谢两位队友的大力支持与带飞。
A 定时转运
试题题面
内存限制：1024MB 时间限制：4s
题目描述
某园区内有一条固定的通行线路。
从入口到终点之间依次经过 \(N\) 个中转点，编号为 \(1,2,\dots,N\)。
一名访客的移动规则如下：
- 从入口步行到中转点 \(1\) 需要固定时间 \(A\)；
- 对于每个 \(i\ (1\le i\le N-1)\)，中转点 \(i\) 到中转点 \(i+1\) 之间有一班接驳车：
- 这班车会在时刻 \(0, C_i, 2C_i, 3C_i, \dots\) 发车；
- 乘上后经过 \(D_i\) 的时间到达中转点 \(i+1\)；
- 从中转点 \(N\) 步行到终点还需要固定时间 \(B\)。
现在有 \(Q\) 次询问。
第 \(k\) 次询问给出一个出发时刻 \(R_k\)，表示访客恰好在时刻 \(R_k\) 从入口出发。
对于每次询问，请求出访客最早能够到达终点的时刻。
特别地，如果访客恰好在某班接驳车的发车时刻到达对应中转点，那么他可以立即乘坐该车。
输入格式
第一行包含三个整数 \(N, A, B\)。
接下来 \(N-1\) 行，第 \(i\) 行包含两个整数 \(C_i, D_i\)，表示从中转点 \(i\) 到中转点 \(i+1\) 的发车周期与乘车时间。
接下来一行包含一个整数 \(Q\)。
再接下来 \(Q\) 行，每行一个整数 \(R_k\)，表示一次询问的出发时刻。
输出格式
输出 \(Q\) 行。
第 \(k\) 行输出第 \(k\) 次询问的答案，即从时刻 \(R_k\) 出发时最早到达终点的时刻。
样例输入1
样例输出1
数据范围
\(2\le N\le 10^5\)
\(1\le A,B\le 10^9\)
\(1\le C_i\le 8\)
\(1\le D_i\le 10^9\)
\(1\le Q\le 2\times 10^5\)
\(0\le R_k\le 10^9\)
输入中的所有数均为整数。
WriteUp
首先想到的是暴力（因为一般第一题都是签到题不太会为难人？）最简单写了一个两层for循环模拟，在每组数据的每一个中转点模拟，时间超限，11/100。
这里是一个小trick，关键观察是有一个数据范围很小\(1\le C_i\le 8\)，其含义是班车会在时刻 \(0, C_i, 2C_i, 3C_i, \dots\) 发车。这也就意味着\(t\)时刻与\(t+840n\)时刻出发的人到达时间一定只相差\(840n\)（任意组合的最小公倍数一定是1到8的最小公倍数840的约数）。
AC代码如下。本题于00:49通过，一部分原因是本题大数据加大量暴力的尝试导致OJ判题队列累积。
#include <iostream>
using namespace std;
int n, a, b, q;
long long st, nst, tmp;
long long c[200005], d[200005];
long long myhash[860];
int main(){
cin >> n >> a >> b;
for(int i = 0; i < n-1; i++)
cin >> c[i] >> d[i];
for(int i = 0; i < 840; i++){
st = i;
for(int j = 0; j < n-1; j++){
if(st % c[j] != 0) st = (st / c[j] + 1) *c[j];
st += d[j];
}
st += b;
myhash[i] = st;
}
cin >> q;
for(int i = 0; i < q; i++){
cin >> tmp;
nst = tmp + a;
nst = myhash[nst % 840] + (nst/840) * 840;
cout << nst << endl;
}
return 0;
}
B 异侧
试题题面
内存限制：1024MB 时间限制：2s
题目描述
有 \(N\) 个位置，编号为 \(1,2,\dots,N\)。
现在需要给每个位置填入一个值，这个值只能是 \(0\) 或 \(1\)。
同时给出两列长度均为 \(M\) 的编号序列 \(P,Q\)。对于每个 \(i\ (1\le i\le M)\)，第 \(i\) 对编号 \((P_i,Q_i)\) 表示一个要求：
编号为 \(P_i\) 和 \(Q_i\) 的两个位置，所填的值必须不同。
也就是说，若最终填入的结果为
则必须对所有 \(1\le i\le M\) 满足
请判断，是否存在一种填法，使得所有要求同时成立。
如果存在，输出 Yes；否则输出 No。
输入格式
第一行包含两个整数 \(N,M\)。
第二行包含 \(M\) 个整数 \(P_1,P_2,\dots,P_M\)。
第三行包含 \(M\) 个整数 \(Q_1,Q_2,\dots,Q_M\)。
输出格式
如果存在合法的填法，输出 Yes；否则输出 No。
样例输入1
样例输出1
样例输入2
样例输出2
样例输入3
样例输出3
数据范围
\(1\le N,M\le 2\times 10^5\)
\(1\le P_i,Q_i\le N\)
输入中的所有数均为整数。
WriteUp
本来想投机取巧试试最简单的尝试能不能过去的……数据造的还是不错的，没能让最简单的先排个序然后依次尝试填入，如果遇到一个依赖关系两边都还没有填就随便填一个这种乱七八糟的东西混过去……答案错误 86/100
遂老实建图遍历（应该说本题思路是比较清晰的，一开始不这么做大概只是不想敲很多代码遂碰碰运气），照着洛谷深入浅出的板子打的，把有\(Y_{P_i} \ne Y_{Q_i}\)要求的\(P_i ,Q_i\)对在图中连一条无向边，然后dfs依据其父节点的数字填入子节点的数字或者（子节点已经有数字）判断关系是否成立，如果不成立就退出输出No，完整遍历完成没有冲突输出Yes即可。还有一点就是需要注意一下递归的条件，图中可能是存在环的（板子是树的遍历），如果一个节点已经填写了数字（在本解答中即color不为0，则不需要再对其dfs，否则可能无限递归然后运行错误；代码中0表示未访问，1表示0，2表示1，一条边连接的两个节点数字加和为3则认为符合要求）。
AC代码如下。通过时间1：59。
#include<bits/stdc++.h>
using namespace std;
int n, m, tp, tq, isa, dis[200005], color[200005];
int ans[200005], tmp[200005], tmq[200005];
vector<int> G[200005];
void addedge(int u, int v){
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int u, int f){
if(isa == -1) return;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(v == f) continue;
dis[v] = dis[u] + 1;
if(!color[v]) {
color[v] = 3-color[u];
dfs(v, u);
}
else if(color[v] + color[u]!= 3){
isa = -1;
return;
}
}
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++)
cin >> tmp[i];
for(int i = 0; i < m; i++)
cin >> tmq[i];
for(int i = 0; i < m; i++){
if(tmp[i] == tmq[i]) isa = -1;
addedge(tmp[i], tmq[i]);
}
for(int i = 1; i <= n; i++){
if(!color[i] && isa != -1) {
color[i] = 1;
dfs(i,0);
}
}
if(isa == -1) cout << "No" << endl;
else cout << "Yes" << endl;
return 0;
}
C 平方和的波动
试题题面
内存限制：1024MB 时间限制：2s
题目描述
在一个物理实验中，研究员需要观察 \(n\) 个独立粒子的能量叠加态。
已知第 \(i\) 个粒子的基础能量值为 \(x_i\)，其取值范围被限定在闭区间 \([a_i, b_i]\) 内，且 \(x_i\) 必须为整数。
实验的总能量指标 \(S\) 定义为所有粒子能量的平方和，即：
现在的任务是：计算在所有可能的 \(x_i\) 取值组合下，总能量指标 \(S\) 一共有多少种不同的可能取值？
输入格式
第一行包含一个正整数 \(n\)，表示粒子的数量。
接下来的 \(n\) 行，每行包含两个正整数 \(a_i\) 和 \(b_i\)，表示第 \(i\) 个粒子的能量取值区间。
输出格式
输出一行一个整数，表示总能量指标 \(S\) 的不同取值种数。
样例输入1
样例输出1
数据范围
\(1 \le n \le 100\)
\(1 \le a_i \le b_i \le 100\)
WriteUp
一个很经典的bitmap问题，平方和可能达到\(10^6\)，不过这一数据还是相对较小的。bitsetnxt |= (cur << v)：将 cur 的所有位左移 \(v\) 位。如果平方和 \(s\) 可达，那么加上当前粒子的贡献 \(v\) 后，新的平方和 \(s+v\) 就可达，将左移后的位集与 nxt 进行按位或操作。处理完当前粒子后，cur 更新为新的可达状态，准备处理下一个粒子。最后cur.count() 返回 cur 中 1 的个数，即所有粒子处理完后可达的平方和数量。bitset在这一操作中是高效的。
AC代码如下。通过时间3：12。
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 100 * 100 * 100;
bitset<MAXS+1> cur, nxt;
int main() {
int n;
cin >> n;
cur[0] = 1;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
nxt.reset();
for (int x = a; x <= b; x++) {
int v = x * x;
nxt |= (cur << v);
}
cur = nxt;
}
cout << cur.count() << endl;
return 0;
}
D 三元组
试题题面
内存限制：1024MB 时间限制：2s
题目描述
给定一组编号为 \(1\) 到 \(N\) 的卡片，第 \(i\) 张卡片上写着一个正整数 \(B_i\)。
现在需要统计有多少个有序三元组 \((x, y, z)\) 满足：
- \(1 \le x, y, z \le N\)；
- 卡片 \(x\) 与卡片 \(y\) 上数字的乘积，恰好等于卡片 \(z\) 上的数字。也就是说，需要满足：
注意：
- 三个位置是有序的，\((x, y, z)\) 与 \((y, x, z)\) 视为不同；
- 三个位置允许相同；
- 即使若干张卡片上的数字相同，只要位置不同，也要分别计数。
请输出满足条件的三元组数量。
输入格式
第一行输入一个整数 \(N\)。
接下来 \(N\) 行，第 \(i\) 行输入一个正整数 \(B_i\)。
输出格式
输出一个整数，表示满足条件的有序三元组个数。
样例输入1
样例输出1
样例输入2
6
1
123456789123456789123456789
123456789123456789123456789
2
246913578246913578246913578
246913578246913578246913578
样例输出2
数据范围
- \(1 \le N \le 1000\)
- \(1 \le B_i < 10^{1000}\)
所有输入的 \(B_i\) 均为十进制表示的正整数。
Write Up
叽里咕噜说什么呢，大的数据说是，和我的python说去吧。很奇妙的是直接双重循环没通过，时间超限 94/100，然后加了个a>b就跳出的判断，渐进时间复杂度没改变就过了，卡常？
AC代码如下。通过时间3：39。
from collections import Counter
n = int(input())
arr = [int(input()) for i in range(n)]
freq = Counter(arr)
vals = list(freq.keys())
ans = 0
for a in vals:
for b in vals:
if a > b:
continue
p = a * b
if p in freq:
if a!=b:
ans += 2 * freq[a] * freq[b] * freq[p]
else:
ans += freq[a] * freq[b] * freq[p]
print(ans)
E 时空覆盖器
试题题面
内存限制：1024MB 时间限制：2s
题目描述
在数轴上会出现 \(N\) 个目标。
对于每个 \(1 \le i \le N\)，第 \(i\) 个目标会在时刻 \(T_i\) 出现在坐标 \(X_i\)，且只会出现一次。
现在有一个“时空覆盖器”，它的持续时间为 \(D\)，覆盖长度为 \(W\)。
你只能使用它一次，具体操作如下：
选择正整数 \(S\) 和 \(L\)。
你会在时刻 \(S-0.5\) 时启动装置，使其覆盖区间
并在时刻 \(S+D-0.5\) 时关闭装置。
在装置启动到关闭的这段时间内，所有出现在其覆盖范围内的目标都可以被捕获。
装置在启动后不能移动，关闭后也不能再次使用。
请你求出，最多能够捕获多少个目标。
输入格式
第一行包含三个整数 \(N, D, W\)。
接下来 \(N\) 行，每行包含两个整数 \(T_i, X_i\)，表示第 \(i\) 个目标出现的时刻和坐标。
输出格式
输出一个整数，表示最多能捕获的目标数量。
样例输入1
样例输出1
样例解释
一种最优方案是选择 \(S=3, L=2\)。
这样装置会在时刻 \(2.5\) 到 \(6.5\) 之间工作，并覆盖区间
因此，以下目标会被捕获：
- 在时刻 \(3\)、坐标 \(4\) 出现的目标
- 在时刻 \(6\)、坐标 \(4\) 出现的目标
- 在时刻 \(5\)、坐标 \(2\) 出现的目标
- 在时刻 \(4\)、坐标 \(2\) 出现的目标
- 在时刻 \(4\)、坐标 \(3\) 出现的目标
共 \(5\) 个。
数据范围
\(1 \le N \le 2 \times 10^5\)
\(1 \le D \le 2 \times 10^5\)
\(1 \le W \le 2 \times 10^5\)
\(1 \le T_i \le 2 \times 10^5\)
\(1 \le X_i \le 2 \times 10^5\)
所有 \((T_i, X_i)\) 两两不同
输入中的所有数均为整数。
Write Up
这道题还挺难的，将二维的时空覆盖问题转化为一维的空间区间覆盖问题，并通过动态维护时间窗口内的目标点，使用线段树加速查询与更新操作。
AC代码如下。通过时间【封榜后】。
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
int mx[1000005], tag[1000005];
void pushup(int rt) {
mx[rt] = max(mx[rt * 2], mx[rt * 2 + 1]);
}
void pushdown(int rt) {
if (tag[rt]) {
int ls = rt *2, rs = rt * 2 + 1;
mx[ls] += tag[rt];
mx[rs] += tag[rt];
tag[ls] += tag[rt];
tag[rs] += tag[rt];
tag[rt] = 0;
}
}
void update(int L, int R, int v, int l, int r, int rt) {
if (L <= l && r <= R) {
mx[rt] += v;
tag[rt] += v;
return;
}
pushdown(rt);
int mid = (l + r) / 2;
if (L <= mid) update(L, R, v, l, mid, rt*2);
if (R > mid) update(L, R, v, mid + 1, r, rt*2+1);
pushup(rt);
}
int query() {
return mx[1];
}
} seg;
vector<int> add[200005], del[200005];
int maxT = 0, maxX = 0;
int N, D, W, T, X, sbegin, send;
int main() {
cin >> N >> D >> W;
for (int i = 0; i < N; i++) {
cin >> T >> X;
maxT = max(maxT, T);
maxX = max(maxX, X);
sbegin = max(1, T - D + 1);
send = T + 1;
add[sbegin].push_back(X);
del[send].push_back(X);
}
int ans = 0;
for (int i = 1; i <= maxT + 1; i++) {
for (int x : del[i]) {
int L = max(1, x - W + 1);
seg.update(L, x, -1, 1, maxX, 1);
}
for (int x : add[i]) {
int L = max(1, x - W + 1);
seg.update(L, x, 1, 1, maxX, 1);
}
ans = max(ans, seg.query());
}
cout << ans << endl;
return 0;
}
F 集合异或
内存限制：256MB 时间限制：1s
试题题面
题目描述
给定一个由 \(n\) 个整数构成的数组 \(\{a_1, a_2, \dots, a_n\}\)。你需要将数组中的每一个元素不重不漏地划分进入 \(k\) 个集合 \(S_1, S_2, \dots, S_k\) 中（\(k\) 是给定的正整数），使得这些集合各自的异或和再做异或后的结果尽可能大。
形式化地，设每个集合 \(S_i\) 的异或和为 \(\bigoplus_{a \in S_i} a\)，你需要求出：
的值，且 \(S_1, S_2, \dots, S_k\) 构成数组 \(\{a_1, a_2, \dots, a_n\}\) 的一个划分（即每个元素恰好属于其中某一个集合）。
特别地，若某个集合为空集，规定其异或和为 \(0\)。
名词解释
- 按位异或：\(\oplus\) 表示按位异或运算。两个整数按位异或的结果，是将它们的二进制表示逐位做异或运算（相同为 \(0\)，不同为 \(1\)）所得到的整数。例如，\((5)_{10} = (101)_2\)，\((3)_{10} = (011)_2\)，则 \(5 \oplus 3 = (110)_2 = (6)_{10}\)。
输入格式
第一行输入两个整数 \(n, k\) (\(1 \le k \le n \le 10^5\))，分别表示数组 \(a_i\) 中的元素个数，以及需要划分的集合的数量。
第二行输入 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\))，代表数组中的各个元素。
输出格式
输出一行一个整数，即将数组 \(\{a_1, a_2, \dots, a_n\}\) 中的每一个元素不重不漏地划分进 \(k\) 个集合后，这些集合的异或和再做异或所能取到的最大值。
样例输入1
样例输出1
样例输入2
样例输出2
样例解释
在第二个样例中，数组为 \(\{1,1,4,5,1,4\}\)，下面给出一种最优划分方案：
- 令 \(S_1 = \{1,1,5,1\}\)，\(S_2 = \{4,4\}\)，则 \(S_1\) 的异或和为 \(1 \oplus 1 \oplus 5 \oplus 1 = 4\)，\(S_2\) 的异或和为 \(4 \oplus 4 = 0\)；
- 最终结果为 \(4 \oplus 0 = 4\)。
可以验证，不存在任何划分方案使结果超过 \(4\)，故答案为 \(4\)。
Write Up
骗你的，无论怎么加括号都不影响结果，直接全部异或输出即可。
AC代码如下。通过时间1：00。
#include <iostream>
using namespace std;
int n, k;
long long a[100005], ans = 0;
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> a[i];
ans = ans ^ a[i];
}
cout << ans << endl;
return 0;
}
G 骰子示数
试题题面
内存限制：256MB 时间限制：1s
题目描述
有两个正方体形状的骰子。与常规骰子不同，这两个骰子的每一面都可以任意地展示一个 \(0 \sim 7\) 的整数。
抛出两个骰子后，将两个骰子正上方的示数从左到右拼接，构成一个两位数，其值即为本次的投掷结果。例如，两个骰子正上方的示数从左到右分别为 \(0\) 和 \(1\)，则构成的结果为 "01"，其值为 \(1\)。
特别地：
- 数字 \(6\) 因为可以旋转，也可以被看作 \(9\)；
- 两个骰子的左右相对位置是任意的，即两个骰子可以互换左右位置。
给定两个骰子各个面上所写的数值，请输出这两个骰子所有可能的投掷结果的值，按照从小到大的顺序输出，相同的值只输出一次。
输入格式
第一行输入六个整数 \(a_1, a_2, a_3, a_4, a_5, a_6\) \((0 \le a_i \le 7)\)，表示第一个骰子六个面上的数值。
第二行输入六个整数 \(b_1, b_2, b_3, b_4, b_5, b_6\) \((0 \le b_i \le 7)\)，表示第二个骰子六个面上的数值。
输出格式
在一行上按照从小到大的顺序输出所有可能的投掷结果的值，相邻两个数之间用一个空格隔开。相同的值只输出一次。
样例输入1
样例输出1
样例输入2
样例输出2
提示
样例 2 解释
在第二个样例中，第一个骰子可以展示的数值为 \(\{0,1,2\}\)，第二个骰子可以展示的数值为 \(\{0,1,3\}\)。由于两个骰子的左右位置任意，所有可能的投掷结果如下：
- 第一个骰子在左、第二个骰子在右时：
- 第一个骰子示数为 \(0\)，第二个骰子示数为 \(0\)，结果为
"00"，其值为 \(0\)； - 第一个骰子示数为 \(0\)，第二个骰子示数为 \(1\)，结果为
"01"，其值为 \(1\)； - 第一个骰子示数为 \(0\)，第二个骰子示数为 \(3\)，结果为
"03"，其值为 \(3\)； - 第一个骰子示数为 \(1\)，第二个骰子示数为 \(0\)，结果为
"10"，其值为 \(10\)； - 第一个骰子示数为 \(1\)，第二个骰子示数为 \(1\)，结果为
"11"，其值为 \(11\)； - 第一个骰子示数为 \(1\)，第二个骰子示数为 \(3\)，结果为
"13"，其值为 \(13\)； - 第一个骰子示数为 \(2\)，第二个骰子示数为 \(0\)，结果为
"20"，其值为 \(20\)； - 第一个骰子示数为 \(2\)，第二个骰子示数为 \(1\)，结果为
"21"，其值为 \(21\)； -
第一个骰子示数为 \(2\)，第二个骰子示数为 \(3\)，结果为
"23"，其值为 \(23\)。 -
第二个骰子在左、第一个骰子在右时：
- 额外产生的结果为
"02"（值为 \(2\)）、"12"（值为 \(12\)）、"30"（值为 \(30\)）、"31"（值为 \(31\)）、"32"（值为 \(32\)），其余与上方重复。
去重并从小到大排序后，得到输出 \(0\ 1\ 2\ 3\ 10\ 11\ 12\ 13\ 20\ 21\ 23\ 30\ 31\ 32\)。
Write Up
真正的签到题，直接写个模拟，略。
AC代码如下。通过时间0：54。
#include<iostream>
using namespace std;
int hash1[10], hash2[10], tmp, ans[105];
int main(){
for(int i = 0; i < 6; i++){
cin >> tmp;
hash1[tmp] ++;
if(tmp == 6) hash1[9] ++;
}
for(int i = 0; i < 6; i++){
cin >> tmp;
hash2[tmp] ++;
if(tmp == 6) hash2[9] ++;
}
for(int i = 0; i < 100; i++){
int ta = i % 10;
int tb = i / 10;
if((hash1[ta] > 0 && hash2[tb] > 0) || (hash2[ta] > 0 && hash1[tb] > 0))
ans[i]++;
}
for(int i = 0; i < 100; i++)
if(ans[i])
cout << i << " ";
cout << endl;
return 0;
}
H 好友链追踪器
试题题面
内存限制：256MB 时间限制：1s
题目描述
在现代社交网络中，共有 \(n\) 个用户，编号为 \(1\) 到 \(n\)。初始时，任意两个用户之间均没有好友关系。
现在，给定 \(q\) 次操作，每次操作为以下三种之一：
- 添加好友：在用户 \(a\) 和用户 \(b\) 之间建立好友关系；
- 解除好友：移除用户 \(a\) 和用户 \(b\) 之间的好友关系；
- 查询链长：查询用户 \(a\) 和用户 \(b\) 之间最短好友链的长度。若两人之间不存在好友链，则输出 \(-1\)。
名词解释
- 好友链：从用户 \(u\) 出发，沿好友关系依次经过若干用户，最终到达用户 \(v\)，中途不重复经过同一用户，所经过的路径称为一条从 \(u\) 到 \(v\) 的好友链。好友链的长度定义为路径中所经过的好友关系（即边）的数量。特别地，若 \(a=b\)，则链长为 \(0\)。
- 最短好友链：在用户 \(a\) 与用户 \(b\) 之间所有好友链中，长度最短的一条，称为最短好友链。
输入格式
第一行输入两个整数 \(n\) 和 \(q\) \((1 \le n, q \le 10^3)\)，分别表示用户数量和操作次数。
此后 \(q\) 行，每行先输入一个整数 \(op\) \((1 \le op \le 3)\) 代表操作类型，编号同题干。随后在同一行：
- 若 \(op=1\)，输入两个整数 \(a\) 和 \(b\) \((1 \le a,b \le n; a \neq b)\)，表示在用户 \(a\) 和用户 \(b\) 之间建立好友关系；
- 若 \(op=2\)，输入两个整数 \(a\) 和 \(b\) \((1 \le a,b \le n; a \neq b)\)，表示移除用户 \(a\) 和用户 \(b\) 之间的好友关系；
- 若 \(op=3\)，输入两个整数 \(a\) 和 \(b\) \((1 \le a,b \le n)\)，表示查询用户 \(a\) 和用户 \(b\) 之间最短好友链的长度。
输出格式
对于每个 \(op=3\) 的操作，在一行上输出一个整数，代表用户 \(a\) 和用户 \(b\) 之间最短好友链的长度。若两人之间不存在好友链，则输出 \(-1\)。
样例输入1
样例输出1
样例输入2
样例输出2
提示
样例 1 解释
在这个样例中，共有 \(6\) 个用户，执行 \(8\) 次操作：
- 操作 \(1\)：建立用户 \(1\) 与用户 \(2\) 的好友关系，当前好友关系为 \(1-2\)；
- 操作 \(2\)：建立用户 \(2\) 与用户 \(3\) 的好友关系，当前好友关系为 \(1-2-3\)；
- 操作 \(3\)：建立用户 \(3\) 与用户 \(4\) 的好友关系，当前好友关系为 \(1-2-3-4\)；
- 操作 \(4\)：建立用户 \(4\) 与用户 \(5\) 的好友关系，当前好友关系为 \(1-2-3-4-5\)；
- 操作 \(5\)：查询用户 \(1\) 到用户 \(5\) 的最短好友链长度。当前路径为 \(1 \to 2 \to 3 \to 4 \to 5\)，长度为 \(4\)，故输出 \(4\)；
- 操作 \(6\)：移除用户 \(2\) 与用户 \(3\) 的好友关系，当前好友关系变为两个连通块：\(\{1,2\}\) 与 \(\{3,4,5\}\)；
- 操作 \(7\)：查询用户 \(1\) 到用户 \(5\) 的最短好友链长度。由于两人不连通，故输出 \(-1\)；
- 操作 \(8\)：查询用户 \(1\) 到用户 \(3\) 的最短好友链长度。由于两人不连通，故输出 \(-1\)。
Write Up
好友关系其实就是一张图，如果有好友关系就存在一条无向边，反之不存在。当收到查询时直接单源最短路Dijkstra输出结果。同样是照着深入浅出的板子打的。
令人有些困惑，AC代码这份相当于在删除好友后把边的权重置为了\(+\infty\)，但是先前我们尝试了直接把边删除（更直观）但是得到了答案错误 90/100，这两个应该是等价的，可能有哪里没注意到写错了，不管了。
AC代码如下。通过时间3：05。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500000
const int inf = 2000;
int n, m, cnt = 0;
int dis[MAXN], h[MAXN], to[MAXN], val[MAXN], nxt[MAXN], vis[MAXN];
int mq, op, aaa, bbb;
void add(int a, int b, int c){
to[++cnt] = b;
val[cnt] = c;
nxt[cnt] = h[a];
h[a] = cnt;
to[++cnt] = a;
val[cnt] = c;
nxt[cnt] = h[b];
h[b] = cnt;
}
void del(int a, int b){
for(int i = h[a]; i; i = nxt[i]){
if(to[i] == b){
val[i] = 2000;
}
}
for(int i = h[b]; i; i = nxt[i]){
if(to[i] == a){
val[i] = 2000;
}
}
}
struct node{
int v, w;
friend bool operator < (node a, node b){
return a.w > b.w;
}
} tmp;
priority_queue <node> q;
void Dijkstra(int s, int teg){
for(int i = 0; i <= n; i++)
dis[i] = inf;
for(int i = 0; i <= n; i++)
vis[i] = 0;
dis[s] = 0;
while(!q.empty()) q.pop();
tmp.v = s, tmp.w = 0; q.push(tmp);
while(!q.empty()){
int u = q.top().v;
q.pop();
if(vis[u] != 0) continue;
vis[u] = 1;
for(int i = h[u]; i; i = nxt[i]){
if(dis[to[i]] > dis[u] + val[i]){
dis[to[i]] = dis[u] + val[i];
tmp.w = dis[to[i]], tmp.v = to[i]; q.push(tmp);
}
}
}
}
int main(){
cin >> n >> mq;
for(int i = 0; i < mq; i++){
cin >> op >> aaa >> bbb;
if(op == 1)
if(aaa != bbb)
add(aaa, bbb, 1);
if(op == 2)
if(aaa != bbb)
del(aaa, bbb);
if(op == 3) {
if(aaa == bbb) cout << "0" << endl;
else {
Dijkstra(aaa, bbb);
if(dis[bbb] <= 1005) cout << dis[bbb] << endl;
else cout << "-1" << endl;
}
}
}
return 0;
}