首页 > itarticle > uva 306 – cipher

uva 306 – cipher

admin 11月 12, 2020 0

Contents

Problem

題目網址
 中文網址

Solution

將在每個位置轉換的過程記錄下來，會形成一個循環，且回到一開始的位置。(因為其 key 為 1~n )
order[i][0] 為第 i 個字元一開始的位置，order[i][k+1] 為在第 k 次轉換後的位置， order[i][0] 拿來存循環的週期。
接著只要將原先的字元存進對應的結果即可:

m = k%order[i][0];//週期
ans[order[i][m + 1]] = str[i - 1];

注意 index 的處理。

Code


#include<cstring>
#define N 201

int ()
{
    int n;
    int key[N], order[N][N];
    char str[N], ans[N];
    while (scanf("%d", &n) && n)
    {
        int i, k;
        for (i = 1; i <= n; i++) 
            scanf("%d", &key[i]);

        for (i = 1; i <= n; i++)
        {
            int temp = i, j = 0;

            do
            {
                order[i][++j] = temp;
                temp = key[temp];
            } while (i != temp);

            order[i][0] = j;
        }

        while (scanf("%d", &k) && k)
        {
            getchar();
            gets(str);
            
            for (i = 1; i <= n; i++)
                ans[i] = ' ';
            int len = strlen(str), m;

            for (i = 1; i <= len; i++)
            {
                m = k%order[i][0];
                ans[order[i][m + 1]] = str[i - 1];
            }

            for (i = 1; i <= n; i++)
                putchar(ans[i]);
            putchar('n');
        }

        putchar('n');
    }

    return 0;
}