计蒜客信息学3月普及组模拟赛

• 分值：100
• 时间限制：1000ms
• 测试点数目：10

B. 锈湖　　题目链接

• 分值：100
• 时间限制：2000ms
• 测试点数目：10

C. 图 　　　题目链接

• 分值：100
• 时间限制：1000ms
• 测试点数目：10

D. 体育课　　题目链接

• 分值：100
• 时间限制：1000ms
• 测试点数目：20

 下面步入正题

A. 断幺九

今晚，hzj 一如既往地打开雀魂，开始愉快的打麻将。

第一把四人东，前三局都荒牌了，hzj 决定在第四局绝地反击。

终于，hzj 等到了上家放铳，但是由于他打的太过激烈，大脑超速运转，已经无法算清自己的牌了。

现在他只想知道自己的牌是不是断幺九，于是他决定将这个艰巨的任务交给你。

断幺九就是指牌里面没有一筒(Ipin)、九筒(Chupin)、一索(Isou)、九索(Chusou)、一万(Iwan)、九万(Chuwan)、东(Ton)、南(Nan)、西(Sha)、北(Pei)、白(Haku)、发(Hatsu)、中(Chun)。

输入格式

输入共十四行，每行一个字符串，代表 hzj 的牌。

输出格式

一行一个字符串，如果 hzj 的牌是断幺九，输出"Rong,Duan Yao Jiu,1000 Dian"，否则输出"Gong Fu Zai Gao,Ye Pa Duan Yao"。

数据范围

本题共有 10个测试点，每个测试点 10分。

对于第一个测试点，所有的牌都是筒子；

对于第二个测试点，所有的牌都是索子；

对于第三个测试点，所有的牌都是万子；

对于剩下的七个测试点，无特殊限制。

保证数据合法且每行的牌的字符串长度不会超过 100，但是你并不需要知道其他牌的名称。

输出时每行末尾的多余空格，不影响答案正确性

 解题思路:

　　这个题其实困难在于读题，总结一下就是只要这14行没有一筒(Ipin)、九筒(Chupin)、一索(Isou)、九索(Chusou)、一万(Iwan)、九万(Chuwan)、东(Ton)、南(Nan)、西(Sha)、北(Pei)、白(Haku)、发(Hatsu)、中(Chun)，那么这副牌就是断幺九牌。换句话说，只要有一个上述牌，它就不是断幺九牌。代码编辑难度是很简单的。

 1 #include<iostream>
 2 using namespace std;
 3 string s;
 4 int main(){
 5     for(int i=1;i<=14;i++){
 6         cin>>s;
 7         if(s=="Ipin"||s=="Chupin"||s=="Isou"||s=="Chusou"||s=="Iwan"||s=="Chuwan"||s=="Ton"||s=="Nan"||s=="Sha"||s=="Pei"||s=="Haku"||s=="Hatsu"||s=="Chun")
 8         {
 9             cout<<"Gong Fu Zai Gao,Ye Pa Duan Yao";
10             return 0;
11         }
12     }
13     cout<<"Rong,Duan Yao Jiu,1000 Dian";
14     return 0;
15 }

AC代码

B.锈湖

你在玩锈湖。

你卡关了。

你面前有 n 把钥匙，第 i把钥匙的上面写着线索数字 ai?。

你要在其中找到两把钥匙，使得他们线索数字的最大公约数最大。

输入格式

第一行一个正整数 n，第二行 n个正整数 ai?。

输出格式

一行一个整数，表示最大的最大公约数。

数据范围

对于 20% 的数据，n≤500, ai≤500；

对于 30%的数据，n≤4000；

对于 50%的数据，n≤100000，ai≤300000；

对于 100%的数据，n≤5000000，ai≤5000000。

输出时每行末尾的多余空格，不影响答案正确性

3
3 6 8

3

解题思路：

1. 枚举所选的两把钥匙，计算他们的最大公约数。可以通过暴力枚举求两个数的最大公约数。  时间复杂度 O(a_maxn² )，其中 a_max 指最大的 a_i。

2. 枚举所选的两把钥匙，计算他们的最大公约数（欧几里得算法）。 时间复杂度 O(n² log n)。

3. 设 m 为最大的 ai。最后的答案一定是那两把钥匙的约数。那么对每个 ai，将其约数全部扔到一个桶里，如果一个数出现两次，那么可以成为答案。时间复杂度 O(n√m)。

4. 正解：考虑每个x 能成为答案，当且仅当他的倍数在钥匙中出现了两次以上。对于每个x 枚举它的倍数并计数就可判断了。时间复杂度 O(n log n)。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 int vis[5000000],num[5000000];
 6 int main() {
 7     int n, in, mmax = 0;
 8     scanf("%d", &n);
 9     for (int i = 1; i <= n; ++i) {
10         scanf("%d", &in);
11         ++vis[in];
12         mmax = max(mmax, in);
13     }
14     for (int i = 1; i <= mmax; ++i)
15         for (int j = i; j <= mmax; j += i)
16             num[i] += vis[j];
17     for(int i=mmax;i>=1;i--) if(num[i]>=2){
18         cout<<i<<endl;
19         return 0;
20     }
21 }

AC代码

如果不懂，强烈推荐大家看我的另一篇博客：洛谷 P1414 又是毕业季II

至于C、D两题：

本蒟蒻也不会啊，只能先附上题解：2019年3月普及组模拟赛题解三、四题