首页 > 代码库 > poj 1721 CARDS(置换群)
poj 1721 CARDS(置换群)
题目链接:poj 1721 CARDS
题意:
看了半天才看懂,就是一次置换为b[i]=a[a[i]],a[i]=b[i]。
现在已经知道了置换了多少次和当前的序列,问你最原来的序列为
题解:
将这个置换的循环次数ans找出来,再做ans-s次就行了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define F(i,a,b) for(int i=a;i<=b;++i) 5 using namespace std; 6 #define ___ freopen("c:\\code\\in.txt","r",stdin); 7 const int N=1010; 8 9 int n,s,a[N],init[N],b[N]; 10 11 int Is_same() 12 { 13 F(i,1,n)if(a[i]!=init[i])return 0; 14 return 1; 15 } 16 17 int main() 18 { 19 while(~scanf("%d%d",&n,&s)) 20 { 21 F(i,1,n)scanf("%d",init+i),a[i]=init[i]; 22 int cnt=0; 23 while(1) 24 { 25 cnt++; 26 F(i,1,n)b[i]=a[a[i]]; 27 F(i,1,n)a[i]=b[i]; 28 if(Is_same())break; 29 30 } 31 s=s%cnt,cnt-=s; 32 F(i,1,cnt) 33 { 34 F(j,1,n)b[j]=a[a[j]]; 35 F(j,1,n)a[j]=b[j]; 36 } 37 F(i,1,n)printf("%d\n",a[i]); 38 } 39 return 0; 40 }
poj 1721 CARDS(置换群)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。