CF2086C 题解
2025-08-02 19:07:28
发布于：浙江
19阅读
0回复
0点赞
题目名称：Disappearing Permutation
这道题是我第一次打 CF 比赛时做的，现在因为神秘力量，我重写了一遍。
当时我是用一个类似并查集的结构写的，时间复杂度 。现在我找到了一个更优解，时间复杂度为 。
题目翻译：
给定一个 的排列 和 次删除操作。每次删除操作会选择一个数 ，使 变为 。每次操作选定的 各不相同。
每次操作结束后，你需要回答一个问题：给你若干次修改操作，每次操作可以选择一个数 ，使 变为 。问你做少需要进行多少次操作才能使 重新变为一个排列？
创建一个新排列 ，使原来的 满足 。
我们可以发现，如果现在的 ，则修改 后还得修改 ；如果 ，那么修改完 后还得修改 ... 一直链式反应传递下去。传递到什么时候呢？显然是当传递到 时，，这样修改一下 就行了。
然后就很显然了，只要一直模拟就可以了。
但是这样是 的，我们还得想办法优化。
注意到前面的删除操作后要进行的修改操作在后面也会用到。所以我们可以在修改时顺便把当前的元素设置为 就行了。
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005], b[100005];
void solve(){
int n, ans = 0;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = i;
for(int i = 1; i <= n; i++){
int idx;
cin >> idx;
if(a[idx] == 0){
cout << ans << ' ';
continue;
}
int cur = b[idx];
a[idx] = 0;
ans++;
while(a[cur] != 0){
a[cur] = 0;
ans++;
cur = b[cur];
}
cout << ans << ' ';
}
cout << '\n';
for(int i = 1; i <= n; i++){
b[i] = 0;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
全部评论 7
附一个：
#include <bits/stdc++.h> using namespace std; const int N = 1e5+5; int t,n,ans,p[N],d[N]; bool vis[N]; void dfs(int x) { ans++; vis[x] = 1; if(!vis[p[x]]) dfs(p[x]); } int main() { cin >> t; while(t--) { ans = 0; cin >> n; for(int i = 1;i <= n;i++) { vis[i] = 0; cin >> p[i]; } for(int i = 1;i <= n;i++) { cin >> d[i]; if(!vis[d[i]]) { dfs(d[i]); } cout << ans << " "; } cout << '\n'; } return 0; }2025-08-02 来自 浙江
0
有帮助，赞一个