哈尔滨华德学院第十七届程序设计竞赛题解

比赛设置

• 校内赛：共 15 题（A～O），时长 2.5 小时，不允许携带纸质或电子资料。
• 同步赛：共 13 题，删除校内赛的 B、C 两题，其余题目相同，时长 2.5 小时，允许携带电子版资料。

题目难度梯度合理，涵盖基础语法、前缀和、排序、动态规划、最短路、广度优先搜索、二进制规律、模拟、平衡树、最小生成树性质、博弈论与换根 DP、二分图最大权匹配等多个知识点。适合算法初学者入门与巩固，也包含一定的思维与代码实现挑战。本题题解全部代码注释都是deepseek加的，诶AI进步太快了，内测发现豆包都能AK这套题。

题目列表

A. 签到了签到了

题意简述

输出固定字符串 HHDU2026。

算法思路

这是一道纯粹的签到题，不涉及任何输入与逻辑处理。直接使用输出语句将目标字符串打印到标准输出即可。

在 C++ 中可以使用 cout，在 C 中可以使用 printf，其他语言类似。

复杂度分析

• 时间复杂度：
• 空间复杂度：

标程

#include <iostream>
using namespace std;

int main() {
        // 直接输出固定字符串即可，注意换行
        cout << "HHDU2026"<< endl;
}

B. a大于b吗？

题意简述

输入两个整数 和 ，它们的绝对值可能高达 。要求判断 与 的大小关系，并输出相应的符号：

• 若 ，输出 >
• 若 ，输出 =
• 若 ，输出 <

算法思路

由于数据范围较大（），需要使用 64 位整数类型（如 C++ 中的 long long）进行存储。读取两个数后，直接通过 if-else 语句比较大小并输出对应字符即可。

需要注意：C++ 中 cin 和 cout 默认可以正确处理 long long 类型的输入输出。

复杂度分析

• 时间复杂度：
• 空间复杂度：

标程

#include <iostream>
using namespace std;

int main() {
    // 使用 long long 存储绝对值可能高达 1e18 的整数
    long long int a, b;
    cin>>a>>b;
    // 按大小关系输出对应符号
    if(a==b){
        cout<<"="<<endl;
    }else if(a>b){
 cout<<">"<<endl;
    }else if(a<b){
 cout<<"<"<<endl;
    }
}

C. 找找2026

题意简述

给定 个整数，题目保证这些数中至少包含一个 2026。请找出第一个出现的 2026，并输出它是第几个输入的整数（下标从 1 开始）。

算法思路

从下标 开始遍历输入的整数，当遇到值为 2026 的数时，直接输出当前下标并结束程序。

因为只需要第一个匹配项，使用 break 或 return 提前退出可以提高一点效率（虽然本题 ，影响不大）。

复杂度分析

• 时间复杂度：，最坏情况下需要检查所有元素。
• 空间复杂度： 或 （取决于是否存储整个数组，标程使用数组存储）。

标程

#include<bits/stdc++.h>
using namespace std;
// 数组开得较大，实际 n <= 100，预留足够空间
int a[1100000], n, m;
int main() {
	cin >> n;
	// 从下标 1 开始读取 n 个整数
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		// 找到第一个值为 2026 的元素
		if (a[i] == 2026)
		{
			// 输出该元素的位置（从 1 开始计数）
			cout << i << endl;
			// 找到后提前结束，不再处理后续数字
			break;
		}
	}
	return 0;
}

D. 华德学院的校训

题意简述

哈尔滨华德学院的校训标准拼音为：chengyi qiuzhen duxue qiangji（单词之间严格使用单个空格分隔）。

现给出 个只包含小写字母和空格的字符串，要求判断每个字符串是否与标准拼音完全相等（包括空格的数量和位置）。

算法思路

本题主要考察字符串的输入与比较。

1. 使用 getline 读取整行字符串，因为它能保留空格。
2. 注意在读取 之后，输入缓冲区中会残留一个换行符，需要使用 cin.ignore() 将其忽略，否则第一次 getline 会读到空行。
3. 将读取的字符串与预定义的标准字符串直接使用 == 比较，输出 YES 或 NO。

复杂度分析

• 时间复杂度：，字符串长度不超过 100，完全足够。
• 空间复杂度：，用于存储临时字符串。

标程

#include <iostream>
#include <string>
using namespace std;
// 预定义标准拼音字符串
string s = "chengyi qiuzhen duxue qiangji";
int main() {
    int T;
    cin >> T;
    // 忽略输入流中 T 之后的换行符，防止影响后续 getline
    cin.ignore();
    while (T--) {
        string s1;
        // 读取包含空格的一整行
        getline(cin, s1);
        // 严格比较，完全相等则输出 YES，否则 NO
        if (s1 == s) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

E. 运动会积分统计

题意简述

给定一个长度为 的整数数组 （积分可能为负），以及 次询问。每次询问给出左右端点 ，需要快速回答区间 内所有元素的和。

算法思路

本题是前缀和的经典应用。

1. 预处理前缀和数组 pre，其中 pre[i] = a[1] + a[2] + ... + a[i]。
   递推公式：pre[i] = pre[i-1] + a[i]。
2. 对于每次询问 ，区间和可通过 pre[r] - pre[l-1] 在 时间内得到。

注意数据范围：，，累加结果可能超过 32 位整数范围，应使用 long long 类型存储前缀和。

复杂度分析

• 预处理时间复杂度：
• 单次查询时间复杂度：
• 总体时间复杂度：
• 空间复杂度：

标程

#include <bits/stdc++.h>
using namespace std;
// 前缀和数组，使用 long long 防止数据溢出
long long int pre[2100000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    // 预处理前缀和，pre[0] 默认为 0
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        // 递推：pre[i] = pre[i-1] + a[i]
        pre[i] = pre[i - 1] + x;
    }
    // 处理每次询问
    while (q--) {
        int l, r;
        cin >> l >> r;
        // 区间和 = pre[r] - pre[l-1]
        cout << pre[r] - pre[l - 1] << '\n';
    }
    return 0;
}

F. 排行榜生成

题意简述

举办了一场比赛，有 名选手、 道题目。输入直接给出每位选手在每道题上的总罚时（若为 0 则表示未通过该题，否则表示通过且罚时为该值）。

需要按照 ACM 规则生成排行榜：

• 解题数：罚时非零的题目数量。
• 总罚时：所有非零罚时之和。
• 排序规则：
  1. 解题数降序（越多越靠前）
  2. 解题数相同时，总罚时升序（越少越靠前）
  3. 若仍相同，则按学号升序排列，并且排名并列（例如两人并列第1，则下一人排名为第3）。
• 没有任何通过题目的人，解题数和总罚时均为 0，排名统一为最后一名（并列）。

算法思路

1. 数据统计：遍历每名选手的每道题，累加解题数与总罚时。
2. 排序：根据规则自定义比较函数，使用 sort 对选手数组排序。
3. 计算排名：遍历排序后的数组，若当前选手的解题数和总罚时与上一人完全相同，则排名与上一人相同；否则，排名等于当前遍历的次序（从 1 开始计数）。

复杂度分析

• 时间复杂度：。统计 ，排序 。
• 空间复杂度：，存储选手信息。

标程

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// 选手信息结构体
struct xuanshou {
    string sid;      // 学号
    int solved;      // 解题数
    int penalty;     // 总罚时
}xuanshou1[2100000];

// 自定义排序规则
bool cmp(const xuanshou &a, const xuanshou &b) {
    // 解题数降序
    if (a.solved != b.solved) return a.solved > b.solved;
    // 解题数相同，按总罚时升序
    if (a.penalty != b.penalty) return a.penalty < b.penalty;
    // 以上均相同，按学号升序
    return a.sid < b.sid; 
}

int main() {
    int n, m;
    cin >> n >> m;
    // 读入每名选手的数据
    for (int i = 0; i < n; i++) {
        cin >> xuanshou1[i].sid;
        xuanshou1[i].solved = 0;
        xuanshou1[i].penalty = 0;
        for (int j = 0; j < m; j++) {
            int t;
            cin >> t;
            // 罚时非零表示通过该题
            if (t > 0) {
                xuanshou1[i].solved++;          // 解题数加一
                xuanshou1[i].penalty += t;      // 累加罚时
            }
        }
    }
    // 按规则排序
    sort(xuanshou1, xuanshou1 + n, cmp);
    int rank = 1; // 当前实际排名
    for (int i = 0; i < n; i++) {
        // 如果与前面选手的解题数和罚时不全部相同，则更新排名为当前位次
        if (i > 0 && (xuanshou1[i].solved != xuanshou1[i-1].solved || xuanshou1[i].penalty != xuanshou1[i-1].penalty)) {
            rank = i + 1;
        }
        // 输出排名、学号、解题数、总罚时
        cout << rank << " " << xuanshou1[i].sid << " " << xuanshou1[i].solved << " " << xuanshou1[i].penalty << endl;
    }
    return 0;
}

G. 军训物资分配

题意简述

经典的 0/1 背包问题：有 件物资，每件有重量 和价值 。背包总容量为 。每件物资最多选一次，求在不超过背包容量的前提下能获得的最大总价值。

算法思路

使用动态规划解决 0/1 背包问题。

• 状态定义：dp[j] 表示背包容量为 时能获得的最大价值。
• 状态转移：对于每件物品 ，倒序遍历容量 （从 到 ），执行 dp[j] = max(dp[j], dp[j - w] + v)。
• 倒序遍历的原因：确保每件物品最多被选取一次（防止同一物品被重复使用，即避免完全背包的效果）。

由于 ，，总时间复杂度 在可接受范围内。价值 可达 ，需要使用 long long 类型存储 dp 数组。

复杂度分析

• 时间复杂度：
• 空间复杂度：，使用一维滚动数组优化。

标程

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// dp[j] 表示容量为 j 时能获得的最大价值，使用 long long
long long int dp[21000000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, W;
    cin >> n >> W;
    // 遍历每一件物品
    for (int i = 0; i < n; ++i) {
        int w, v;
        cin >> w >> v;
        // 倒序遍历容量，保证同一件物品最多被选一次
        for (int j = W; j >= w; --j) {
            // 状态转移：选或不选当前物品
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    // 输出容量为 W 时的最大价值
    cout << dp[W] << '\n';
    return 0;
}

H. 最优通勤路线

题意简述

给定一个 个点、 条边的无向带权连通图。要求计算从起点 出发，必须经过点 ，最后到达终点 的最短路径总长度。

算法思路

由于所有边权非负，且需要计算两点之间的最短路径，使用 Dijkstra 算法 是最合适的。

问题要求路径必须依次为 ，这等价于计算：

因此，只需执行两次 Dijkstra：

1. 以 为源点，得到所有点的最短距离数组 dist_s；
2. 以 为源点，得到所有点的最短距离数组 dist_x；
3. 最终答案为 dist_s[x] + dist_x[t]。

需要注意：

• 点数 ，边数 ，必须使用堆优化的 Dijkstra（时间复杂度 ）。
• 可能存在重边和自环，标准 Dijkstra 实现可以自动处理（自环不会影响最短距离，重边会在松弛时自然取较小值）。
• 若 或 或三者重合，算法同样适用（dist_s[x] 为 0）。

复杂度分析

• 时间复杂度：
• 空间复杂度：

标程

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include<queue>
#include<unordered_map>
#include<queue>
using namespace std;
// vis: 从 s 出发的最短距离；vis2: 从 x 出发的最短距离
long long int vis[210000],vis2[210000],n,m,syd,x,s,t;
// 链式前向星存图：qxx_top 为每个点的第一条边索引
long long int qxx_top[10000000];
// 边结构体：v 权值，next 下一条边索引，zd 终点
struct dl {
    long long int v;
    long long int next;
    long long int zd;
}qxx[1100000];
// 优先队列节点：szd 当前点编号，qz 源点到该点的最短距离
struct dian {
    long long int szd, qz;
    // 按距离从小到大排序（小顶堆）
    bool operator <(const dian& x)const
    {
        return x.qz < qz;
    }
};
// 向图中添加无向边，实际插入两条有向边
void add_qxx(int qd, int zd, int qz)
{
    qxx[++syd].next = qxx_top[qd];
    qxx[syd].zd = zd;
    qxx[syd].v = qz;
    qxx_top[qd] = syd;
}
priority_queue<dian>diandl;
// jyh 与 jyh2 为 Dijkstra 访问标记，防止重复处理已确定最短距离的点
int jyh[210000],jyh2[210000];
int main() {
    cin >> n>>m;
    // 初始化距离为极大值
    for (int i = 0; i <= n; i++)
    {
         vis[i] = 10000000000000000;
         vis2[i] = 10000000000000000;
    } 
    // 读取边，建立无向图
    for (int i = 0; i < m; i++)
    {
        long long int x, y,v;
        cin >> x >> y>>v;
        add_qxx(x, y, v);
        add_qxx(y, x, v);

    }
    cin>>s>>x>>t;
    // 第一次 Dijkstra：从 s 出发
    diandl.push({ s,0 });
    vis[s] = 0;
    while (diandl.size())
    {
        dian xz = diandl.top();
        diandl.pop();
        // 若已处理过该点，跳过
        if (jyh[xz.szd])continue;
        jyh[xz.szd] = 1;
        // 遍历邻接边，尝试松弛操作
        for (int i = qxx_top[xz.szd]; i != 0; i = qxx[i].next)
        {
            if (vis[qxx[i].zd] > vis[xz.szd] + qxx[i].v)
            {
                vis[qxx[i].zd] = vis[xz.szd] + qxx[i].v;
                if (!jyh[qxx[i].zd])
                {
                    diandl.push({ qxx[i].zd,vis[qxx[i].zd] });
                }
            }
        }
    }
    
    // 第二次 Dijkstra：从 x 出发
    diandl.push({ x,0 });
    vis2[x] = 0;
    while (diandl.size())
    {
        dian xz = diandl.top();
        diandl.pop();
        if (jyh2[xz.szd])continue;
        jyh2[xz.szd] = 1;
        for (int i = qxx_top[xz.szd]; i != 0; i = qxx[i].next)
        {
            if (vis2[qxx[i].zd] > vis2[xz.szd] + qxx[i].v)
            {
                vis2[qxx[i].zd] = vis2[xz.szd] + qxx[i].v;
                if (!jyh2[qxx[i].zd])
                {
                    diandl.push({ qxx[i].zd,vis2[qxx[i].zd] });
                }
            }
        }
    }
    // 若点 x 或点 t 不可达，则按题目逻辑异常退出（实际上保证连通）
    if(vis[x]==10000000000000000||vis2[t]==10000000000000000)
        exit(-10086);
    // 答案为 s 到 x 的最短距离 + x 到 t 的最短距离
    cout<<vis[x]+vis2[t];
}

I. 走迷宫

题意简述

在一个四维网格迷宫中，每个维度的坐标范围均为 。格子状态用字符表示：S 为起点，E 为终点，. 为可通行，# 为障碍。每次移动只能在某一个维度上变化 （曼哈顿距离为 1）。求从起点到终点的最短移动步数，若无法到达则输出 。

算法思路

本题是标准的广度优先搜索（BFS）在四维空间的应用。

• 状态表示：用四元组 表示一个位置。
• 状态转移：每一步可以选择 8 个方向之一（每个维度正负两个方向）。
• 边界条件：不能越出 ，且目标格子不能是 #。
• 搜索过程：使用队列进行 BFS，用 dis 数组记录到达每个格子的最短步数（同时兼作访问标记）。第一次到达终点的步数即为最短步数。

由于 ，整个状态空间最多为 ，BFS 完全可行。

输入处理细节

标程中采用四重循环按 的顺序读取字符。这与题目描述中“时间点、空间层、矩阵”的输入格式相对应，需要注意读入顺序。

复杂度分析

• 时间复杂度：，每个状态最多入队一次。
• 空间复杂度：，用于存储迷宫和距离数组。

标程

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 20;

int n;
// 起点、终点的四维坐标
int sx, sy, sz, st;
int ex, ey, ez, et;
// 四维迷宫
char g[N][N][N][N];
// 距离数组，-1 表示未访问
int dis[N][N][N][N];
// 八个移动方向：每个维度 ±1
int dx[8] = {0, 0, 0, 0, 0, 0, 1, -1};
int dy[8] = {0, 0, 0, 0, 1, -1, 0, 0};
int dz[8] = {0, 0, 1, -1, 0, 0, 0, 0};
int dt[8] = {1, -1, 0, 0, 0, 0, 0, 0};

// 四维坐标结构体
struct E
{
	int x, y, z, t;
};

// 检查坐标是否在 [1, n] 范围内
inline bool check(int p)
{
	return p >= 1 && p <= n;
}

int bfs()
{
	memset(dis, -1, sizeof dis);
	queue<E> q;
	// 起点入队，距离为 0
	q.push({sx, sy, sz, st});
	dis[sx][sy][sz][st] = 0;
	
	while(q.size())
	{
		auto [x, y, z, t] = q.front();
		q.pop();
		
		// 尝试八个方向
		for(int i = 0; i < 8; i ++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			int nt = t + dt[i];
			// 坐标合法、未访问、不是障碍则入队
			if(check(nx) && check(ny) && check(nz) && check(nt) &&
				dis[nx][ny][nz][nt] == -1 && g[nx][ny][nz][nt] != '#')
			{
				q.push({nx, ny, nz, nt});
				dis[nx][ny][nz][nt] = dis[x][y][z][t] + 1;
			}
		}
	}
	
	// 返回到达终点的最短距离，若不可达则为 -1
	return dis[ex][ey][ez][et];
}


int main()
{
	int T;
	
	cin >> T;
	while(T --)
	{
		cin >> n;
		// 按 t, z, x, y 顺序读入四维迷宫
		for(int t = 1; t <= n; t ++)
			for(int z = 1; z <= n; z ++)
				for(int x = 1; x <= n; x ++)
					for(int y = 1; y <= n; y ++)
					{
						cin >> g[x][y][z][t];
						// 记录起点坐标
						if(g[x][y][z][t] == 'S')
							sx = x, sy = y, sz = z, st = t;
						// 记录终点坐标
						if(g[x][y][z][t] == 'E')
							ex = x, ey = y, ez = z, et = t;
					}
		
		cout << bfs() << endl;
	}
	return 0;
}

J. 奥义·影分身之术

题意简述

给定整数 ，数字集合为 。分裂规则：数字 分裂出左子 和右子 。

初始第 1 层只有一个数字 。此后每一层都由上一层的每个数字按规则分裂成两个数字（顺序拼接）。求第 层的第 个数字是多少。

算法思路

观察生成规律：

• 这是一个完全二叉树结构，第 层有 个节点。
• 从根节点（第1层第1个，值为0）到目标节点的路径可由 的二进制表示决定：从高位到低位（或低位到高位），0 代表向左走，1 代表向右走。
• 初始值为 。每向右走一次，当前值变为 ；向左走则值不变。
• 因此，最终的值等于初始值 加上路径中向右走的次数，再对 取模。
• 路径中向右走的次数恰好等于 的二进制表示中 1 的个数（即 popcount）。

综上，答案为 。

由于 可能非常大（达到 级别），不可能实际生成序列，必须使用这种 的数学方法。C++ 中可使用 __builtin_popcountll 计算 unsigned long long 类型数值的二进制中 1 的个数。

复杂度分析

• 时间复杂度：
• 空间复杂度：

标程

(注：标程中包含一些未使用的全局数组和函数，系出题人模板残留，不影响核心逻辑。)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector> 
#include <map>
#include <set>

#define LL unsigned long long

using namespace std;

typedef pair<LL , LL> PII;
int T;
const int N = 2 * 100010 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
map<int , set<int>> g;

// 以下数组和 dfs 函数为出题人模板残留，本题未使用
int st[N] , cen = 1 , res = 1;
void dfs(int u){
    for(auto i : g[u]){
        if(st[i] == 0){
            st[i] = 1;
            cen ++;
            res = max(res , cen);
            dfs(i);
            cen --;
            st[i] = 0;
        }
    }
}

void resolve()
{
    LL k , n , m;
    cin >> k >> n >> m;
    LL res = 0;
    // m 表示层中的第几个，转为从 0 开始的索引
    m --;
    // 计算 m 的二进制中 1 的个数（向右走的次数）
    while(m){
        res += m % 2;
        m /= 2;
    }
    // 结果对 k+1 取模
    res = res % (k + 1);
    cout << res;
}

int main()
{
    //     prime_init();
    //     combin_init();
    
    T = 1;
    while(T --)
    {
        resolve();
    }
}

K.不好，Alice和Bob又来做游戏了

题意简述

Alice 和 Bob 在一棵 个节点的树上进行游戏。先指定一个根 ，棋子初始放在根上。双方轮流将棋子从当前节点移动到它在有根树意义下的某个子节点。无法移动的一方判负，Alice 先手，双方均采取最优策略。

对于每一个节点 ，请你判断：若以 为根独立进行游戏，先手 Alice 是否必胜。若必胜输出 Alice，否则输出 Bob。

数据范围：。

这题有两种做法

第一种做法 博弈论、布尔换根 DP

《这个做法是验题人发现的 因此这个题目难度降低了一大截 防AK变成了中期题 悲》

题意简述

给定一棵 个节点的树，对每个节点作为根，判断有根树上的移动游戏（每次向子节点移动，无法移动者输）先手是否必胜。

算法思路

性质观察：在这类移动游戏中，一个局面的 SG 值等于其所有子节点 SG 值的 mex。先手必胜当且仅当 SG 值不为 0。

进一步观察：一个节点的 SG 值为 0，等价于其所有子节点的 SG 值都不为 0。
因此，一个节点是必胜态（SG ≠ 0）的充要条件是：至少存在一个子节点是必败态（SG = 0）。

基于这个布尔性质，可以直接用换根 DP 解决，无需计算具体的 SG 值和维护 mex。

• 设 dp[u] 表示以 u 为根的子树（固定 1 为根时）u 是否必胜。
• 设 up[u] 表示从父节点方向来的那棵子树是否使 u 必胜（即父方向是否提供了必败邻居）。
• 第一次 DFS（后序）求出 dp[u]。
• 第二次 DFS（换根）求出 up[u] 和最终答案 ans[u]。ans[u] 为真当且仅当 u 的所有邻居（包括父方向）中存在必败态。

复杂度分析

• 时间复杂度：，两次遍历。
• 空间复杂度：。

标程

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <random>
#include <string>
#include <utility>
using namespace std;

long long int n, m, syd;
long long int qxx_top[10000000];          // 前向星头指针数组
bool dfs1_dzt[210000], dfs2_dzt[210000], up[210000]; // dp:子树胜负, ans:最终答案(必败邻居计数), up:父方向状态

struct dl {
    long long int v;       // 权值（本题未用到）
    long long int next;    // 下一条边的索引
    long long int zd;      // 目标节点
} qxx[1100000];

void add_qxx(int qd, int zd, int qz) {
    qxx[++syd].next = qxx_top[qd];
    qxx[syd].zd = zd;
    qxx[syd].v = qz;
    qxx_top[qd] = syd;
}

// 第一次DFS：后序遍历，计算只考虑子树时的胜负状态 (dp[u])
int dfs(int u, int fa) {
    int dqzt = 0;                    // 假设子树内没有必败儿子
    for (int i = qxx_top[u]; i != 0; i = qxx[i].next) {
        int v = qxx[i].zd;
        if (v == fa) continue;
        dfs(v, u);                  // 先递归子节点
        if (dfs1_dzt[v] == 0)       // 如果儿子是必败态
            dqzt = 1;               // 当前节点就能靠这个儿子获胜
    }
    dfs1_dzt[u] = dqzt;             // 记录子树胜负
    return 0;
}

// 第二次DFS：换根DP，计算每个节点作为根时的答案
// up[u] 在进入本函数前已被父节点设置好，表示“父方向是否包含必败态（0表示父方向必败）”
int dfs2(int u, int fa) {
    int dqzt = 0;                   // 统计当前节点所有邻居中必败态的数量
    // 先检查所有子节点（子树方向）
    for (int i = qxx_top[u]; i != 0; i = qxx[i].next) {
        int v = qxx[i].zd;
        if (v != fa) {
            if (dfs1_dzt[v] == 0)   // 子节点必败
                dqzt++;
        }
    }
    // 再检查父方向（如果存在）
    if (u != 1 && up[u] == 0)       // up[u]==0 表示父方向是必败态
        dqzt++;

    dfs2_dzt[u] = dqzt;             // 记录当前节点的必败邻居总数（>0即必胜）

    // 为每个儿子计算它的 up 值
    for (int i = qxx_top[u]; i != 0; i = qxx[i].next) {
        int v = qxx[i].zd;
        if (v == fa) continue;
        int lsgx = dqzt;            // 复制当前节点的完整邻居统计
        if (dfs1_dzt[v] == 0)       // 如果儿子 v 原本是必败态，在父方向中要排除它的贡献
            lsgx--;
        up[v] = lsgx;               // up[v] 记录“u去掉v之后剩下的部分是否包含必败态”（非0即包含）
        dfs2(v, u);                 // 递归处理子节点
    }
    return 0;
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_qxx(u, v, 0);           // 添加无向边
        add_qxx(v, u, 0);
    }
    dfs(1, 0);                      // 第一遍DFS：计算子树胜负
    up[1] = 0;                      // 根节点没有父方向，视为父方向“必败”？实际上根没有父方向，此初始值不影响，因为dfs2中 u==1 不会检查 up[1]。
    dfs2(1, 0);                     // 第二遍DFS：换根计算答案
    for (int i = 1; i <= n; ++i)
        cout << (dfs2_dzt[i] ? "Alice" : "Bob") << '\n'; // 只要必败邻居数>0，先手必胜
}

第二种做法 SG函数、换根DP、mex动态维护

算法思路

这是一个有向无环图上的公平组合游戏，可以使用 SG 函数（Sprague-Grundy） 进行求解。

固定根时的 SG 值 对于一棵有根树，叶子节点的 SG 值为 ；非叶子节点的 SG 值为其所有子节点 SG 值集合的 mex（最小未出现的非负整数）。先手必胜当且仅当根节点的 SG 值不为 。

换根 DP 求出所有根的答案 若对每个点都重新做一次树形 DP，时间复杂度会达到 ，无法通过。因此采用换根 DP（二次扫描）：

1. 先以 为根做一次后序遍历，计算出每个节点仅考虑子树方向时的 SG 值，记为 。
2. 再做一次前序遍历（换根），将“父节点方向”也视为一棵子树，计算出它在去掉当前子树后的 SG 值，称为 ，并将 加入到子节点的子节点集合中，从而得到该子节点作为根时的完整 SG 值。

mex 的动态维护 在换根过程中，需要向一个节点的“子节点集合”中增加或删除某个 SG 值，并迅速求出新的 mex。可以为每个节点维护一个 map<int,int> 记录每种 SG 值出现的次数，同时维护一个 mex 变量。插入时若插入值等于当前 mex，则向后推进 mex 直到遇到未出现的值；删除时若该值计数降为 且其值小于当前 mex，则将 mex 更新为该值。

非递归实现 由于 可达 ，递归 DFS 可能导致栈溢出，标程使用显式栈模拟后序遍历和前序遍历。

复杂度分析

• 时间复杂度：。每条边被访问常数次，每次 map 操作 。
• 空间复杂度：，存储邻接表、每个节点的子节点 SG 计数等。

标程

#include <bits/stdc++.h>
using namespace std;
int n, syd;
int qxx_top[1100000];                     // 前向星头指针
struct dl {
    long long int v;       // 权值（本题未用到）
    long long int next;    // 下一条边的索引
    long long int zd;      // 目标节点
} qxx[1100000];

void add_qxx(int qd, int zd, int qz) {
    qxx[++syd].next = qxx_top[qd];
    qxx[syd].zd = zd;
    qxx[syd].v = qz;
    qxx_top[qd] = syd;
}

// cnt[u] : 节点 u 的子节点 SG 值计数器，用于动态求 mex
map<int, int> cnt[210000];
int mex_val[210000], down[210000], ans[210000];

// 向节点 u 的子节点集合插入 SG 值 x，并维护 mex_val[u]
void add(int u, int x) {
    cnt[u][x]++;
    if (x == mex_val[u]) {
        while (cnt[u].count(mex_val[u]) && cnt[u][mex_val[u]] > 0)
            ++mex_val[u];
    }
}

// 从节点 u 的子节点集合删除 SG 值 x，并维护 mex_val[u]
void remove(int u, int x) {
    auto it = cnt[u].find(x);
    if (it == cnt[u].end()) return;
    if (--(it->second) == 0) {
        cnt[u].erase(it);
        if (x < mex_val[u]) mex_val[u] = x;
    }
}

// 第一次 DFS：后序遍历，计算子树 SG 值 down[u]
void dfs1(int u, int fa) {
    for (int i = qxx_top[u]; i; i = qxx[i].next) {
        int v = qxx[i].zd;
        if (v == fa) continue;
        dfs1(v, u);
        add(u, down[v]);            // 收集子节点的 SG 值
    }
    down[u] = mex_val[u];           // 当前节点的 SG 值为子节点集合的 mex
}

// 第二次 DFS：换根，计算每个点作为根时的 SG 值 ans[u]
void dfs2(int u, int fa) {
    ans[u] = mex_val[u];            // 此时集合已包含所有邻居方向

    for (int i = qxx_top[u]; i; i = qxx[i].next) {
        int v = qxx[i].zd;
        if (v == fa) continue;

        // 暂时删除子节点 v 的贡献，得到“父方向”的 SG 值
        remove(u, down[v]);
        int up_sg = mex_val[u];
        add(u, down[v]);            // 恢复

        // 将 up_sg 作为 v 的一个“子节点”，递归处理 v
        add(v, up_sg);
        dfs2(v, u);
        // 不需撤回 v 中的 up_sg，因为后续不会再用 v 的状态
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        add_qxx(u, v,0);
        add_qxx(v, u,0);
    }

    dfs1(1, 0);                     // 以 1 为根求出子树 SG 值
    ans[1] = mex_val[1];            // 根 1 的答案
    dfs2(1, 0);                     // 换根求所有节点的答案

    // 输出结果：SG 值非 0 则先手必胜
    for (int i = 1; i <= n; ++i)
        cout << (ans[i] ? "Alice" : "Bob") << '\n';

    return 0;
}

L. 排行榜查询（Easy）

题意简述

模拟一个 ACM 竞赛的实时排行榜。共有 名选手， 道题目， 次操作。操作有两种：

1. 提交 1 sid pid result time：学号为 sid 的选手在时刻 time 提交了题目 pid，结果为 result。评测结果可能是 AC、WA、TLE、RE、CE、MLE、PE 之一。保证输入时间严格递增。
2. 查询 2 k：输出当前排行榜上第 条记录的信息（排名、学号、解题数、总罚时）。若 超过榜单人数，输出 -1。

排行榜计分规则：

• 每道题只有第一次 AC 才计解题数。
• 该题罚时 = 首次 AC 时间 + （首次 AC 前非 CE 的错误提交次数）。
• 总罚时 = 所有已 AC 题目的罚时之和。
• 未 AC 任何题的选手解题数为 0，总罚时为 0。
• 排名规则：解题数降序、总罚时升序、学号升序，相同者并列。
• 没有任何 AC 的选手排在最后（并列最后一名）。

限制条件：本题保证 ，。

算法思路

本题是 Easy 版本，由于 有限制，可以在每次查询时遍历排行榜的前 个元素来计算排名，而不需要严格 的查询。

实现细节：

1. 数据结构：

   • 使用 map<long long, ac_nowcoder_Ranking_data> 存储每个选手的详细数据（通过学号映射）。ac_nowcoder_Ranking_data 中包含选手的解题数、总罚时以及一个长度为 的数组记录每道题的状态（是否已 AC、错误次数、AC 时间）。
   • 使用 set<ac_nowcoder_Ranking_data*> 维护一个按排名规则排序的选手指针集合。每当选手数据更新时，先从 set 中移除旧记录，更新数据后再插回，以保证集合始终有序。

2. 处理提交：

   • 若选手首次出现，创建其数据并插入 set。
   • 评测结果为 CE 则直接忽略（不增加错误次数，也不影响罚时）。
   • 若结果为 AC 且该题之前未 AC，则更新解题数、累加罚时，并标记该题已 AC。
   • 若结果为其他错误（WA、TLE 等）且该题未 AC，则增加该题的错误次数（用于后续可能的罚时计算）。

3. 处理查询：

   • 遍历 set 的前 个元素，在此过程中计算每个选手的实际排名（考虑并列）。
   • 当遍历到第 个时，输出其信息。

复杂度分析

• 每次提交：（set 的删除与插入）。
• 每次查询：，由于 ，总体可接受。
• 空间复杂度：，主要用于存储每个选手的题目状态。

标程

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
// 题目状态
struct Title_status {
    int pid;
    int status = 0;             // 题目状态：0表示未完成，1表示已完成
    int Number_of_errors = 0;   // 错误提交次数（不含CE）
    long long int AC_time = 0;  // 完成时间
};

// 选手排名数据
struct ac_nowcoder_Ranking_data {
	long long int  userid = -1;
	mutable long long int  ranking = 0;         
	long long int  acceptedCount = 0;    
	long long int penalty_Time = 0;   
    Title_status Title_status_map[21]; // 每题状态，题目数 m <= 20
	// 排序规则：解题数降序、总罚时升序、学号升序
	 bool operator < (const ac_nowcoder_Ranking_data p1) const {
        if (acceptedCount == p1.acceptedCount) {
            if (penalty_Time == p1.penalty_Time) {
                        return userid < p1.userid;
            }
            return penalty_Time < p1.penalty_Time;
        }
        return acceptedCount > p1.acceptedCount;
    }
};
// 用于 set 内部比较指针所指对象的仿函数
struct ac_nowcoder_Ranking_data_cmp {
    bool operator()(const ac_nowcoder_Ranking_data* a, const ac_nowcoder_Ranking_data* b) const {
        return *a < *b;
    }
};
int main() {
  /*  for (int i = 31; i <= 35; i++) {
    freopen((to_string(i)+".in").c_str(), "r", stdin);
    freopen((to_string(i) + ".out").c_str(), "w", stdout);
    */
    int n, m, q;
    cin >> n >> m >> q;
    
    // 学号到选手数据的映射
    map<long long int, ac_nowcoder_Ranking_data> ac_nowcoder_Ranking_data_map;
    // 按排名规则有序维护所有选手的指针
    set<ac_nowcoder_Ranking_data *, ac_nowcoder_Ranking_data_cmp>  ac_nowcoder_Ranking_data_set;
    while (q--)
    {
        int cz = 0;
        long long int sid;
        int pid;
        string result;
        int time;
        int k;
        cin >> cz;
        if (cz == 1)
        {
            cin >> sid >> pid >> result >> time;
            // 如果该选手首次出现，则创建其数据并插入 set
            if (ac_nowcoder_Ranking_data_map.find(sid) ==
                ac_nowcoder_Ranking_data_map.end()) {
                ac_nowcoder_Ranking_data ac1;
                ac1.userid = sid;
                for (int i = 1; i <= m; i++) {
                    ac1.Title_status_map[i].pid = i;
                }
                ac_nowcoder_Ranking_data_map[sid] = ac1;
                ac_nowcoder_Ranking_data_set.insert(&ac_nowcoder_Ranking_data_map[sid]);
            }
            // CE 不计入错误次数，直接忽略
            if (result == "CE")continue;
            // 先移除旧记录，更新后再插回，保持 set 有序
            ac_nowcoder_Ranking_data& ac1 = ac_nowcoder_Ranking_data_map[sid];
            ac_nowcoder_Ranking_data_set.erase(&ac1);
            if (result == "AC")
            {
                // 仅当该题之前未 AC 时才更新
                if (ac1.Title_status_map[pid].status == 0)
                {
                    ac1.Title_status_map[pid].status = 1;
                    ac1.Title_status_map[pid].AC_time = time;
                    ac1.acceptedCount++;
                    // 罚时 = 首次 AC 时间 + 20 * 之前错误次数
                    ac1.penalty_Time +=
                        20 * ac1.Title_status_map[pid].Number_of_errors
                        + ac1.Title_status_map[pid].AC_time;
                }
            }
            else {
                // 非 AC 且非 CE 的错误提交，若该题未 AC 则增加错误次数
                if (ac1.Title_status_map[pid].status == 0)
                {
                    ac1.Title_status_map[pid].Number_of_errors++;
                }
            }
            ac_nowcoder_Ranking_data_set.insert(&ac1);
        }
        else if (cz == 2)
        {
            cin >> k;
            if (k > ac_nowcoder_Ranking_data_set.size())
            {
                cout << -1 << endl;
                continue;
            }
            int pm = 1; // 当前处理到第几条记录
            ac_nowcoder_Ranking_data csh;
            ac_nowcoder_Ranking_data *ac2= &csh; // 记录上一条记录，用于并列判断
            // 遍历 set 中的前 k 条记录，计算实时排名
            for (auto* ac1 : ac_nowcoder_Ranking_data_set)
            {
                // 与上一条解题数、罚时相同，则排名并列
                if (ac1->acceptedCount == ac2->acceptedCount && ac1->penalty_Time == ac2->penalty_Time)
                {
                    if (ac2->userid == -1)
                    {
                        ac1->ranking = 1; // 第一名
                    }
                    else
                    {
                        ac1->ranking = ac2->ranking; // 并列沿用上一排名
                    }
                }
                else {
                    ac1->ranking = pm; // 不同则排名为当前位次
                }
                ac2 = ac1;
                if (pm == k) {
                    break; // 已到达第 k 条
                }
                pm++;
            }
            cout << ac2->ranking << " " << ac2->userid << " " << ac2->acceptedCount << " " << ac2->penalty_Time << "\n";
        }
        else {
            exit(-10086); // 异常操作码，直接退出
        }
    }/*
    cin.clear();
}*/
}

M. 排行榜查询（Hard）

题意简述

与 K 题（Easy 版本）核心规则完全相同，但有以下区别：

1. 取消了 的限制，每次查询需要在 或更优时间内完成。
2. 题目数量 可以达到 ，因此不能再用固定大小的数组存储每个选手的题目状态。
3. 提交时间不再严格递增，而是保证同一时间同一选手只能提交一次，且后续提交时间不小于前面。

算法思路

Easy 版本中每次查询需遍历前 个元素，在 较大时无法通过。Hard 版本需要使用支持快速按排名查询的有序数据结构。

C++ 标准库的 std::set 不支持直接通过索引访问元素。因此标程使用了 GNU 扩展库 __gnu_pbds 中的 tree，它实现了类似平衡树的功能，并提供了 find_by_order(k)（获取排名为 的元素）和 order_of_key(key)（获取键值的排名）方法，时间复杂度均为 。

主要改进点：

1. 选手题目状态存储：由于 很大，改用 unordered_map<int, Title_status> 动态存储发生提交的题目状态。
2. 排行榜维护：使用 Tree（即 tree<ac_nowcoder_Ranking_data*, null_type, ...>）替代 set。更新选手数据时，同样采用“先删除、修改、再插入”的方式。
3. 排名计算：
   • 通过 find_by_order(k - 1) 直接获取榜单上第 个选手的指针。
   • 为了计算该选手的真实排名（考虑并列），构造一个虚拟的 vkey，将其解题数和罚时设为与该选手相同，学号设为 -1（极小），然后用 order_of_key(&vkey) 查找第一个大于等于该组合的排名，从而得到该并列段的第一名排名，即该选手的排名。

复杂度分析

• 每次提交：，涉及树结构的删除与插入。
• 每次查询：，通过 find_by_order 和 order_of_key 实现。
• 空间复杂度：，比 Easy 版本更节约空间。

标程

#include<bits/stdc++.h>
#include<unordered_map>
// 引入 GNU pbds 平衡树
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// 题目状态
struct Title_status {
    int pid;
    int status = 0;             // 题目状态：0表示未完成，1表示已完成
    int Number_of_errors = 0;   // 错误提交次数
    long long int AC_time = 0;  // 完成时间
};

// 选手排名数据
struct ac_nowcoder_Ranking_data {
    long long int  userid = -1;
    mutable long long int  ranking = 0;
    long long int  acceptedCount = 0;
    long long int penalty_Time = 0;
    unordered_map<int,Title_status> Title_status_map; // 动态存储题目状态
    // 排序规则
    bool operator < (const ac_nowcoder_Ranking_data &p1) const {
        if (acceptedCount == p1.acceptedCount) {
            if (penalty_Time == p1.penalty_Time) {
                return userid < p1.userid;
            }
            return penalty_Time < p1.penalty_Time;
        }
        return acceptedCount > p1.acceptedCount;
    }
};
// 比较指针
struct ac_nowcoder_Ranking_data_cmp {
    bool operator()(const ac_nowcoder_Ranking_data* a, const ac_nowcoder_Ranking_data* b) const {
        return *a < *b;
    }
};
// 使用 pbds 红黑树，支持 order statistics
using Tree = tree<ac_nowcoder_Ranking_data*, null_type, ac_nowcoder_Ranking_data_cmp, rb_tree_tag, tree_order_statistics_node_update>;int main() {
        int n, m, q;
        cin >> n >> m >> q;

        map<long long int, ac_nowcoder_Ranking_data> ac_nowcoder_Ranking_data_map;
        Tree ac_nowcoder_Ranking_data_tree;
        while (q--)
        {
            int cz = 0;
            long long int sid;
            int pid;
            string result;
            int time;
            int k;
            cin >> cz;
            if (cz == 1)
            {
                cin >> sid >> pid >> result >> time;
                // 首次出现的选手，创建数据并插入平衡树
                if (ac_nowcoder_Ranking_data_map.find(sid) ==
                    ac_nowcoder_Ranking_data_map.end()) {
                    ac_nowcoder_Ranking_data ac1;
                    ac1.userid = sid;
                    ac_nowcoder_Ranking_data_map[sid] = ac1;
                    ac_nowcoder_Ranking_data_tree.insert(&ac_nowcoder_Ranking_data_map[sid]);
                }
                if (result == "CE")continue;
                // 更新数据：先删后插
                ac_nowcoder_Ranking_data& ac1 = ac_nowcoder_Ranking_data_map[sid];
                ac_nowcoder_Ranking_data_tree.erase(&ac1);
                if (result == "AC")
                {
                    if (ac1.Title_status_map[pid].status == 0)
                    {
                        ac1.Title_status_map[pid].status = 1;
                        ac1.Title_status_map[pid].AC_time = time;
                        ac1.acceptedCount++;
                        ac1.penalty_Time +=
                                20 * ac1.Title_status_map[pid].Number_of_errors
                                + ac1.Title_status_map[pid].AC_time;
                    }
                }
                else {
                    if (ac1.Title_status_map[pid].status == 0)
                    {
                        ac1.Title_status_map[pid].Number_of_errors++;
                    }
                }
                ac_nowcoder_Ranking_data_tree.insert(&ac1);
            }
            else if (cz == 2)
            {
                cin >> k;
                if (k > ac_nowcoder_Ranking_data_tree.size()) {
                    cout << -1 << endl;
                    continue;
                }
                // 通过 find_by_order 获取第 k 个元素（0-indexed）
                auto it = ac_nowcoder_Ranking_data_tree.find_by_order(k - 1);
                ac_nowcoder_Ranking_data* ac2 = *it;
                // 构造虚拟键值，用于查找该并列段的第一名排名
                ac_nowcoder_Ranking_data vkey;
                vkey.acceptedCount = ac2->acceptedCount;
                vkey.penalty_Time = ac2->penalty_Time;
                vkey.userid = -1; // 极小值，定位到该并列段的第一人
                // order_of_key 返回小于该键值的元素个数，+1 得排名
                ac2->ranking = ac_nowcoder_Ranking_data_tree.order_of_key(&vkey) + 1;
                cout << ac2->ranking << " " << ac2->userid << " " << ac2->acceptedCount << " " << ac2->penalty_Time << "\n";
            }
            else {
                exit(-10086);
            }
        }
}

N. 五彩斑斓的最小生成树

题意简述

给定一张 个点、 条边的无向连通图，每条边有权值 和颜色 。

定义一个权值 对于颜色 是“好的”，当且仅当存在一棵最小生成树（MST），它包含了所有颜色为 且权值为 的边。

对于每种在输入中出现过的颜色，求其“好的”权值的个数（即积分）。

算法思路

本题需要利用最小生成树的环路性质和 Kruskal 算法的边处理顺序。

核心性质： 在 Kruskal 算法过程中，当处理到权值为 的边时，所有权值严格小于 的边已经被尝试加入，此时图的连通状态是确定的（无论这些边具体是如何选择的，连通块划分是唯一的）。权值为 的边能否被选入某棵 MST，仅取决于它是否连接了当前两个不同的连通块（即是否为“有用边”）。

对于本题，我们需要判断：对于某个颜色 和权值 ，是否所有该颜色该权值的边都是“有用边”。如果是，则意味着我们可以将它们全部选入 MST（因为它们彼此之间以及和已选边之间不会形成环）；否则，如果存在任何一条无用边（两端已连通），那么要想包含所有该颜色该权值的边，就必然会引入环，从而无法构成一棵树。

具体算法步骤：

1. 边的排序：将所有边按权值 为第一关键字、颜色 为第二关键字排序。

2. 初始化：并查集初始化，每个点自成一个连通块。使用一个可撤销并查集（带栈记录合并操作），以便在判断同权值、同颜色的边时能够临时加边并随后撤销。

3. 按权值分组处理：

   • 将所有边按权值分组。对于当前权值 ：
     • 首先，确保所有 的边已经不可撤销地加入并查集（因为这些边在 MST 中的选择是确定的，我们只需保留最终的连通状态）。
     • 然后，在权值为 的边中，进一步按颜色分组。
     • 对于每种颜色 的权值为 的边组：
       • 临时将这些边全部加入并查集（使用可撤销的 add_bcj）。
       • 如果全部加边成功（即没有出现两端点已经在同一集合的情况），则说明该权值对该颜色是“好的”，对应颜色的积分加 1。
       • 无论成功与否，之后都撤销这些临时加边操作（通过栈恢复并查集状态）。
   • 处理完当前权值 的所有临时判断后，将所有权值为 的边不可撤销地加入并查集（相当于 Kruskal 正常流程），然后进入下一个更大的权值。

4. 输出：按颜色编号升序输出每种颜色的积分。

为什么需要可撤销并查集？ 因为在判断同一权值下不同颜色的边组时，各组之间的判断是独立的。我们需要在干净的连通状态（只包含 的边）下分别测试每组边，而不能让前一组颜色的测试影响后一组。因此，每次测试后需要撤销临时合并。

复杂度分析

• 排序：
• 并查集操作：每条边最多被临时加入一次、撤销一次，以及最终不可撤销加入一次。使用按秩合并的并查集，单次操作近似 。
• 总体时间复杂度：，效率优秀。
• 空间复杂度：，主要用于存储边、并查集和撤销栈。

标程

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n, m;
// 并查集：bcj 父节点，bcj_size 子树大小（用于按秩合并）
int bcj[210000], bcj_size[210000];
// 颜色积分，key 为颜色编号，value 为“好的”权值个数
map<int, int> color_jifen;
// 可撤销的操作记录
struct chexiao {
    int fs, ft, fs_size, ft_size;
};
stack<chexiao>chexiao_stack;
// 边结构体
struct bian {
	int u, v, w, c;
}bian_arr[210000];
// 排序：按权值升序，权值相同按颜色升序
int cmp(bian& x, bian& y)
{
	if (x.w == y.w)
	{
		return x.c < y.c;
	}
	return x.w < y.w;
}
// 查找根
int fin(int k) {
	if (bcj[k] == k)return k;
	return fin(bcj[k]);
}
// 可撤销的加边，返回是否成功合并（不形成环）
bool add_bcj(int s, int t) {
	int fs = fin(s);
	int ft = fin(t);
	if (fs == ft)return false; // 已经在同一集合，加边会形成环
	// 记录操作以便撤销
	chexiao_stack.push({ fs,ft,bcj_size[fs],bcj_size[ft] });
	// 按秩合并
	if (bcj_size[fs] < bcj_size[ft]) {
		bcj[fs] = ft;
		bcj_size[ft] += bcj_size[fs];
	}
	else {
		bcj[ft] = fs;
		bcj_size[fs] += bcj_size[ft];
	}
	return true;
}
// 不可撤销的加边，用于 Kruskal 确定部分
bool add_bcj_buchexiao(int s, int t) {
	int fs = fin(s);
	int ft = fin(t);
	if (fs == ft)return false;
	if (bcj_size[fs] < bcj_size[ft]) {
		bcj[fs] = ft;
		bcj_size[ft] += bcj_size[fs];
	}
	else {
		bcj[ft] = fs;
		bcj_size[fs] += bcj_size[ft];
	}
	return true;
}
// 初始化并查集
int csh() {
	for (int i = 1; i <= n; i++)
	{
		bcj_size[i] = 1;
		bcj[i] = i;
	}
	return 0;
}
// 撤销一次合并操作
int bcj_chexiao(chexiao chexiao1) {
	bcj[chexiao1.fs] = chexiao1.fs;
	bcj[chexiao1.ft] = chexiao1.ft;
	bcj_size[chexiao1.fs] = chexiao1.fs_size;
	bcj_size[chexiao1.ft] = chexiao1.ft_size;
	return 0;
}
vector<int>qzfd_v, ysfd_v;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	csh(); // 并查集初始化
	for (int i = 1; i <= m; i++)
	{
		cin >> bian_arr[i].u >> bian_arr[i].v >> bian_arr[i].w >> bian_arr[i].c;
		color_jifen[bian_arr[i].c] = 0; // 初始化该颜色的积分为 0
	}
	// 对边排序
	sort(bian_arr + 1, bian_arr + 1 + m, cmp);
	int qzfd = 1, ysfd=1;
	// 预处理权值分组起点和颜色分组起点
	for (int i = 1; i <= m; i++)
	{
		if (bian_arr[i].w != bian_arr[i-1].w)
		{
			qzfd = i;
			qzfd_v.push_back(qzfd);
		}
		if (bian_arr[i].c != bian_arr[i-1].c|| bian_arr[i].w != bian_arr[i-1].w)
		{
			ysfd = i;
			ysfd_v.push_back(ysfd);
		}
	}
	qzfd_v.push_back(m + 1);
	ysfd_v.push_back(m + 1);
	// 按权值分组处理
	for (int i = 1,j=1; i < qzfd_v.size(); i++) {
		int qz_qd = qzfd_v[i - 1], qz_zd = qzfd_v[i]-1; // 当前权值组的范围
		int fdqzjl = bian_arr[qz_qd].w; // 当前权值
		// 处理该权值内的每种颜色分组
		for (; j < ysfd_v.size()&&bian_arr[ysfd_v[j] - 1].w==fdqzjl; j++)
		{
			int ysqd = ysfd_v[j-1], yszd = ysfd_v[j] - 1; // 当前颜色组的范围
			bool bj = true;
			// 尝试临时加入该颜色组的所有边
			for (int q = ysqd; q <= yszd; q++)
			{
				bj = add_bcj(bian_arr[q].u, bian_arr[q].v);
				if(bj==false) // 出现环，说明不能全部加入
				break;
			}
			if (bj == true)
			{
				// 全部成功，该权值对该颜色是“好的”
				color_jifen[bian_arr[yszd].c]++;
			}
			// 撤销所有临时加边，恢复状态
			while (chexiao_stack.size())
			{
				bcj_chexiao(chexiao_stack.top());
				chexiao_stack.pop();
			}
		}
		// 当前权值组处理完毕，将所有边不可撤销地加入并查集
		for (int q = qz_qd; q <= qz_zd; q++)
		{
		    add_bcj_buchexiao(bian_arr[q].u, bian_arr[q].v);
		}

	}
	// 按颜色编号升序输出积分
	for (auto& x : color_jifen)
	{
		cout << x.first << " " << x.second << "\n";
	}
	return 0;
}

O.星际航线规划

题意简述

有 个太空站，任意两站 之间存在利润 （可能为负，自环 禁止选择）。要求设计若干条循环航线，使得所有站点被恰好覆盖一次（每个站点恰有一条出边、一条入边），且不允许长度为 1 的自环。最大化所有被使用边 的利润之和。

，。保证存在合法方案。

算法思路

模型转化 每个点恰有一条出边和一条入边，等价于在完全有向图上找一个最大权圈覆盖。将每个点 拆成左部点 和右部点 ，若选择 ，则在二分图中匹配左 与右 ，权值为 。问题转化为在完全二分图 上求最大权完美匹配。

KM 算法（BFS 优化） 标准 KM 采用 DFS 找增广路时，若不加松弛优化，最坏时间复杂度为 ，无法通过 。本题标程使用 BFS 版 KM，在每次为左点增广时，用一个队列维护当前交错树，并利用 slack 数组记录每个右点的最小松弛量。当无法直接在相等子图中找到增广路时，一次性计算最小调整量 并修改顶标，同时将 slack 为 的新右点直接纳入交错树，避免重复搜索。整个算法时间复杂度严格 。

实现细节：

• 用邻接表（前向星）存储左点 到右点 的有效边（）。
• 顶标 lx[i], ly[j] 满足 ，相等子图包含所有 的边。
• slack[y] 记录当前交错树中左点 到未访问右点 的最小顶标超出量。
• 每次从队列中取出左点扩展，或当队列为空时根据 slack 进行全局顶标调整，将 slack 最小的右点加入交错树。
• 找到未匹配右点后，通过 huisu_x 和 xr_jy 回溯更新匹配。
• 若调整过程中出现无法继续的情况（MZDBJ=1），说明不存在完美匹配；由于题目保证有解，最终必然成功。

答案即为所有顶标之和 ，也等于所有匹配边的权值和。

复杂度分析

• 时间复杂度：。外层 次增广，每次增广至多进行 次顶标调整，每次调整时扫描 个右点。 时操作次数约 ，常数较小可在时限内完成。
• 空间复杂度：，用于存储边表（或邻接表）。

标程

#include <bits/stdc++.h>
#include <random>
using namespace std;
// 链式前向星存边
struct dl {
    long long int v;     // 边权
    int next;            // 下一条边的索引
    int zd;              // 终点（右部点编号）
}qxx[300000];
int n, m, MZDBJ = 0;     // MZDBJ 标记匹配是否失败
int qxx_top[300000], qxx_size, xr_jy[510], jyh[510];
long long int lx[510], ly[510];          // 左、右顶点顶标
long long int jyh_x[510], jyh_y[510];    // BFS 中访问标记
long long int scl[510];                  // slack 数组
int huisu_x[510];                        // 记录右部点在交错树中的前驱左点
int huisu_y[510];                        // 记录左部点在交错树中的前驱右点
// 加边函数
int add_qxx(int qd, int zd, int qz)
{
    qxx[++qxx_size].next = qxx_top[qd];
    qxx[qxx_size].zd = zd;
    qxx[qxx_size].v = qz;
    qxx_top[qd] = qxx_size;
    return 0;
}
// 回溯更新匹配
int huisu(int y) {
    int now_y = y;
    while (now_y != 0)
    {
        int last_x = huisu_x[now_y];      // 该右点的前驱左点
        xr_jy[now_y] = last_x;            // 更新匹配
        int last_y = huisu_y[last_x];     // 左点原来的匹配右点
        now_y = last_y;
    }
    return 0;
}
// 为左点 qd 寻找增广路（BFS 版本）
int find_bfs_km(int qd) {
    queue<int>dl;
    // 初始化 slack、访问标记和前驱记录
    for (int i = 1; i <= n; i++)
    {
        scl[i] = 999999999999;
        jyh_x[i] = 0;
        jyh_y[i] = 0;
        huisu_x[i] = 0;
        huisu_y[i] = 0;
    }
    jyh_x[qd] = 1;
    dl.push(qd);
    xr_jy[0] = qd; // 哨兵
    while (true)
    {
        if (dl.size())
        {
            int x = dl.front();
            dl.pop();
            // 遍历左点 x 的所有出边
            for (int i = qxx_top[x]; i != 0; i = qxx[i].next)
            {
                int y = qxx[i].zd;
                if (jyh_y[y])continue;
                long long int scljs = lx[x] + ly[y] - qxx[i].v;
                if (scljs == 0) // 边在相等子图中
                {
                    jyh_y[y] = true;
                    huisu_x[y] = x;
                    if (xr_jy[y] == -1) // 找到未匹配的右点
                    {
                        huisu(y);       // 回溯更新匹配
                        return 0;
                    }
                    else {
                        // 右点已匹配，将匹配它的左点入队，扩展交错树
                        int next_x = xr_jy[y];
                        jyh_x[next_x] = true;
                        huisu_y[next_x] = y;
                        dl.push(next_x);
                    }
                }
                else if (scljs > 0)
                {
                    // 更新该右点的最小 slack
                    if (scljs < scl[y])
                    {
                        scl[y] = scljs;
                        huisu_x[y] = x;
                    }
                }
            }
        }
        else {
            // 队列为空，需要调整顶标
            long long int scl_js = 999999999999;
            for (int y = 1; y <= n; y++)
            {
                if (!jyh_y[y])
                {
                    scl_js = min(scl_js, scl[y]);
                }
            }
            if (scl_js == 999999999999) {
                MZDBJ = 1; // 无法找到增广路，匹配失败
                break;
            }
            // 调整交错树中的顶标
            for (int i = 1; i <= n; i++)
            {
                if (jyh_x[i])
                    lx[i] -= scl_js;
                if (jyh_y[i])
                    ly[i] += scl_js;
            }
            // 更新未访问右点的 slack 值
            for (int y = 1; y <= n; y++)
            {
                if (!jyh_y[y])scl[y] -= scl_js;
            }
            // 将 slack 变为 0 的右点纳入交错树
            for (int y = 1; y <= n; y++)
            {
                if (!jyh_y[y] && scl[y] == 0) {
                    jyh_y[y] = 1;
                    jyh_y[y] = true;
                    if (xr_jy[y] == -1)
                    {
                        huisu(y);
                        return 0;
                    }
                    else {
                        int next_x = xr_jy[y];
                        jyh_x[next_x] = true;
                        huisu_y[next_x] = y;
                        dl.push(next_x);
                    }
                }
            }
            continue;
        }
    }

    return 0;
}
// KM 算法主流程
long long int km() {
    // 初始化顶标和匹配
    for (int i = 0; i <= n; i++)
    {
        lx[i] = 0;
        ly[i] = 0;
        xr_jy[i] = -1; // -1 表示未匹配

    }
    // 初始化左顶标为出边最大权值
    for (int i = 1; i <= n; i++)
    {
        for (int j = qxx_top[i]; j != 0; j = qxx[j].next)
        {
            lx[i] = max(lx[i], qxx[j].v);
        }
    }
    // 依次为每个左部点寻找增广路
    for (int x = 1; x <= n; x++)
    {
        find_bfs_km(x);
    }
    // 计算最大权和：顶标之和
    long long int ans = 0;
    for (int x = 1; x <= n; x++)
    {
        ans += lx[x];
        ans += ly[x];

    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    n = N;                   
    m = N * (N - 1);         // 完全二分图，但不含自环

    long long val;
    // 读入利润矩阵，建边（跳过 i == j 的自环）
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> val;
            if (i != j) {     
                add_qxx(i, j, val);
            }
        }
    }
    long long int qz = km();
    if (MZDBJ == 0)
    {
        cout << qz << "\n"; // 输出最大利润
    }
    else {
        cout << -1;          // 若匹配失败（按题目保证不会发生）
    }

    return 0;
}