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があって、さもなくば間違いで、、、、
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 ;
}