Problem source: http://acm.zju.edu.cn/show_problem.php?pid=1009.
这是一道排列变换的题目. 题目本身不容易理解. 有耐心的就仔细看看题目吧, 如果不把题目理解清楚, 一定会在解的过程中出问题. 我一开始认为题目中的sample有错, 结果我错了…
有人认为题目很easy. 当然, 如果只要求解出来的确不难. 有几点很有意思, 个人也觉得不太合理, 但事实如此, 虽然下面的方法很依赖测试数据, 但工程中我们要解决的问题往往不一定需要很通用, 所以也不一定是完全不可取的方法. 注意main() 函数中的string分配, 完全是硬试出来的, 用不断的submit以及返回的segmentation fault做为判断依据得到的数据.
1. 大多数人的做法是正向模拟排列复合最后的结果. 这样做有一个不好地方, 就是在最后得到复合的结果后, 还需要反向查找. 我用了另一种思路, 从一开始就维护一张反向表, 最后只需要直接用密文的字母做为index,即可得到结果.
2. 许多人把一次输入做为基本单位, 中间有很多重复计算. 可以这样理解, 每一次按扭时, 这时的状态对于所有的第i个字母来说都是一样的. 我的做法是把所有的密文全部输入, 然后维护一张反查表, 这样的好处是测试数据如果一个case的密文有多条, 且都不一样时, 效率是很高的. 当然如果数据量太大时现在的做法也是不合适的, 这是一种用空间换时间的方法.
3. 优化求余操作. 求余会被转化为除法操做, 在算法中的核心函数rotate大量使用求余操作. 考虑用LookUpTable做加速. 时间从0.04s降到了0.02s. 这个哈稀表很简单, 但却有大用处. 另外就是要处理LookUpTable的大小, 越小越好…
4. 关于permutation的一些推导, 有兴趣的自己研究一下吧… 可以用inverse permutation, permutation cycles和multiply permutation做关键字去google一把… 如果想深入看, 需要读Knuth的TACOP, I, section 1.3.3 和 III section 5.1. 可以帮你在无尽的绕圈圈中找到一些方向感… 
_________________________________________________________
Performance status
| Run time | Run memory | Language |
| 00:00.02 sec | 420K | C++ |
___________________________________________________________
#include <stdio.h>
#include <memory.h>
int LookUpTable[26*3];
void inverse( int size, int src[] )
{
static int tmp[26],i;
for ( i = 0; i < size ; i++ ) {
tmp[src[i]] = i;
}
memcpy(src,tmp,sizeof(int)*size);
}
void multiply( int size, int src0[], int src1[], int dst[] )
{
int i;
for ( i = 0 ; i < size; i++ ) {
dst[i] = src1[src0[i]];
}
}
void rotate( int size ,int rotor[], int offset[], int * start)
{
int idx,i;
// Rotate r1^{-1}
start[0] = (start[0] + size – 1) % size;
idx = start[0];
for ( i = 0 ; i < size ; i++ ) {
rotor[i] = LookUpTable[i + offset[idx] + size ];
idx = LookUpTable[idx + 1];
}
}
// Denote the rotor0, rotor1, rotor2 as r0, r1, r2.
int main()
{
int size,i,j,cnt;
int enigmaCnt = 1;
int rotor[5][26];
char string[26][1001];
int flags[26];
int listLen;
int start,cur;
int curChar;
int starter[3];
int offset[3][26];
bool bChange;
int counter0,counter1;
int sizeSquare;
int *pTable;
do {
scanf( "%d\n", &size );
if ( !size ) {
break;
}
if ( enigmaCnt != 1 ) {
printf("\n");
}
pTable = LookUpTable;
for ( j = 0 ; j< 3 ; j++ ) {
gets(string[0]);
for ( i = 0 ; i < size ; i++ ){
rotor[j][i] = string[0][i]-’A';
offset[j][rotor[j][i]] = i – rotor[j][i];
// Init lookup table here.
*pTable++ = i;
}
// Let l = r0*r1*r2
// l^{-1} = r2^{-1}*r1^{-1}*r0^{-1}
inverse(size,rotor[j]);
}
// r3 = r2^{-1}*r1^{-1}
multiply(size,rotor[2],rotor[1],rotor[3]);
scanf( "%d\n", &cnt );
printf( "Enigma %d:\n",enigmaCnt++);
for ( i = 0; i < cnt – 1; i++ ) {
// Init input and linked list.
gets(string[i]);
flags[i] = i + 1;
}
gets(string[i]);
flags[i] = -1;
listLen = cnt;
// Init stage.
start = curChar = cur = 0;
bChange = false;
starter[0] = starter[1] = starter[2] = 0;
sizeSquare = size*size;
counter0 = counter1 = 0;
do{
int last = cur;
int thisLen = listLen;
cur = start;
// Compute l^{-1} for current stage
// r2 changed.
if ( 0 == counter1 && curChar ) {
bChange = true;
rotate(size,rotor[2],offset[2],starter + 2);
}
// r1 changed.
if ( 0 == counter0 && curChar ) {
bChange = true;
rotate(size,rotor[1],offset[1],starter + 1);
}
if ( bChange ) {
bChange = false;
multiply(size,rotor[2],rotor[1],rotor[3]);
}
multiply(size,rotor[3],rotor[0],rotor[4]);
for ( i = 0 ; i < thisLen; i ++ ) {
// When current string is processed, delete it from list.
if ( ” == string[cur][curChar] ) {
if ( thisLen == 1 ) {
listLen –;
} else{
if ( cur == start ) {
start = flags[cur];
} else if ( -1 == flags[cur] ) {
flags[last] = -1;
} else {
flags[last] = flags[cur];
}
listLen–;
}
} else {
string[cur][curChar] =
‘a’ + rotor[4][string[cur][curChar]-’A'];
last = cur;
}
cur = flags[cur];
}
// r0 always change.
rotate(size,rotor[0],offset[0],starter);
curChar++;
if( counter0 == size – 1 ){
counter0 = 0;
} else{
counter0++;
}
if( counter1 == sizeSquare – 1 ){
counter1 = 0;
} else{
counter1++;
}
}while( listLen );
for ( i = 0; i < cnt; i++ ) {
printf("%s\n",string[i]);
}
} while (1);
return 0;
}
