poj 1026 Cipher(置換)

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;
}