poj1026 Cipher ——置换群

August 25, 2013

其实这道题目和poj2369这道题目一样。

都是基础的置换群题目。把那道题目理解了，这道题就没问题了。

不过我的方法貌似比较挫，或者处理方法效率不高，比较慢……

就是对每个数字求出循环节，用rec[]保存，然后用k%rec[]得到余数，

再模拟这个余数次就得到了目标位置。

/*
ID: zypz4571
LANG: C++
TASK: decode.cpp
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
char str[222];
int rec[222], a[222], b[222], c[222];
bool flag[222];
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    int n, k;
    while (~scanf("%d", &n)) {
        if (!n) break;
        for (int i = 0; i < n; ++i) scanf("%d", a + i + 1);
        memset(rec, 0, sizeof(rec));
        memset(flag, false, sizeof(flag));
        vector<int> tmp;
        for (int i = 1; i <= n; ++i) {
                tmp.clear();
                if (!flag[i]) {
                    int sum = 0, pos = i;
                    while (!flag[a[pos]]) {
                        sum++; flag[a[pos]] = true; tmp.push_back(a[pos]); pos = a[pos];
                    }
                    for (size_t j = 0; j < tmp.size(); ++j) rec[tmp[j]] = sum;
                }
        }
        while (~scanf("%d", &k)) {
            if (!k) break;
            getchar();
            gets(str);
            int len = strlen(str);
            if (len < n) {
                for (int i = strlen(str); i < n; ++i) str[i]=' ';
                str[n]='\0';
            }
            for (int i = 1; i <= n; ++i) {
                int cnt = k % rec[i], sum = 0, pos = i;
                memset(flag, false, sizeof(flag));
                while (!flag[a[pos]]) {
                    if (sum >= cnt) break;
                    sum++; flag[a[pos]] = true; pos = a[pos];
                }
                b[i] = pos;
            }
            for (int i = 1; i <= n; ++i) c[b[i]] = str[i-1];
            for (int i = 1; i <= n; ++i) printf("%c", c[i]);
            printf("\n");
        }
        printf("\n");
    }
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

每个block后面加一个空行！输出格式搞清楚

嗨，中村。

Read more