星期天这天一口气AC了五道题，除了1009外基本都可算是简单题。
（1）1009 Enigma：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1009
题目是讲解二战期间德国使用的密码机Enigma。明文通过按键，通过转盘（rotor）转换为密文。如下图所示为有1个转盘，一共有6个字母的情况，每击键一次，转盘转动一格。如果含有多个转盘，则以类似数字进制方式转动，即第一个盘转动一圈后，第二个盘转动一格，以此类推。题目要求解密含有三个转盘的密文，第一行输入m，表示键盘一共有m个字母（'A'，'B'，'C'，...，'A'+m-1)，然后输入三行表示每个转盘的初始字符映射状态（例如下图中的rotor的初始状态是BADFEC）。然后输入n行密文，要求输出每个密文的明文。
分析上面的图，可得转盘的输入x和输出x'之间的关系是偏移关系，即x'=x+dx;因此我们把映射关系中的偏移量dx用一个数组表示：
int rotor[m]; 这个数组中的负数也可以通过加上m矫正为正数。
例如上图中的映射关系为BADFEC，用偏移量数组表示为{1, -1, 1, 2, 0, 3},
当rotor转动一格时，相当于该数组循环向右移动一格，变为{3, 1, -1, 1, 2, 0};
因此我们完全物理模拟rotor的转动过程，给出第一个版本的AC的代码如下：
1009_Version_01
/*旋转圆盘的解密问题*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*6个转盘，前3个存储的是即时状态，后3个存储的是初始状态！！*/
char rotors[6][27];
/*每个转盘的当前步进值*/
int steps[3];
/*顺时针旋转某个转盘一个步进，
index表示转盘号，m表示每个转盘一共多少个字母*/
void Rotate(char *rotor, int m)
{
int i;
char temp;
/*先转换为偏移值，有正有负*/
for(i=0; i<m; i++)
rotor[i]=rotor[i] - ('A' + i);
/*旋转*/
temp=rotor[m-1];
for(i=m-1;i>0;i--)
rotor[i]=rotor[i-1];
rotor[0]=temp;
/*复原为字符串，同时矫正负数值*/
for(i=0; i<m; i++)
rotor[i]='A' + ( (i + rotor[i] + m) % m);
}
/*整体转动一次！m为每个转盘的字符数*/
void RotateRotors(int m)
{
steps[0]++;
Rotate(rotors[0],m);
if(steps[0]==m)
{
steps[0]=0;
steps[1]++;
Rotate(rotors[1],m);
}
if(steps[1]==m)
{
steps[1]=0;
steps[2]++;
Rotate(rotors[2],m);
}
}
/*根据输出的密文，得出原文，都是大写字母*/
char GetPlainChar(const char* rotor, char c)
{
char *p=strchr(rotor, c);
return 'A'+(p-rotor);
}
/*复原到初始状态*/
void ResetRotors()
{
steps[0]=steps[1]=steps[2]=0;
/*设置圆盘的初始状态*/
strcpy(rotors[0], rotors[3]);
strcpy(rotors[1], rotors[4]);
strcpy(rotors[2], rotors[5]);
}
int main()
{
int m, n, count=1, i;
char line[1024], *s;
while(1)
{
/*读入密码数*/
gets(line);
m=atoi(line);
if(m==0)
break;
/*每个test case之间插入一个空行*/
if(count!=1) printf("\n");
printf("Enigma %d:\n", count++);
/*读入三个rotor*/
gets(rotors[3]);
gets(rotors[4]);
gets(rotors[5]);
/*读取输入的密文数*/
gets(line);
n=atoi(line);/*读取换行符*/
/*解密*/
for(i=0;i<n;i++)
{
/*设置圆盘的初始状态*/
ResetRotors();
gets(line);
s=line;
while(*s)
{
*s=GetPlainChar(rotors[2],*s);
*s=GetPlainChar(rotors[1],*s);
*s=GetPlainChar(rotors[0],*s);
*s=*s - 'A' + 'a';/*化为小写字母*/
RotateRotors(m);
s++;
}
printf("%s\n", line);
}
}
return 0;
}
上面的代码用时190ms，而该题的解排行榜的用时为20ms，30ms，40ms。可见运行时间还可以改进，我想运行时间的改进可能是主要针对常数因子的改进。因此我们考虑上面的代码中的导致效率低下的地点所在。大致可以确定是每敲打一次按键，对rotor转动时需要对数组进行如下操作：字符串->偏移值数组->数组元素转动->字符串，虽然字符串长度不大，但它的耗时属于O(n)，因此我们可以把这个过程改为O(1)。即我们不实际转动数组元素，而是利用一个标记当前的totor位置的“指针”，这样rotor转动时，我们仅仅改变“指针”的值，而不需要移动数组。
为了快速求取输入，我们把上面的数组可以认为是函数f（x），我们现在把该数组改为f的反函数即f'(x)。即：
f(x): {1, -1, 1, 2, 0, 3}; （明文）abcdef -> BADFEC （密文）
f'(x): {1, -1, 3, -1, 0, 4}; （密文）ABCDEF -> bafced （明文）
这样，我们就能根据密文，直接得到明文。因此我们得到第二个版本的代码如下：
1119_Version_02
/*旋转圆盘的解密问题，改进后为50ms*/
#include <stdio.h>
#include <string.h>
/*6个转盘，前3个存储的是正向偏移值，后3个存储的是字符状态！！*/
char rotor0[27],rotor1[27],rotor2[27];
char buf0[27], buf1[27], buf2[27];
/*每个转盘的当前位置指针！，指示每个圆盘的当前起点*/
int p0,p1,p2;
/*整体顺时针转动一次！则位置向后移动一格*/
void RotateRotors(int m)
{
p0--;
if(p0==0)
{
p0=m;
p1--;
if(p1==0)
{
p1=m;
p2--;
if(p2==0) p2=m;
}
}
}
/*根据输出的密文，得出原文，都是大写字母, pointer是该rotor的指针位置*/
char GetPlainChar(const char* rotor, int m, int pointer, char c)
{
return 'A' + (c - 'A' + rotor[ (pointer+ c-'A')%m ]) % m;
}
/*把字符串换算为偏移值(全部转为正数)， m为每个圆盘的字符个数*/
/*rotors[3,4,5]存储的是字符串！*/
void InitRotors(int m)
{
int i;
/*计算出反推明文的偏移数组*/
for(i=0; i<m; i++)
{
rotor0[ buf0[i]-'A' ] = (('A'+i) - buf0[i] + m)%m;
rotor1[ buf1[i]-'A' ] = (('A'+i) - buf1[i] + m)%m;
rotor2[ buf2[i]-'A' ] = (('A'+i) - buf2[i] + m)%m;
}
}
int main()
{
int m, n, count=1, i;
char line[1024], *s;
while(1)
{
/*读入密码数*/
scanf("%d", &m);
if(m==0)
break;
/*每个test case之间插入一个空行*/
if(count!=1) printf("\n");
printf("Enigma %d:\n", count++);
/*读入三个rotor*/
scanf("%s", buf0);
scanf("%s", buf1);
scanf("%s", buf2);
/*初始化Rotors[0,1,2]*/
InitRotors(m);
/*读取输入的密文数*/
scanf("%d",&n);
/*解密*/
for(i=0;i<n;i++)
{
/*设置圆盘的初始状态*/
p0=p1=p2=m;
scanf("%s", line);
s=line;
while(*s)
{
*s='A' + (*s - 'A' + rotor2[ (p2+ *s-'A')%m ]) % m;
*s='A' + (*s - 'A' + rotor1[ (p1+ *s-'A')%m ]) % m;
*s='A' + (*s - 'A' + rotor0[ (p0+ *s-'A')%m ]) % m;
*s=*s - 'A' + 'a';/*化为小写字母*/
RotateRotors(m);
s++;
}
printf("%s\n", line);
}
}
return 0;
}
版本2的运行时间为50ms，（两个版本的内存占用都是100多K，属于小空间），因此这个解无法上榜。暂时没有想到进一步提高速度的方法，因此这道题暂且就到这里了。
---------------------------------------------------------------------------------------------
（2）1115题：Digital Roots
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1115
题目要求计算一个正整数的digital root，也就是计算一个10进制正整数n的所有位的和，如果结果不是一位数，继续计算，直到得到一位数为止，称为n的digital root。例如当n=39，则求取过程如下：3+9=12， 1+2=3；即digital root (39) = 3;
可见此题相当简单，但是这个题有一个小小的“注意事项”，就是输入的n可能很大，因此在读取输入时，我们不能当作一个普通数据类型读入，而是用一个字符串整体读入，求出第一次的数位和以后即可用常规数据类型计算。代码如下：
1115_digital_root
/*1115题：求一个正数的digital root*/
#include <stdio.h>
#include <string.h>
/*得到初始值，因为整数可能很大！*/
int getinitsum(const char* line)
{
int sum=0;
char *s=line;
while(*s)
{
sum+=*s-'0';
s++;
}
return sum;
}
/*求n的数位和*/
int getsum(int n)
{
int sum=0;
while(n)
{
sum+=n%10;
n/=10;
}
return sum;
}
/*求n的digital root*/
int getroot(int n)
{
int sum=getsum(n);
while(sum>=10)
{
sum=getsum(sum);
}
return sum;
}
int main()
{
int n, root;
char line[1024];
while(scanf("%s", line)!=EOF && strcmp(line,"0")!=0)
{
n=getinitsum(line);
root=getroot(n);
printf("%d\n",root);
}
return 0;
}
---------------------------------------------------------------------------------------------
（3）1476 Weird Clock（怪异钟）：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1476
题目很简单，一个钟只有分针（仅能表示0~59分），它自己不会走，只有投入一种硬币，它才会走。硬币上标有一个数字d，则该钟向前走当前时间s（分钟）的d倍，例如当时钟分针为45分钟时(s=45)，投入d=2的硬币，该钟将向前走45*2=90分钟，指向15分。现在输入时钟的当前分钟，和硬币上的数字d，问最少投入多少个这样的硬币后指针指向0点，如果永远不可能指向0点，则输出impossible。
这个问题实际上很简单，但是我们需要谨慎考虑impossible的情况，否则我们的代码可能会陷入死循环！考虑impossible的情况，必然是在旋转落点上进入了重复，即在投入一些硬币后，分针重新指向此前已经达到过的分钟数，这时即永远无法指向0点。因此我们用一个flag数组标记分针已经到达过的位置，只要分针到达的位置重复，就说明是impossible的情况，例如分钟为10，d=2时，分钟的轨迹为：10->30->30->30->...。代码如下：
1476_weird_clock
/*怪异钟*/
#include <stdio.h>
char flag[60];
/*s为初始分钟，d为硬币上的数字*/
int getcount(int s, int d)
{
int count=0;
memset(flag, 0, 60);
flag[s]=1;
while(s%60)
{
s=(s*(d+1))%60;
if(flag[s]) /*如果曾经到达过，则impossible*/
return -1;
flag[s]=1; /*留下到达过该位置标记*/
count++;
}
return count;
}
int main()
{
int s,d,count;
while(scanf("%d %d", &s, &d)!=EOF && s!=0)
{
count=getcount(s,d);
if(count>=0)
printf("%d\n",count);
else
printf("Impossible\n");
}
}
----------------------------------------------------------------------------------------------
（4）1733：Common Subsequence （最长公共子序列问题）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1733
该题属于动态规划经典命题之一，算法书都会讲到，因此我原样引用了《软件设计师教程》书中的代码。需要注意的是，这个代码比较原始，空间效率不高，可以进一步改进。代码原理就不解释了。
1733_common_subsequence
/*求最长公共子序列的长度*/
#include <stdio.h>
#include <string.h>
#define N 1024
char a[N],b[N];
/*char str[N];*/
char c[N][N];
/*输出最长子序列的长度*/
int lcs_len(char *a, char *b, int c[][N])
{
int m=strlen(a), n=strlen(b), i, j;
for(i=0;i<=m;i++)
c[i][0]=0;
for(j=1;j<=n;j++)
c[0][j]=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
return c[m][n];
}
/*找出最长公共子序列*/
char* build_lcs(char s[], char *a, char *b)
{
int k, i=strlen(a), j=strlen(b), c[N][N];
k=lcs_len(a,b,c);
s[k]='\0';
while(k>0)
{
if(c[i][j]==c[i-1][j])
i--;
else if(c[i][j]==c[i][j-1])
j--;
else
{
s[--k]=a[i-1];
i--;
j--;
}
}
return s;
}
int main()
{
while(scanf("%s %s", a, b)!=EOF)
printf("%d\n", lcs_len(a, b, c));
return 0;
}
--------------------------------------------------------------------------------------------
（5）2405 Specialized Four-Digit Numbers：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2405
题目描述也很简单，求出所有满足下列条件的4位数（10进制），该数字用10进制，12进制，16进制表示时，数位和相等。例如2992是第一个满足条件的数字，12进制为1894，16进制为BB0， 2+9+9+2 = 1+8+9+4 = B+B+0 =22；该题属于典型简单题，穷举即可，无须解释，代码如下：
2405_specialized_four_digit_numbers
/*输出一个数字的10，12，16进制位之和相等的4位数*/
#include <stdio.h>
/*计算数字n以base为基数时的位和*/
int getsum(int n, int base)
{
int sum=0;
while(n)
{
sum+=n%base;
n/=base;
}
return sum;
}
int main()
{
int i,sum1,sum2,sum3;
for(i=2992;i<=9999;i++)
{
sum1=getsum(i, 16);
sum2=getsum(i, 12);
if(sum1!=sum2) continue;
sum3=getsum(i, 10);
if(sum3==sum1)
printf("%d\n", i);
}
return 0;
}