poj 1026--cipher(置換群)

2350 ワード

タイトルリンク:クリックしてリンクを開く
1つの符号化の順序を与えて、毎回第i位の文字を符号化して第a[i]位に戻ります.次に、kと初期の列を与え、k回符号化された列が何であるかを尋ねる.
kは大きくて暴力ができない可能性があるので、置換群を使って、交代するリングを見つけて、リングの中にmの数があると仮定すると、符号化m回ごとに、これがまた初期状態に戻ったことを意味して、k%mを使って、このように符号化の回数を減らすことができます.ローテーションを記録する位置であれば、ローテーション中のi番目の文字に対してk回符号化され、ローテーション中の(i+k)%m番目の文字となる.これにより、最終的な結果を直接計算することができます.
注意、問題は難しくありませんが、入力が頭を悩ませ、、、、何度もwaを経て、テストは(getlineを除く):
gets(str) ;
int len = strlen(str) ;
for(i = len ; i <= n ; i++)
str[i] = ' ' ;
そして必ず後ろのforがあって、さもなくば間違いで、、、、
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std ;
char str[210] , s[210] , ch ;
int cnt ;
int a[210] , vis[210] ;
vector <int> vec[210] ;
int vec_num ;
void grop(int n) {
    int i , j ;
    vec_num = 0 ;
    memset(vis,0,sizeof(vis)) ;
    for(i = 1 ; i <= n ; i++) {
        if( vis[ a[i] ] ) continue ;
        j = i ;
        while( !vis[ a[j] ] ) {
            vis[ a[j] ] = 1 ;
            vec[ vec_num ].push_back( j ) ;
            j = a[j] ;
        }
        vec_num++ ;
    }
}
int main() {
    int n , m , k , i , j , l , num , mod , temp ;
    while( scanf("%d", &n) && n ) {
        for(i = 1 ; i <= n ; i++) {
            scanf("%d", &a[i]) ;
        }
        for(i = 0 ; i < n ; i++) vec[i].clear() ;
        grop(n) ;
        while( scanf("%d", &k) && k ) {
            cnt = 0 ;
            memset(s,0,sizeof(s)) ;
            memset(str,0,sizeof(str)) ;
            /*getchar() ;
            while( ch = getchar() ) {
                if( ch == '
' ) break ; str[++cnt] = ch ; }*/ gets(str) ; int len = strlen(str) ; for(i = len ; i <= n ; i++) str[i] = ' ' ; for(i = 0 ; i < vec_num ; i++) { num = vec[i].size() ; for(j = 0 ; j < num ; j++) { l = (j+k)%num ; s[ vec[i][l] ] = str[ vec[i][j] ] ; } } for(i = 1 ; i <= n ; i++) { printf("%c", s[i]) ; } printf("
") ; } printf("
") ; } return 0 ; }