【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（3）
比赛链接本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18786128
开题 + 补题情况
很菜的一把，就开了三个签到题，1001 Lucas 定理花了好久才看出来，明明前两周 CF div3 才遇到过，1010 那么明显的曼哈顿距离拆绝对值想了八百年才想出来，明明寒假集训才学过的，真的感觉自己基础太不牢固了，很多很基本的东西用不好。
1005 - 修复公路
非常明显的并查集，答案就是连通块个数 \(-1\)。
点击查看代码#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int N = 3e5 + 9;
int a, fa;
int root(int x) {
return (fa == x) ? x : fa = root(fa);
}
void merge(int u, int v) {
fa = root(fa);
}
void solve()
{
int n;std::cin >> n;
for(int i = 1;i <= n;i ++) {
std::cin >> a;
}
for(int i = 1;i <= n;i ++) {
fa = i;
}
for(int i = 1;i <= n;i ++) {
if(i - a > 0) {
merge(i, i - a);
}
if(i + a <= n) {
merge(i, i + a);
}
}
int sum = 0;
for(int i = 1;i <= n;i ++) {
sum += (root(i) == i);
}
std::cout << sum - 1 << '\n';
}1009 - 部落冲突（补题）
听说是前几场 ABC 的原题，有点后悔没打 ABC 了。
对于这个题，若没有第三个操作，则很明显就是一个并查集，用并查集来维护一下各个部落的归属情况，查询的时候查一下野人对应的部落所在的连通块即可。
但是操作 3 让这个变得难了一点，操作 3 我们需要互换两个部落，若暴力求解显然会 TLE。
我们看一下上面没有操作 3 的思路，对于合并操作，我们并没有修改野人对应的部落，而是修改部落相互之间的归属关系，查询时直接查询即可。
那么类似的，我们也想一下能不能维护。
我们把这个问题转化一下，初始的时候有 \(n\) 个部落，放在 \(n\) 个位置中，那么对于操作 \(3\) 的交换，就可以翻译为“交换位置 \(a\) 和位置 \(b\) 的部落”，而对于最后的查询，我们也是查询一个野人所在部落的当前位置，这样就无需修改野人的位置信息了，而对于题目中的输入，我们输入的都是位置，而不是部落，因此此做法成立！
我们用 \(f_i\) 表示位置 \(i\) 的部落，用 \(g_i\) 表示部落 \(i\) 所在的位置，用 \(h_i\) 表示野人 \(i\) 所在的部落，那么就有以下解决方法：
[*]操作 \(1\)： 获取一下位置 \(a\) 和位置 \(b\) 当前的部落 \(f_a\) 和 \(f_b\)，使用并查集进行合并。
[*]操作 \(2\)： 获取一下位置 \(b\) 对应的部落 \(f_b\)，修改一下野人 \(a\) 当前的部落。
[*]操作 \(3\)： 获取一下位置 \(a\) 和位置 \(b\) 当前的部落 \(f_a\) 和 \(f_b\)，同时交换 \(f_a,f_b\) 和 \(g_{f_a},g_{f_b}\)，表示交换位置 \(a\) 和 位置 \(b\) 对应的部落，同时交换部落 \(f_a\) 和部落 \(f_b\) 对应的位置。
[*]操作 \(4\)： 由于我们对于野人存储的是部落信息 \(root_{h_a}\)，但答案需要的是位置信息，因此应该输出 \(g_{root_{h_a}}\)。
很好的一个题吧，算是把离散数学的函数应用得淋漓尽致了。
点击查看代码#include #define inf32 1e9#define inf64 2e18#define ls on >> q; std::vector f(n + 1), g(n + 1), h(n + 1); std::iota(f.begin() + 1, f.begin() + n + 1, 1); std::iota(g.begin() + 1, g.begin() + n + 1, 1); std::iota(h.begin() + 1, h.begin() + n + 1, 1); BCJ bcj(n); while(q --) { int op;std::cin >> op; if(op == 1) { int a, b;std::cin >> a >> b; bcj.merge(f, f); } else if(op == 2) { int a, b;std::cin >> a >> b; h = f; } else if(op == 3) { int a, b;std::cin >> a >> b; a = f; b = f; std::swap(f], f]); std::swap(g, g); } else { int a;std::cin >> a; std::cout > m; std::vector a(m); std::vector b(n, std::vector(m)), w(n, std::vector(m)); for(auto &i : a) { std::cin >> i; } for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { std::cin >> b; } for(int j = 0;j < m;j ++) { std::cin >> w; } } std::vector pq(m); for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { pq.push({i, b}); } } int sum = n; std::vector cnt(n); while(true) { int pre = sum; std::vector tmp; for(int i = 0;i < m;i ++) { while(pq.size() && pq.top().val > i; } for(int i = 0;i < n;i ++) { c = {a, i}; } sort(c.begin(), c.end()); for(int i = 1;i > x; x --; vis = true; } std::vector dp(n, {inf64, inf64}); auto power = [](i64 x) -> i64 { return x * x; }; dp = 0; dp = power(c.first - c.first); if(!vis.second])dp = 0; for(int i = 2;i < n;i ++) { if(vis.second]) { dp = std::min(dp, dp); dp = std::min(dp, dp + power(c.first - c.first)); } else { dp = std::min(dp, std::min(dp, dp)); dp = std::min(dp, dp + power(c.first - c.first)); dp = std::min(dp, dp + power(c.first - c.first)); } } i64 ans = inf64; if(vis.second])ans = std::min(ans, dp); else ans = std::min(ans, std::min(dp, dp)); std::cout
页:
[1]