分数：\(50 + 0 + 19 + 0 = 69\)
- 别样的 subtask 大战。
- 别样的配分大战。
- 别样的爆零大战。
- 别样的 IceBee 大战。
T1
当时在场上苦思冥想了半天没有结果，是因为忽略了一条重要性质：序列是一个排列。可以证明：最小生成树中每条边的权值都小于 \(n\)，证明如下：
考虑构造一个特殊的生成树：按照节点编号顺序连接成一条链，即连接边 \((1, 2), (2, 3), \cdots , (n-1, n)\)。由于 \(p\) 是由 \(1\) 到 \(n\) 的排列，所以 \(\left|p_i - p_{i + 1}\right|\) 的取值范围是 \(1 \sim (n - 1)\)。
设 \(T\) 是最小生成树，\(T'\) 是我们构造的特殊生成树。根据最小生成树的定义， \(T\) 的权值和应当小于等于 \(T'\) 的权值和，即 \(w(T) \le w(T')\)。
假设最小生成树 \(T\) 中存在一条边 \(E\)，使得 \(w(e) \ge n\)。考虑将 \(E\) 从 \(T\) 中删除，这会使 \(T\) 分裂为两个连通分量 \(A\) 与 \(B\)。由于 \(T'\) 是连通的，在 \(T'\) 中必然存在一条路径连接 \(A\) 和 \(B\)。设这条路径为 \(P = \{e_1, e_2, \cdots, e_k\}\)，其中 \(e_1\) 在 \(A\) 中，\(e_k\) 在 \(B\) 中。由于 \(P\) 连接了 \(A\) 与 \(B\)，在 \(P\) 中必然存在至少一条边 \(e_j\)，它连接了 \(A\) 和 \(B\)。现在考虑用边 \(e_j\) 替换 \(e\)，得到新的生成树 \(T''\)，其权值和 \(w(T'') = w(T) - w(e) + w(e_j)\)。根据我们的构造，\(T'\) 中所有边的权值都小于 \(n\)，所以 \(w(e_j) < n\)。根据假设 \(w(e) \ge n\)，有 \(w(T'') = w(T) - w(e) + w(e_j) < w(T) - n + n = w(T)\)。这意味着我们找到了一个权值更小的生成树 \(T''\)，与 \(T\) 是最小生成树的假设矛盾。
得到这一结论后，考虑 Kruskal 的过程，我们只需要边权小于 \(n\) 的边，因此有 \(|p_i - p_j| \times |i - j| < n\)，要么 \(|p_i - p_j| < \sqrt{n}\)，要么 \(|i - j| < \sqrt{n}\)。因此每个点只需要考虑 \(O(\sqrt{n})\) 条边。
考虑到空间、时间有限，注意舍弃重复的边和不符合要求的边，并使用 unsigned short 等空间较小的数据类型。别样的卡空间大战。
#include <bits/stdc++.h>
const int N = 5e4+10;
typedef long long ll;
int n; unsigned short p[N], pos[N];struct Edge {unsigned short s, t;int len;
};
std::vector<Edge> edges;struct UF {int par[N], siz[N];UF(int n) {for (int i = 1; i <= n; i++) {par[i] = i, siz[i] = 1;}}unsigned short find(unsigned short u) {return u == par[u] ? u : (par[u] = find(par[u]));}void merge(unsigned short u, unsigned short v) {u = find(u), v = find(v);if (siz[u] > siz[v]) std::swap(u, v);par[u] = v, siz[v] += siz[u];}
};signed main() {freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n;for (int i = 1; i <= n; i++) {std::cin >> p[i];pos[p[i]] = i;}int sqr = ceil(sqrt(n));for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= std::min(n, i + sqr); j++) {int w = abs(p[i] - p[j]) * (j - i);if (w < n) {edges.push_back({(unsigned short)i, (unsigned short)j, w});}}}for (int i = 1; i <= n; i++) {for (int val = std::max(1, p[i] - sqr); val <= std::min(n, p[i] + sqr); val++) {if (val == p[i]) continue;int j = pos[val];if (j <= i) continue;if (abs(i - j) < sqr) continue;int w = abs(i - j) * abs(p[i] - p[j]);if (w < n) edges.push_back({(unsigned short)i, (unsigned short)j, w});}}std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) {return a.len < b.len;});UF uf(n);int cnt = 0; ll ans = 0;for (auto const &edge : edges) {if (cnt >= n - 1) break;if (uf.find(edge.s) == uf.find(edge.t)) continue;ans += ll(edge.len);cnt++;uf.merge(edge.s, edge.t);}std::cout << ans << '\n';return 0;
}
T2
这道题明明比 T1 简单得多，但还是不耽误我在上面爆零。可以发现，设 \(g = \gcd(m, n)\)，则当且仅当 \(i \mod g = j \mod g\) 时，卡牌 \(i\) 和 \(j\) 才会互相比较。因此，我们可以将所有数字按照下标模 \(g\) 分类，对于每一类，把相应的 \(A, B\) 排序。设对于每个 \(A_i\)，有 \(x_i\) 个比自己小的 \(B_i\)，以及 \(y_i\) 个和自己相等的 \(B_i\)，那么小 Y 赢的次数 \(X = \left(\sum_{i=1}^{g} x_i\right) g\)，平局的次数 \(Y = \left(\sum_{i=1}^{g} y_i\right) g\)，而小 Z 赢的次数 \(Z = mn - X - Y\)。
#include <bits/stdc++.h>
#define int long long
const int N = 1e5+10;
int a[N], b[N];
int n, m;
int yWin, zWin, same;
std::vector<int> aa[N], bb[N];signed main() {freopen("cardgame.in", "r", stdin);freopen("cardgame.out", "w", stdout);std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n >> m;for (int i = 1; i <= n; i++) {std::cin >> a[i];}for (int i = 1; i <= m; i++) {std::cin >> b[i];}int g = std::__gcd(n, m);for (int i = 1; i <= n; i++) {aa[i % g].push_back(a[i]);}for (int i = 1; i <= m; i++) {bb[i % g].push_back(b[i]);}for (int i = 0; i < g; i++) {std::sort(aa[i].begin(), aa[i].end());}for (int i = 0; i < g; i++) {std::sort(bb[i].begin(), bb[i].end());}int yWin = 0, same = 0;for (int i = 0; i < g; i++) {for (auto const &num : aa[i]) {int pos = std::lower_bound(bb[i].begin(), bb[i].end(), num) - bb[i].begin();yWin += pos;same += std::upper_bound(bb[i].begin(), bb[i].end(), num) - bb[i].begin() - pos;}}yWin *= g, same *= g;int zWin = m * n - yWin - same;std::cout << yWin << '\n' << zWin << '\n' << same << '\n';return 0;
}