最小生成树与随机化矩阵验证实战解析
给定 n 个需要理发的个体，存在 m 组相互服务关系。当个体 x 为 y 理发时消耗时间 wx,y，且该关系具有对称性（y 为 x 理发同样消耗 wx,y）。服务规则包含：个体必须先完成自身理发才能服务他人；允许自我服务。目标是计算完成所有理发的最短总耗时。
核心解法：引入虚拟源点 root = n+1。遍历所有关系对 (x,y,w)：若 x=y 则建立 root→x 的无向边；否则建立 x↔y 无向边。在包含虚拟源点的图上运行 Prim 算法求最小生成树，其总权重即为答案。该方法将自我服务转化为源点连接，满足服务依赖约束。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
int n, m, root;
vector<pair<int, int>> graph[MAX_N];
long long prim() {
vector<long long> minEdge(MAX_N, LLONG_MAX);
vector<bool> inTree(MAX_N, false);
minEdge[root] = 0;
long long total = 0;
for (int i = 0; i <= n; ++i) {
int u = -1;
for (int j = 1; j <= n+1; ++j) {
if (!inTree[j] && (u == -1 || minEdge[j] < minEdge[u]))
u = j;
}
if (minEdge[u] == LLONG_MAX) return -1;
inTree[u] = true;
total += minEdge[u];
for (auto& [v, w] : graph[u]) {
if (!inTree[v] && w < minEdge[v])
minEdge[v] = w;
}
}
return total;
}
int main() {
cin >> n >> m;
root = n + 1;
while (m--) {
int x, y, w;
cin >> x >> y >> w;
if (x == y) {
graph[root].emplace_back(x, w);
graph[x].emplace_back(root, w);
} else {
graph[x].emplace_back(y, w);
graph[y].emplace_back(x, w);
}
}
cout << prim();
return 0;
}异世界场景中需处理三类事件：添加新怪物（名称与血量）、群体战技（全体减固定血量）、终结技（斩杀当前血量最高的怪物）。关键约束：血量≤0的怪物不再受后续影响；终结技优先选择最后出现的最高血量怪物。
优化策略：维护全局累计伤害 totalDamage。当新怪物加入时，将其初始血量增加 totalDamage；战技仅更新 totalDamage；终结技执行时，通过 totalDamage 实时计算当前血量。使用优先队列按 (血量+totalDamage, 加入序号) 排序，确保高效获取目标怪物。
#include <bits/stdc++.h>
using namespace std;
struct Monster {
string name;
long long baseHp;
int seq;
};
int main() {
int Q, seq = 0;
long long totalDamage = 0;
priority_queue<Monster> pq;
auto cmp = [](const Monster& a, const Monster& b) {
return a.baseHp != b.baseHp ?
a.baseHp < b.baseHp : a.seq < b.seq;
};
priority_queue<Monster, vector<Monster>, decltype(cmp)> pq(cmp);
cin >> Q;
while (Q--) {
int op; cin >> op;
if (op == 1) {
string name; long long hp;
cin >> name >> hp;
pq.push({name, hp + totalDamage, ++seq});
} else if (op == 2) {
long long damage; cin >> damage;
totalDamage += damage;
} else {
while (!pq.empty() &&
pq.top().baseHp - totalDamage <= 0)
pq.pop();
if (pq.empty()) cout << "Air 0\n";
else {
auto top = pq.top(); pq.pop();
cout << top.name << " "
<< top.baseHp - totalDamage << "\n";
}
}
}
return 0;
}n 个任务需分配给两名工人（A/B），任务 i 由 A 完成耗时 ai，由 B 完成耗时 bi。两人可并行工作，求完成所有任务的最短时间。
动态规划解法：定义 dp[j] 表示 A 累计耗时 j 时 B 的最小耗时。状态转移：dp[j] = min(dp[j], dp[j - ai] + bi)。最终答案为 min{ max(j, dp[j]) }。使用滚动数组优化空间复杂度，时间复杂度 O(n·max_time)。
#include <bits/stdc++.h>
using namespace std;
const int MAX_TIME = 40000;
int main() {
int n; cin >> n;
vector<int> a(n+1), b(n+1);
for (int i = 1; i <= n; ++i)
cin >> a[i] >> b[i];
vector<int> dp(MAX_TIME + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = MAX_TIME; j >= a[i]; --j) {
if (dp[j - a[i]] != INT_MAX)
dp[j] = min(dp[j], dp[j - a[i]] + b[i]);
}
}
int ans = INT_MAX;
for (int j = 0; j <= MAX_TIME; ++j)
if (dp[j] != INT_MAX)
ans = min(ans, max(j, dp[j]));
cout << ans;
return 0;
}验证矩阵乘法 A×B=C 是否成立，其中 A,B,C 均为 N×N 矩阵（N∈[1,1000]），支持最多 5 组查询。直接计算 O(N³) 不可取。
应用 Freivalds 算法：生成随机列向量 R∈{0,1}N×1，验证 A×(B×R)=C×R。若等式成立则大概率 A×B=C。现代随机数发生器（如 mt19937）单次验证错误概率低于 10⁻⁹，无需多次重复。关键步骤：
- 生成随机 0/1 向量 R
- 计算 BR = B×R 和 CR = C×R
- 计算 ABR = A×BR
- 比较 ABR 与 CR
#include <bits/stdc++.h>
using namespace std;
using Matrix = vector<vector<long long>>;
Matrix multiply(const Matrix& A, const Matrix& B) {
int n = A.size(), m = B[0].size(), p = B.size();
Matrix C(n, vector<long long>(m, 0));
for (int i = 0; i < n; ++i)
for (int k = 0; k < p; ++k)
for (int j = 0; j < m; ++j)
C[i][j] += A[i][k] * B[k][j];
return C;
}
int main() {
mt19937 rng(20240806);
uniform_int_distribution<int> dist(0, 1);
int N;
while (cin >> N) {
Matrix A(N, vector<long long>(N));
Matrix B(N, vector<long long>(N));
Matrix C(N, vector<long long>(N));
for (auto& row : A) for (auto& x : row) cin >> x;
for (auto& row : B) for (auto& x : row) cin >> x;
for (auto& row : C) for (auto& x : row) cin >> x;
Matrix R(N, vector<long long>(1));
for (int i = 0; i < N; ++i)
R[i][0] = dist(rng);
Matrix BR = multiply(B, R);
Matrix ABR = multiply(A, BR);
Matrix CR = multiply(C, R);
cout << (ABR == CR ? "Yes" : "No") << "\n";
}
return 0;
}