Cipher--POJ 1026
8315 ワード
1、タイトルタイプ:文字列、置換群.
2、解題の構想:(1)入力n個の符号化の順序によってそれぞれ1文字ごとに置換された周期を記録し、Cy[i]と記録する.(2)符号化回数kはCy[i]に対してそれぞれ余剰を求め,余剰はこの文字k回置換後の位置である.
3、注意事項:注意シーケンス全体に対して周期を求めてはいけない(この時の周期はn個の単一文字周期の最小公倍数である).そうでなければTLE.
4、実現方法:
2、解題の構想:(1)入力n個の符号化の順序によってそれぞれ1文字ごとに置換された周期を記録し、Cy[i]と記録する.(2)符号化回数kはCy[i]に対してそれぞれ余剰を求め,余剰はこの文字k回置換後の位置である.
3、注意事項:注意シーケンス全体に対して周期を求めてはいけない(この時の周期はn個の単一文字周期の最小公倍数である).そうでなければTLE.
4、実現方法:
#include
<
iostream
>
#include
<
string
>
using
namespace
std;
int
n;
int
pos[
210
],Cy[
210
];
void
Solve()
{
int
k,i,j,m,len;
char
str[
210
],ans[
210
];
while
(cin
>>
k
&&
k)
{
getchar();
gets(str);
len
=
strlen(str);
while
(len
<
n)
{
str[len
++
]
=
'
'
;
}
str[len]
=
'
\0
'
;
for
(i
=
0
;i
<
n;i
++
)
{
m
=
k
%
Cy[i];
j
=
i;
while
(m
--
)
j
=
pos[j]
-
1
;
ans[j]
=
str[i];
}
ans[n]
=
'
\0
'
;
cout
<<
ans
<<
endl;
}
}
int
main()
{
int
i,j;
while
(cin
>>
n
&&
n)
{
memset(Cy,
0
,
sizeof
(Cy));
for
(i
=
0
;i
<
n;i
++
)
cin
>>
pos[i];
for
(i
=
0
;i
<
n;i
++
)
{
j
=
i;
while
(pos[j]
!=
i
+
1
)
{
j
=
pos[j]
-
1
;
Cy[i]
++
;
}
Cy[i]
++
;
}
Solve();
cout
<<
endl;
}
return
0
;
}