首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13121

花车巡游 题目描述 嘉年华的花车巡游正在展示精心编排的队列变换! 最初,所有 N辆花车排成一行,花车 i 位于第 i 位。变换程序由 K 个位置对 (a 1 ,…

花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换!

最初,所有 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

限制

时间限制:1000ms

内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int N, K;     cin &gt;&gt; N &gt;&gt; K;     vector&lt;pair&lt;int, int&gt;&gt; swaps(K);     unordered_set&lt;int&gt; S;     for (int i = 0; i &lt; K; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         swaps[i] = {a, b};         S.insert(a);         S.insert(b);     }     // 计算P = Q_K,即经过K步后的置换     vector&lt;int&gt; Q(N + 1), R(N + 1); // 1-based     for (int i = 1; i &lt;= 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&lt;int&gt; P = Q; // P是Q_K     // 对P进行循环分解     vector&lt;bool&gt; visited(N + 1, false);     vector&lt;vector&lt;int&gt;&gt; cycles;     for (int i = 1; i &lt;= N; ++i) {         if (!visited[i]) {             vector&lt;int&gt; cycle;             int cur = i;             while (!visited[cur]) {                 visited[cur] = true;                 cycle.push_back(cur);                 cur = P[cur];             }             cycles.push_back(cycle);         }     }     // 为每个循环计算答案     vector&lt;int&gt; ans(N + 1);     for (auto&amp; 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&lt;int&gt; current_set(cycle.begin(), cycle.end());         unordered_set&lt;int&gt; Y(current_set.begin(), current_set.end());         for (int t = 0; t &lt; 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 &amp;&amp; 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 &lt;= N; ++i) {         cout &lt;&lt; ans[i] &lt;&lt; '\n';     }     return 0; }</pre>
这道题暂未补解析。