目录：1、潜伏者 【map】 2、Hankson的趣味题【数论】3、mayan游戏【dfs】
题目：
1. 潜伏者
(spy.pas/c/cpp)
【问题描述】
R 国和S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。
历经艰险后，潜伏于S 国的R 国间谍小C 终于摸清了S 国军用密码的编码规则：
1、 S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容
与加密后所的内容均由大写字母‘A’—‘Z’构成（无空格等其他
字母）。
2、 S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中
的所有字母替换为其对应的“密字”。
3、 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。
“密字”可以和原字母相同。
例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则
原信息“ABA”被加密为“ACA”。
现在，小C 通过内线掌握了S 国网络上发送的一条加密信息及其对应的原信息。小C
希望能通过这条信息，破译S 国的军用密码。小C 的破译过程是这样的：扫描原信息，对
于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认
为在密码里y 是x 的密字。如此进行下去直到停止于如下的某个状态：
1、 所有信息扫描完毕，‘A’—‘Z’所有26 个字母在原信息中均出现过
并获得了相应的“密字”。
2、 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出
现。
3、 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S 过密码的编
码规则）。例如某条信息“XYZ”被翻译为“ABA”就违反了“不同
字母对应不同密字”的规则。
在小C 忙得头昏脑胀之际，R 国司令部又发来电报，要求他翻译另外一条从S 国刚刚
截取到的加密信息。现在请你帮助小C：通过内线掌握的信息，尝试破译密码。然后利用破
译的密码，翻译电报中的加密信息。
【输入】
输入文件名为spy.in，共3 行，每行为一个长度在1 到100 之间的字符串。
第1 行为小C 掌握的一条加密信息。
第2 行为第1 行的加密信息所对应的原信息。
第3 行为R 国司令部要求小C 翻译的加密信息。
输入数据保证所有字符串仅由大写字母‘A’—‘Z’构成，且第1 行长度与第2 行相
等。
【输出】
输出文件spy.out 共1 行。
若破译密码停止时出现2，3两种情况，请你输出“Failed”（不含引号，注意首字母大写，其它小写）。
否则请输出利用密码翻译电报中加密信息后得到的原信息。
【输入输出样例1】
spy.in spy.out
AA Failed
AB
EOWIE
【输入输出样例1说明】
原信息中的字母‘A’和‘B’对应相同的密字，输出“Failed”。
【输入输出样例2】
spy.in spy.out
QWERTYUIOPLKJHGFDSAZXCVBN Failed
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO
【输入输出样例2说明】
字母‘Z’在原信息中没有出现，输出“Failed”。
【输入输出样例3】
spy.in spy.out
MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP NOIP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO
2. Hankson的趣味题
(son.pas/c/cpp)
【问题描述】
Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：
1、 x和a0的最大公约数是a1；
2、 x和b0的最小公倍数是b1。
Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。
【输入】
输入文件名为son.in。第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。
【输出】
输出文件son.out共n行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；
【输出输出样例】
son.in son.out
2
41 1 96 288 6
95 1 37 1776 2
【说明】
第一组输入数据，x可以是9、18、36、72、144、288，共有6个。
第二组输入数据，x可以是48、1776，共有2个。
【数据范围】
对于50%的数据，保证有1≤a0，a1，b0，b1≤10000且n≤100。
对于100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000且n≤2000。
3．Mayan 游戏
(mayan.cpp/c/pas)
【问题描述】
Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个7 行5 列的棋盘，上面堆放
着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游
戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：
1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方
块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参
见输入输出样例说明中的图6 到图7）；如果目标位置上没有方块，那么被拖动的方块将从
原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2）；
解题报告：
第一题：如果把仔细审题，理解清楚，各种输出failed的条件分析清楚，再用映射map将其密文、译文对应，就没有问题。初次独立写map还是遇到了问题，先开始我定义的是string对应string，然后就报错了，后来改成char就可以了。然后写的时候把对应关系搞反了，应该是密文对应译文，不是译文对应密文。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<string>
5 #include<map>
6 using namespace std;
7 string s1,s2,s3;
8 int len1,len2;
9 map <char,char> m;//改string为char
10 map <char,bool> canmi;
11 bool b=true,all[30];
12 int main()
13 {
14 freopen("spy.in","r",stdin);
15 freopen("spy.out","w",stdout);
16 cin>>s1;len1=s1.size();
17 cin>>s2;
18 cin>>s3;len2=s3.size();
19 memset(all,false,sizeof(all));
20 for (int i=0;i<len1;i++)
21 {
22 char x=s1[i],y=s2[i];//改string为char
23 if (!m[x]){ //没有对应密文
24 if (!canmi[x]){ //密文没有用过，有效
25 m[x]=y;
26 canmi[x]=true;
27 int t=y-64;
28 all[t]=true;
29 }
30 else{
31 b=false;
32 } //密文用过 ，无效 (不能翻译)
33 }
34 else if (m[x]!=y){ //有对应密文且这次对应的与已知的不一样，无效
35 b=false;
36 }
37 if (!b) {
38 printf("Failed");
39 return 0;
40 }
41 }
42 for (int i=1;i<=26;i++)
43 if (!all[i])
44 b=false;
45 if (b){
46 for (int i=0;i<len2;i++)
47 {
48 char x=s3[i];
49 cout<<m[x];
50 }
51 }
52 else printf("Failed");
53 return 0;
54 } View Code
第二题：数论问题，一定要在草稿纸上多算，学会假设列式子，解式子。
解法一：因为gcd(x,a0)=a1,不妨设x=p*a1。
所以lcm(x,b0)=lcm(p*a1,b0)=p*a1*b0/gcd(p*a1,b0)=b1
可以得到p=b1* gcd(p*a1,b0)/a1/b0，枚举gcd(p*a1,b0)后可以求得p，继而求得x，检验gcd(p*a1,a0)是否为a1即可。
因为gcd(p*a1,b0)是b1的约数，所以枚举量为O(sqrt(b1))，最后复杂度为O(N*sqrt(b1)*log(b1)),期望得分100.(表示只得了50，还要再改一下) 解法二：因为x和a0的最大公约数为a1，所以x/a1与a0/a1肯定互质，同样，x和b0的最小公倍数是b1,所以b1/x和b1/b0肯定互质。那么枚举b1 的约数，如果满足，那么可取。注意判断，如果a0%a1 || b1%b0 都除不尽，说明没有答案，同样，在枚举答案的时候，要x/a1,b1/x 除得尽才行。
解法三：因为lcm(x,b0)=x*b0/gcd(x,b0)=b1,所以x/gcd(x,b0)=b1/b0。不妨把b1/b0分解质因数，又因为x有约数a1，结合素数表进行搜索也能快速出结果。效率不好分析，期望得分100。(这个做法还没有做)、
下面给出解法一的50分：
1 #include<iostream>
2 #include<cstdio>
3 #define ll long long
4 using namespace std;
5 int n,ans;
6 int gcd(int a,int b)
7 {
8 return b==0?a:gcd(b,a%b);
9 }
10 int doit(int a0,int a1,int b0,int b1)
11 {
12 int an=0;
13 for (int i=1;i;i++)
14 {
15 if (i*i>b1) break;
16 if (b1%i==0)
17 {
18 int x=b1*i/b0,o=b1/i;
19 if (gcd(x,a0)==a1&&gcd(x,b0)==x*b0/b1) an++;
20 if (i!=o)
21 {
22 int y=b1*o/b0;
23 if (gcd(y,a0)==a1&&gcd(y,b0)==y*b0/b1) an++;
24 }
25 }
26 }
27 return an;
28 }
29 int main()
30 {
31 freopen("son.in","r",stdin);
32 freopen("son.out","w",stdout);
33 cin>>n;
34 for (int i=1;i<=n;i++)
35 {
36 int a0,a1,b0,b1;
37 scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
38 int ans=doit(a0,a1,b0,b1);
39 printf("%d\n",ans);
40 }
41 return 0;
42 } View Code
解法二的100分：
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int n;
5 int gcd(int a,int b)
6 {
7 return b==0?a:gcd(b,a%b);
8 }
9 int main()
10 {
11 freopen("son.in","r",stdin);
12 freopen("son.out","w",stdout);
13 cin>>n;
14 for (int i=1;i<=n;i++)
15 {
16 int a0,a1,b0,b1,ans=0;
17 scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
18 if (a0%a1||b1%b0)
19 {
20 cout<<0;
21 continue;
22 }
23 int t1=a0/a1,t2=b1/b0;
24 for (int j=1;j*j<=b1;j++)
25 if (b1%j==0)
26 {
27 if (j%a1==0) {
28 if ((gcd(j/a1,t1)==1)&&(gcd(b1/j,t2)==1)) ans++;
29 }
30 int x=b1/j;
31 if (x!=j&&x%a1==0){
32 if ((gcd(x/a1,t1)==1)&&(gcd(b1/x,t2)==1)) ans++;
33 }
34 }
35 printf("%d\n",ans);
36 }
37 return 0;
38 } View Code
解法三的标程：
1 #include<iostream>//数据全过。
2 #define MAXN 50000//x一定是b1的因子，找出b1的质因子及其个数
3 #define MAXP 6000//然后搜索b1的因子，进行判断，每组数据不超过0.2秒
4 #define MAXR 1000
5 using namespace std;
6 int p[MAXP],c[MAXR],d[MAXR],total,num,ans,a0,a1,b0,b1,t,n;
7 bool f[MAXN];
8 void init()
9 {
10 memset(f,1,MAXN);
11 for (int i=2;i<=MAXN;++i) if (f[i])
12 {
13 p[++total]=i;
14 for (int j=2,lim=MAXN/i;j<=lim;++j) f[i*j]=false;
15 }
16 }
17 int gcd(int a,int b)
18 {
19 if (b==0) return a;else return gcd(b,a%b);
20 }
21 int lcm(int a,int b)
22 {
23 return a/gcd(a,b)*b;
24 }
25 void dfs(int i,int w)
26 {
27 if (i==num+1)
28 {
29 if (gcd(w,a0)==a1&lcm(w,b0)==b1) ans++;
30 return;
31 }
32 for (int j=0;j<=c[i];++j)
33 {
34 dfs(i+1,w);
35 w*=d[i];
36 }
37 }
38 int main()
39 {
40 init();
41 freopen("son.in","r",stdin);freopen("son.out","w",stdout);
42 scanf("%d",&n);
43 while (n--)
44 {
45 scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
46 num=0;ans=0;
47 t=b1;
48 for (int i=1;i<=total;++i) if (t%p[i]==0)
49 {
50 c[++num]=0;d[num]=p[i];
51 while (t%p[i]==0)
52 {
53 t/=p[i];
54 ++c[num];
55 }
56 if (t==1) break;
57 }
58 if (t!=1) { c[++num]=1;d[num]=t;}
59 dfs(1,1);
60 printf("%d\n",ans);
61 }
62 return 0;
63 } View Code
第三题：这道题是两个多月前做的一道复杂的题，涉及到许多函数，总体来讲是一个dfs，再加上几个剪枝：
- 左右交换是等价的，根据题中的顺序，只需向右交换即可
- 某个颜色方块的数量<=2，则很显然不能被消除
。虽然做过但是考试的时候并没有打算编这个，因为又忘了具体怎么做了。编好后，还是有一些问题：(1)一些细节的判断。(2)在复制相似的代码时，记得改不同的值(3)取变量的名称时最好不要取完整的单词，因为可能在某个库里有这个定义，导致你的定义不能用，比如这次取的count，在自己评测和VJ上评测都过了，在cena上编译错误，因为没有定义到。
这种比较复杂的题，在考试的时候如果有时间一定要把它分为几段过程，一段一段地考虑，化整为零，这样就把题目简化了。一定要有耐心。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>//exit(0);
4 using namespace std;
5 struct nodem{
6 int mp[6][8];
7 };
8 nodem map;
9 struct nodec{
10 int c[12];
11 };
12 nodec coun;
13 int n,ans[6][3];
14 bool no()
15 {
16 for (int i=1;i<=10;i++)
17 if (coun.c[i]==1||coun.c[i]==2) return 1;
18 return 0;
19 }
20 void down()
21 {
22 for (int i=1;i<=5;i++)
23 for (int j=2;j<=7;j++)
24 if (map.mp[i][j]>0)
25 {
26 int k=j-1;
27 while (k>0&&map.mp[i][k]==0)
28 {
29 map.mp[i][k]=map.mp[i][k+1];
30 map.mp[i][k+1]=0;// k+1 不是 j
31 k--;
32 }
33 }
34 for (int i=1;i<=5;i++)
35 {
36 map.mp[i][0]=0;
37 for (int j=1;j<=7;j++)
38 if (map.mp[i][j]) map.mp[i][0]++;
39 else break;
40 }
41 }
42 int clear()
43 {
44 nodem mm;
45 int flag=0;
46 for (int i=1;i<=5;i++)
47 for (int j=1;j<=7;j++)
48 mm.mp[i][j]=0;
49 for (int i=1;i<=3;i++)
50 for (int j=1;j<=7;j++)
51 if (map.mp[i][j]>0 /*!*/&&map.mp[i][j]==map.mp[i+1][j]&&map.mp[i+1][j]==map.mp[i+2][j])
52 {
53 mm.mp[i][j]=1;mm.mp[i+1][j]=1;mm.mp[i+2][j]=1;
54 }
55 for (int i=1;i<=5;i++)
56 for (int j=1;j<=5;j++)
57 if (map.mp[i][j]>0/*!*/&&map.mp[i][j]==map.mp[i][j+1]&&map.mp[i][j+1]==map.mp[i][j+2])
58 {
59 mm.mp[i][j]=1;mm.mp[i][j+1]=1;mm.mp[i][j+2]=1;
60 }
61 for (int i=1;i<=5;i++)
62 for (int j=1;j<=7;j++)
63 if (mm.mp[i][j]==1)
64 {
65 flag=1;
66 coun.c[map.mp[i][j]]--;
67 map.mp[i][j]=0;
68 }
69 return flag;
70 }
71 void doit()
72 {
73 down();
74 while(clear()) down();
75 }
76 void work(int x)
77 {
78 if (x==n+1)
79 {
80 for (int i=1;i<=5;i++)
81 if (map.mp[i][0]>0) return ;// !
82 for (int i=1;i<=n;i++)
83 printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
84 exit(0);//在for循环外
85 }
86 if (no()) return ;
87 nodem m=map;
88 nodec cc=coun;
89 for (int i=1;i<=5;i++)
90 for (int j=1;j<=map.mp[i][0];j++)
91 {
92 if (i<5)
93 {
94 int t=map.mp[i][j];map.mp[i][j]=map.mp[i+1][j];map.mp[i+1][j]=t;
95 ans[x][0]=i-1;ans[x][1]=j-1;ans[x][2]=1;
96 doit();
97 work(x+1);
98 map=m;
99 coun=cc;
100 }
101 if (i>1&&map.mp[i-1][j]==0)
102 {
103 int t=map.mp[i][j];map.mp[i][j]=map.mp[i-1][j];map.mp[i-1][j]=t;
104 ans[x][0]=i-1;ans[x][1]=j-1;ans[x][2]=-1;
105 doit();
106 work(x+1);
107 map=m;
108 coun=cc;
109 }
110 }
111 }
112 int main()
113 {
114 freopen("mayan.in","r",stdin);
115 freopen("mayan.out","w",stdout);
116 cin>>n;
117 for (int i=1;i<=5;i++)
118 {
119 int h=0,k;
120 scanf("%d",&k);
121 while (k!=0)
122 {
123 map.mp[i][++h]=k;
124 coun.c[k]++;
125 scanf("%d",&k);
126 }
127 map.mp[i][0]=h;
128 }
129 work(1);
130 printf("-1\n");
131 return 0;
132 } View Code
总的来说，这次考试呢，提醒我一定要多复习以前做过的题，还有自己的薄弱项，比如数论，动态规划，图论等。刷题刷题。。。
转载于:https://www.cnblogs.com/lx0319/p/5823497.html