这一次我们进行了NOIP2009的真题测试，算是我这几次以来最好的一次，这归功于第三题的思路较为简单和第二题的暴力能够过1/2的点。但是这不意味着这一套题很简单，与之想法，这套题稍有不慎就会有过失性失分，比如第一题容易看漏条件。下面我们来看看：
这道题利用筒的思路，搞一个“字典”，将一个字母的序号（ASCII码减去’a’）作为下标，将与之相对应的字母的序号存储到数组中就可以了，需要注意的是，除了不能A数组中的对应关系必须是一对一的以外，B数组也是这样。 下面来看看代码：
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N=100; const int M=26; char s1[N+5],s2[N+5],s3[N+5]; int len1,len2,len3; int map[M+1]; int main() { freopen("spy.in","r",stdin); freopen("spy.out","w",stdout); memset(map,-1,sizeof(map)); scanf("%s",s1); scanf("%s",s2); scanf("%s",s3); len1=strlen(s1),len2=strlen(s2),len3=strlen(s3); for(int i=0;i<=len1-1;i++) { if(map[s1[i]-'A']!=-1&&map[s1[i]-'A']!=s2[i]-'A')//没有一个下标对应两个字母的情况 { printf("Failed"); return 0; } map[s1[i]-'A']=s2[i]-'A'; } for(int i=0;i<=24;i++) for(int j=i+1;j<=25;j++) if(map[i]==map[j])//没有两个字母对应一个下标的情况 { printf("Failed"); return 0; } for(int i=0;i<=25;i++)//26个字母要集齐 if(map[i]==-1) { printf("Failed"); return 0; } for(int i=0;i<=len3-1;i++) printf("%c",map[s3[i]-'A']+'A'); return 0; }这道题我先是想到了用暴力的方法，因为他的数据范围设这样的： 可见，我们通过最小公倍数（gcd）和最大公因数（lcm）的求解方法，可以通过枚举（枚举到b1）的方法没举出所有可能的值。 这样的暴力法不难想出，我就不细讲了。这种算法可以得50分。 那么正解是怎么样呢？我们通过观察gcd和lcm的性质，可以发现，我们只需要枚举到sqrt(b1)就可以利用其性质推出其余可能的解，而这样就不会超时。代码如下：
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> using namespace std; const int N=10000; int t,a0,a1,b0,b1; int num,tot; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { return (a/gcd(a,b))*b; } bool judge(int i) { return(i