poj 1026 Cipher(置換)

2045 ワード

http://poj.org/problem?id=1026
大まかな題意:数字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;
}