A22620. 花车巡游
填空题
困难
知识点
题目描述
花车巡游
题目描述
嘉年华的花车巡游正在展示精心编排的队列变换！
最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中：
- 第 1 分钟：位置 a1 与 b1 的花车交换位置
- 第 2 分钟：位置 a2 与 b2 的花车交换位置
- ……
- 第 K 分钟：位置 aK 与 bK 的花车交换位置
- 第 K+1 分钟：重新从 (a1,b1) 开始交换（即位置 a1 与 b1 交换）
- 第 K+2 分钟：位置 a2 与 b2 交换
- 如此无限循环……
请计算每辆花车在整个表演过程中能到达的不同位置数量。
输入格式
第一行输入 N,K。
接下来 K 行每行包含 ai, bi（1≤ai<bi≤N）。
输出格式
输出 N行，第 i 行为花车 i能到达的不同位置数量。
输入样例
5 4
1 3
1 2
2 3
2 4输出样例
4
4
3
4
1样例解释
花车 1 可到达位置 {1,2,3,4}
花车 2 可到达位置 {1,2,3,4}
花车 3 可到达位置 {1,2,3}
花车 4 可到达位置 {1,2,3,4}
花车 5 始终在位置 5（未移动）
数据范围
1≤K≤2×105，2≤N≤105
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<pair<int, int>> swaps(K);
unordered_set<int> S;
for (int i = 0; i < K; ++i) {
int a, b;
cin >> a >> b;
swaps[i] = {a, b};
S.insert(a);
S.insert(b);
}
// 计算P = Q_K，即经过K步后的置换
vector<int> Q(N + 1), R(N + 1); // 1-based
for (int i = 1; i <= N; ++i) {
Q[i] = i;
R[i] = i;
}
for (auto [a, b] : swaps) {
int x1 = R[a];
int x2 = R[b];
swap(R[a], R[b]);
swap(Q[x1], Q[x2]);
}
vector<int> P = Q; // P是Q_K
// 对P进行循环分解
vector<bool> visited(N + 1, false);
vector<vector<int>> cycles;
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
vector<int> cycle;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
cycle.push_back(cur);
cur = P[cur];
}
cycles.push_back(cycle);
}
}
// 为每个循环计算答案
vector<int> ans(N + 1);
for (auto& cycle : cycles) {
// 检查循环是否与S有交集
bool has_intersection = false;
for (int x : cycle) {
if (S.count(x)) {
has_intersection = true;
break;
}
}
if (!has_intersection) {
// 答案是循环大小
int sz = cycle.size();
for (int x : cycle) {
ans[x] = sz;
}
continue;
}
// 模拟current_set的变化，计算Y的大小
unordered_set<int> current_set(cycle.begin(), cycle.end());
unordered_set<int> Y(current_set.begin(), current_set.end());
for (int t = 0; t < K - 1; ++t) { // t处理0到K-2，对应步骤1到K-1
auto [a, b] = swaps[t];
bool has_a = current_set.count(a);
bool has_b = current_set.count(b);
if (has_a && has_b) {
// 交换后集合不变
continue;
} else if (has_a) {
current_set.erase(a);
current_set.insert(b);
Y.insert(b);
} else if (has_b) {
current_set.erase(b);
current_set.insert(a);
Y.insert(a);
}
// 否则集合不变
}
int res = Y.size();
for (int x : cycle) {
ans[x] = res;
}
}
for (int i = 1; i <= N; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
上一题
下一题