星期天這天一口氣AC了五道題，除了1009外基本都可算是簡單題。
（1）1009 Enigma：
題目是講解二戰期間德國使用的密碼機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;
/*複原為字元串，同時矯正負數值*/
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]);
/*讀取輸入的密文數*/
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*/
/*6個轉盤，前3個存儲的是正向偏移值，後3個存儲的是字元狀态！！*/
char rotor0[27],rotor1[27],rotor2[27];
char buf0[27], buf1[27], buf2[27];
/*每個轉盤的目前位置指針！，訓示每個圓盤的目前起點*/
int p0,p1,p2;
/*整體順時針轉動一次！則位置向後移動一格*/
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)
/*計算出反推明文的偏移數組*/
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;
scanf("%d", &m);
scanf("%s", buf0);
scanf("%s", buf1);
scanf("%s", buf2);
/*初始化Rotors[0,1,2]*/
InitRotors(m);
scanf("%d",&n);
p0=p1=p2=m;
scanf("%s", line);
s=line;
*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;
版本2的運作時間為50ms，（兩個版本的記憶體占用都是100多K，屬于小空間），是以這個解無法上榜。暫時沒有想到進一步提高速度的方法，是以這道題暫且就到這裡了。
---------------------------------------------------------------------------------------------
（2）1115題：Digital Roots
題目要求計算一個正整數的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*/
/*得到初始值，因為整數可能很大！*/
int getinitsum(const char* line)
int sum=0;
char *s=line;
while(*s)
sum+=*s-'0';
s++;
return sum;
/*求n的數位和*/
int getsum(int n)
while(n)
sum+=n%10;
n/=10;
/*求n的digital root*/
int getroot(int n)
int sum=getsum(n);
while(sum>=10)
sum=getsum(sum);
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);
---------------------------------------------------------------------------------------------
（3）1476 Weird Clock（怪異鐘）：
題目很簡單，一個鐘隻有分針（僅能表示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
/*怪異鐘*/
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 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 （最長公共子序列問題）
該題屬于動态規劃經典命題之一，算法書都會講到，是以我原樣引用了《軟體設計師教程》書中的代碼。需要注意的是，這個代碼比較原始，空間效率不高，可以進一步改進。代碼原理就不解釋了。
1733_common_subsequence
/*求最長公共子序列的長度*/
#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--;
s[--k]=a[i-1];
return s;
while(scanf("%s %s", a, b)!=EOF)
printf("%d\n", lcs_len(a, b, c));
--------------------------------------------------------------------------------------------
（5）2405 Specialized Four-Digit Numbers：
題目描述也很簡單，求出所有滿足下列條件的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位數*/
/*計算數字n以base為基數時的位和*/
int getsum(int n, int base)
sum+=n%base;
n/=base;
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);