//188K 110MS C++
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
char str1[205];
char str2[205];
int key[205];
int cycleLength[205];
// void replace(char * str, int keyLength, int strLength) {
// memset(str2, 0, sizeof(str2));
// for (int i = 0; i < keyLength; i++) {
// int pos = key[i] - 1;
// if (str[i] == 0 || str[i] == '\n') {
// str2[pos] = ' ';
// } else {
// str2[pos] = str[i];
// }
// }
// memcpy(str1, str2, sizeof(str1));
// }
// void solve(char * str, int keyLength, int repeatTime) {
// // printf("%s\n", str);
// int strLength = strlen(str);
// for (int i = 1; i <= repeatTime; i++) {
// replace(str, keyLength, strLength);
// }
// str[keyLength] = 0;
// printf("%s\n", str);
// }
void getCycleLength(int * key, int keyLength) {
for (int i = 1; i <= keyLength; i++) {
int curCycleLength = 0;
int nextPos = key[i-1];
while(nextPos != i) {
curCycleLength++;
nextPos = key[nextPos-1];
}
// printf("%d %d\n", i, curCycleLength + 1);
cycleLength[i-1] = curCycleLength + 1;
}
}
// int move(int curPos) {
// return key[curPos-1];
// }
int moveWithRepeatTime(int beginPos, int repeatTime) {
if (repeatTime ==0) {
return beginPos;
}
int curPos = beginPos;
for (int i = 1; i <= repeatTime; i++) {
curPos = key[curPos-1];
}
return curPos;
}
int main() {
while(1) {
int keyLength;
memset(key, 0, sizeof(key));
scanf("%d", &keyLength);
if (keyLength == 0) {
return 0;
}
for (int i = 0; i < keyLength; i++) {
scanf("%d", &key[i]);
}
getCycleLength(key, keyLength);
int repeatTime;
while (1) {
scanf("%d", &repeatTime);
if (repeatTime == 0) {
break;
}
char c;
scanf("%c", &c);
memset(str1, 0, sizeof(str1));
// scanf("%9[^\n]", str1);
for(int i = 0; i < keyLength; i++){
str1[i] = ' ';
}
for(int i = 0; i < keyLength; i++){
scanf("%c", &c);
if(c == '\n'){
break;
}
str1[i] = c;
}
int length = strlen(str1);
memset(str2, ' ', sizeof(str2));
for (int i = 0; i < keyLength; i++) {
int curRepeatTime = repeatTime%cycleLength[i];
int newPos = moveWithRepeatTime(i+1, curRepeatTime);
// printf("%d -> %d\n", i, newPos - 1);
if (str1[i] == 0 || str1[i] == '\n') {
str2[newPos-1] = ' ';
} else {
str2[newPos-1] = str1[i];
}
}
str2[keyLength]= 0;
printf("%s\n", str2);
}
printf("\n");
}
}
原理上很简单,就是单纯的模拟,从一个位置移动到另一个位置,
但是题目会要求移动非常多的次数(上万),因此如果搞朴素的模拟,必然TLE。
因此,就要分析一下位移的规律了,对于长度为L的位移数组,最多经过L次,就可以移回原位,这样就算移动N次(N非常大),只需N%移动循环的次数就可以得到一个相对很小的移动次数,就不会TLE了。对每个位置都求解得到其位移循环的最大次数C,然后对每个位置模拟移动N%C次即可,
比如例子中的位移数组:
10 4 5 3 7 2 8 1 6 10 9
对于位置1的数: 1 ->4 -> 7 -> 1 循环最大次数是3
对于位置2的数:2->5->2 循环最大次数是2
对于位置3的数: 3->3, 1
............
该题还考空格输入, 用 scanf("%9[^\n]", str1);一直TLE,怀疑是某次输入被阻塞了,后来不得已一个一个字母的读取了。
最后还要注意,每个block要输出一个空行, 因为这个PE了几次....
标签:1026,int,str2,str1,keyLength,char,poj,str From: https://blog.51cto.com/u_9420214/6332979