目錄：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