【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（3）

比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18786128
开题 + 补题情况

很菜的一把，就开了三个签到题，1001 Lucas 定理花了好久才看出来，明明前两周 CF div3 才遇到过，1010 那么明显的曼哈顿距离拆绝对值想了八百年才想出来，明明寒假集训才学过的，真的感觉自己基础太不牢固了，很多很基本的东西用不好。

1005 - 修复公路

非常明显的并查集，答案就是连通块个数 \(-1\)。
点击查看代码

1. #include <bits/stdc++.h>
2. #define inf32 1e9
3. #define inf64 2e18
4. #define ls o << 1
5. #define rs o << 1 | 1
7. using i64 = long long;
8. using u64 = unsigned long long;
9. using u32 = unsigned int;
11. const int N = 3e5 + 9;
12. int a[N], fa[N];
14. int root(int x) {
15.     return (fa[x] == x) ? x : fa[x] = root(fa[x]);
16. }
18. void merge(int u, int v) {
19.     fa[root(u)] = root(fa[v]);
20. }
22. void solve()
23. {
24.     int n;std::cin >> n;
26.     for(int i = 1;i <= n;i ++) {
27.         std::cin >> a[i];
28.     }
30.     for(int i = 1;i <= n;i ++) {
31.         fa[i] = i;
32.     }
34.     for(int i = 1;i <= n;i ++) {
35.         if(i - a[i] > 0) {
36.             merge(i, i - a[i]);
37.         }
39.         if(i + a[i] <= n) {
40.             merge(i, i + a[i]);
41.         }
42.     }
44.     int sum = 0;
45.     for(int i = 1;i <= n;i ++) {
46.         sum += (root(i) == i);
47.     }
49.     std::cout << sum - 1 << '\n';
50. }

复制代码

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}}\)。
  

很好的一个题吧，算是把离散数学的函数应用得淋漓尽致了。
点击查看代码[code]#include #define inf32 1e9#define inf64 2e18#define ls o  n >> 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[a]);        } else if(op == 2) {            int a, b;std::cin >> a >> b;            h[a] = f;        } else if(op == 3) {            int a, b;std::cin >> a >> b;            a = f[a];            b = f;            std::swap(f[g[a]], f[g]);            std::swap(g[a], 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[j];        }        for(int j = 0;j < m;j ++) {            std::cin >> w[j];        }    }    std::vector pq(m);    for(int i = 0;i < n;i ++) {        for(int j = 0;j < m;j ++) {            pq[j].push({i, b[j]});        }    }    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[x] = true;    }    std::vector dp(n, {inf64, inf64});    auto power = [](i64 x) -> i64 {        return x * x;    };    dp[0][0] = 0;    dp[1][1] = power(c[0].first - c[1].first);    if(!vis[c[0].second])dp[1][0] = 0;    for(int i = 2;i < n;i ++) {        if(vis[c[i - 1].second]) {            dp[0] = std::min(dp[0], dp[i - 1][1]);            dp[1] = std::min(dp[1], dp[i - 1][0] + power(c[i - 1].first - c.first));        } else {            dp[0] = std::min(dp[0], std::min(dp[i - 1][0], dp[i - 1][1]));            dp[1] = std::min(dp[1], dp[i - 1][0] + power(c[i - 1].first - c.first));            dp[1] = std::min(dp[1], dp[i - 2][0] + power(c[i - 2].first - c.first));        }    }    i64 ans = inf64;    if(vis[c[n - 1].second])ans = std::min(ans, dp[n - 1][1]);    else ans = std::min(ans, std::min(dp[n - 1][0], dp[n - 1][1]));    std::cout