poj 1026 Cipher(置換)
2045 ワード
http://poj.org/problem?id=1026
大まかな題意:数字nと1~nのシーケンスnum[]を与える.次に、いくつかの文字列を与え、文字列の下付きiとnum[i]を交換させ、K回交換した後に得られた文字列が何であるかを尋ねる.入力した文字列の長さはn以下であり、n未満であればスペースで補う.
例1
ではstr[4]=‘H’,str[5]='e',str[3]='L'.....
考え方:置換について
4 5 3 7 2 8 1 6 10 9 = (1 7 4)(2 5)(3)(6 8)(9 10)
1 2 3 4 5 6 7 8 9 10
従って、各ローテーションのループセグメントtのみが必要となり、元のi番目の文字についてk%t回ループするだけで目標位置が得られる.
大まかな題意:数字nと1~nのシーケンスnum[]を与える.次に、いくつかの文字列を与え、文字列の下付きiとnum[i]を交換させ、K回交換した後に得られた文字列が何であるかを尋ねる.入力した文字列の長さはn以下であり、n未満であればスペースで補う.
例1
4 5 3 7 2 8 1 6 10 9
H e L L o B o b ' ' ' ' ではstr[4]=‘H’,str[5]='e',str[3]='L'.....
考え方:置換について
4 5 3 7 2 8 1 6 10 9 = (1 7 4)(2 5)(3)(6 8)(9 10)
1 2 3 4 5 6 7 8 9 10
従って、各ローテーションのループセグメントtのみが必要となり、元のi番目の文字についてk%t回ループするだけで目標位置が得られる.
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 10;
int n,k;
char s[210];
int a[210];
int ans[210]; // i
char str[210];
void solve()
{
int i;
for(i = 1; i <= n; i++)
{
int cnt = 1;
int t = a[i];
while(t != i)
{
cnt++;
t = a[t];
}
ans[i] = cnt;
}
}
int main()
{
while(~scanf("%d",&n) && n)
{
int i;
for(i = 1; i <= n; i++)
scanf("%d",&a[i]);
solve();
while(~scanf("%d",&k) && k)
{
getchar();
gets(s+1);
int len = strlen(s+1);
for(i = len+1; i <= n; i++)
s[i] = ' ';
s[n+1] = '\0';
for(i = 1; i <= n; i++)
{
int t = i;
for(int j = 0; j < k%ans[i]; j++)
t = a[t];
str[t] = s[i];
}
str[n+1] = '\0';
cout << str+1 << endl;
}
cout << endl;
}
return 0;
}