当前位置: 代码迷 >> 综合 >> Cipher POJ - 1026(置换群)
  详细解决方案

Cipher POJ - 1026(置换群)

热度:45   发布时间:2024-01-29 13:19:09.0

题意:给出一个编码的顺序,每经过一次编码第i位上的字符回到第a[i]位上。然后给出一个k,和初始的串,问编码k次后的串是什么。

k可能会很大,不能暴力,所以要用置换群,找出轮换的环,假设环中有m个数,那么每编码m次,就代表这又回到了初始状态,可以用k%m,这样减少编码的次数。如果在记录轮换的位置,那么对于轮换中的第i个字符编码k次,就变成了轮换中的第(i+k)%m个字符。这样直接可以计算出最终的结果。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;
int a[210],vis[210];
int num;
vector<int> v[210];
char s[2010];
char ans[210];
void group(int n)
{memset(vis,0,sizeof vis);for(int i=0,j;i<n;i++){if(vis[a[i]]) continue;j=i;while(!vis[a[j]]){vis[a[j]]=1;v[num].push_back(j);j=a[j];}num++;}
}
int main()
{int n,k;while(scanf("%d",&n)&&n){		num=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);a[i]--;}for(int i=0;i<n;i++) v[i].clear();group(n);while(scanf("%d",&k)&&k){getchar();gets(s);if(strlen(s)<n){int l=strlen(s);for(int i=l;i<n;i++) s[i]=' ';}for(int i=0;i<num;i++){int len=v[i].size();for(int j=0;j<len;j++){ans[v[i][(j+k)%len]]=s[v[i][j]];}}ans[n]='\0';printf("%s\n",ans);}printf("\n");}return 0;
}