J.Just Shuffle2020（模拟，置换） 牛客暑期多校训练营（第二场）

本文主要是介绍J.Just Shuffle2020（模拟，置换） 牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
按照$c[i]=b[a[i]]$进行置换，给你起点排列和终点排列，置换了k次，求置换排列

思路：
模拟枚举环上节点，然后置换数组就对应$p[b[i]]=b[i+1]$，相当于在环上后移一位。

是道原题，详解可以看：
https://blog.csdn.net/tomjobs/article/details/107332494

只不过那道题是 a[1],a[2],a[3]…变成1,2,3,4,5…
这道题是1,2,3,4…变成a[1],a[2],a[3]…

把置换数组方向调一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>using namespace std;
const int maxn = 2e5 + 7;int fa[maxn],cnt[maxn];
int a[maxn],b[maxn],p[maxn];int findset(int x) {if(fa[x] == x) return x;return fa[x] = findset(fa[x]);
}int gcd(int n,int m) {return m == 0 ? n : gcd(m,n % m);
}int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {fa[i] = i;cnt[i] = 0;}for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);int rx = findset(i),ry = findset(a[i]);if(rx != ry) fa[rx] = ry; //并查集维护环}for(int i = 1;i <= n;i++) {cnt[findset(i)]++;}for(int i = 1;i <= n;i++) { //本题m为质数，不会无解if(cnt[i] == 0) continue;if(gcd(m,cnt[i]) != 1) { //gcd不等于0的话没法获取环中节点break;}}for(int i = 1;i <= n;i++) {if(cnt[i] == 0) continue;int now = i;for(int j = 0;j < cnt[i];j++) {b[1ll * j * m % cnt[i]] = now; //获取环节点的真实位置now = a[now]; //枚举环中节点}b[cnt[i]] = b[0];for(int j = 1;j <= cnt[i];j++) {p[b[j]] = b[(j + 1) % cnt[i]]; //挪一位，刚好得到置换数组}}for(int i = 1;i <= n;i++) {printf("%d ",p[i]);}printf("\n");return 0;
}

这篇关于J.Just Shuffle2020（模拟，置换） 牛客暑期多校训练营（第二场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---