蓝桥杯c++算法学习【5】之枚举与模拟（卡片、回文日期、赢球票、既约分数：：：非常典型的比刷例题！！！）

别忘了请点个赞+收藏+关注支持一下博主喵！！！! ! ! ！！！

关注博主，更多蓝桥杯nice题目静待更新:)

枚举与模拟

一、卡片：

【问题描述】

小蓝有很多数字卡片，每张卡片上都是一个数字（0到9）。

小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其他数。

想知道自己能从1拼到多少。

例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10，但是拼 11时卡片1已经只有一张了，不够拼出11。

现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少? 提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分

解析：

本题思路较为简单，可直接从数字1开始往后枚举，枚举的同时检查剩下的卡片能不能拼出当前枚举到的数字即可。

定义cnt[i] 表示刻有数字i的卡片张数。那么按照题目的意思，初始化cnt[0∼9]=2021，参考代码如下。

int cnt[10];
for(int i = 0 ; i <= 9 ; i++) cnt[i] = 2021;

若我们将步骤拆分为两步，则可分为枚举、检查。枚举没什么问题，写个循环即可，但该怎么检查呢?

首先就需要把一个数在十进制下的每一位数字求出来。怎么求呢? 可以将该数对 10 取模，这样就得到了个位上的数字；再除以10，这样原本十位上的数字就跑到了个位上；然后再对10取模……反复这个过程，就可以得到这个数在十进制下所有数位上的数字了。

得到数位上的所有数字后再看看这些数字对应的卡片够不够，不够的话就说明这个数拼不了，就停止枚举，这样答案就为上一个枚举的数。

bool check(int x) { // x 表示当前枚举的数while (x) {int b = x % 10; // 获取十进制下的每个数位if (cnt[b] > 0) cnt[b]--; // 这个数位对应的卡片个数 -1else return false; // 如果卡片不够了，则无法拼凑出该数x /= 10; // 将十位变为个位}return true;
}

至此，检查的模块就完成了。不过我们还可以进行一点小小的优化。

我们的枚举是从1开始的，如果分别看枚举数的个位、十位……上的数字，那么会得到如下的内容。

显然，个、十、百、千、万……每一数位的变化都是有周期性的。每个周期中各个数字出现的次数都是相同的，且每一数位都是从1开始变化的。因此，刻有数字1的卡片一定会被最早使用完，我们只需要对该卡片的张数作判断就好，具体代码可见参考代码第4∼14行。

#include <bits/stdc++.h>
using namespace std;int cnt[10];bool check(int x) { // x 表示当前枚举的数while (x) {int b = x % 10; // 获取十进制下的每个数位if (b == 1) {if (cnt[1] == 0) return false;cnt[1]--;}x /= 10; // 将十位变为个位}return true;
}signed main() {for (int i = 0; i <= 9; i++) cnt[i] = 2021;for (int i = 1;; i++) {if (!check(i)) return cout << i - 1 << '\n', 0;}return 0;
}

最终答案为3181。

二、回文日期：

【问题描述】

2020年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按“yyyymmdd”的格式写成一个8位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202即2021年12月2日。

也有人表示20200202并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100年后就能遇到下一个ABABBABA型的回文日期：21211212即2121年12月12日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个ABAB BABA型的回文日期各是哪一天。

【输入格式】

输入包含一个八位整数N，表示日期。对于所有评测用例，10000101⩽N⩽89991231，保证N是一个合法日期的8位数表示。

【输出格式】

输出两行，每行1个八位数。第一行表示下一个回文日期，第二行表示下一个ABAB BABA型的回文日期。

【样例输入】

20200202

【样例输出】

20211202 21211212

【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解析：

根据题意，我们可以将题目拆解为如何判断回文和如何枚举日期两个部分来解决。

1. 如何判断回文

对于一个8位数的整型日期，可以通过除法和取余运算来获取它的每一位数字。比如：

若整数date 的值为20050511，它从高到低的每一数位上的数可以通过下列方法得到。
• data / 10000000 = 2；
• data / 1000000 % 10 = 0；
• data / 100000 % 10 = 0；
• data / 10000 % 10 = 5；
• data / 1000 % 10 = 0；
• data / 100 % 10 = 5；
• data / 10 % 10 = 1；
• data % 10 = 1。

对于本题，若用a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]、a[8] 分别存储每一位，则一个回文日期须满足:

一个ABABBABA 型回文日期须满足以下条件。

a[1] = a[3] = a[6] = a[8]；a[2] = a[4] = a[5] = a[7].

对于一个日期字符串，可以直接通过下标来获取它的每一位数字。例如，string date = “20050511”，它从高到低的每一位分别可以通过data[0],data[1],...,data[7] 得到。判断回文日期及ABABBABA型回文日期的方式和上述方法类似。

不难看出，字符串获取日期的每一位数字是要比整型简单的，所以在判断回文日期及 ABABBABA 型回文日期时可以将整型转换为字符串来操作，如参考代码所示。

#include <bits/stdc++.h>
using namespace std;int date = 20050511;
string s = to_string(date); // 将整型转换为字符串, s = "20050511"// 判断回文日期
bool check1(int date) {string s = to_string(date);if (s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4])return true;return false;
}// 判断 ABABBABA 型回文日期
bool check2(int date) {string s = to_string(date);if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])return true;return false;
}

2. 如何枚举日期

对于一个整型日期，可以用最简单的方式枚举，即令该日期不断+1，直到出现满足ABAB BABA 型的回文日期。

但这样存在一个问题：会枚举出许多不合法的日期（如20209999）。为此，我们需要对日期进行合法性判断：设y,m,d分别表示年、月、日，month[i]表示第i个月的天数，那么当m12或dmonth[m]时日期不合法，反之日期合法，如参考代码所示。

#include <iostream>
#include <string>
using namespace std;int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check(int date) {string s = to_string(date);//stoi->将字符串转为整型int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2));if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;else month[2] = 28;if (m < 1 || m > 12 || d < 1 || d > month[m]) return false;return true;
}int main() {int date = 20050511;for (int i = date + 1;; i++) {if (!check(i)) continue;// 找到下一个有效日期后，可以在这里进行进一步处理// 例如，检查是否是回文日期或 ABABBABA 型回文日期cout << "Next valid date: " << i << endl;break;}return 0;
}

不过这样的枚举量是相当大的，要在比赛中完成本题要求的所有测试数据不太现实。

那么，还有什么枚举方法呢?

可以直接枚举合法日期。枚举合法日期只需模拟日期的变化规律即可，对应参考代码如下所示。

#include <iostream>
using namespace std;int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main() {int date = 20050511;int y = date / 10000, m = date / 100 % 100, d = date % 100;for (int i = y;; i++) {if (i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29; // 闰年2月有29天else month[2] = 28;int j = (i == y) ? m : 1; // 如果是i = y，则月份从m开始枚举，否则从1开始枚举for (; j <= 12; j++) {int k = (i == y && j == m) ? d : 1; // 如果i = y并且j = m，则日从d开始枚举，否则从1开始枚举for (; k <= month[j]; k++) {int new_date = i * 10000 + j * 100 + k;// 在这里可以进行进一步处理，例如检查是否是回文日期或ABABBABA型回文日期cout << "Next valid date: " << new_date << endl;return 0; // 找到第一个有效日期后退出程序}}}return 0;
}

我们还可以只枚举年份。因为答案一定是个回文日期（即回文串），所以枚举年份y，再将其翻转得到y′，得到的y+y′就一定是个回文串，如下页图所示。接着再对该串所对应的日期进行合法判断、ABABBABA型回文判断即可。

综上：

枚举合法日期：

#include <bits/stdc++.h>
using namespace std;int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int date, ans1, ans2;// 判断日期是否为回文
bool check1(int date) {string s = to_string(date);if (s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4])return true;return false;
}// 判断日期是否满足 ABABBABA 型回文
bool check2(int date) {string s = to_string(date);if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])return true;return false;
}signed main() {cin >> date;int y = date / 10000, m = date / 100 % 100, d = date % 100;for (int i = y;; i++) {if (i % 400 == 0 || (i % 100 != 0 && i % 4 == 0))month[2] = 29;elsemonth[2] = 28;int j = (i == y) ? m : 1;for (; j <= 12; j++) {int k = (i == y && j == m) ? d + 1 : 1;for (; k <= month[j]; k++) {int new_date = i * 10000 + j * 100 + k;if (check1(new_date) && ans1 == 0)ans1 = new_date;if (check2(new_date)) {cout << ans1 << '\n' << new_date << '\n';return 0; // 当找到了 ABABBABA 型回文日期时，结束程序}}}}return 0;
}

枚举年份：

#include <bits/stdc++.h>
using namespace std;// month[1~12]分别记录1~12月每月的天数
int date, month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 判断日期是否合法
string check(int date) {string s = to_string(date), t = to_string(date); // 将整型转换为字符串reverse(t.begin(), t.end()); // 翻转s += t; // 将s翻转后再与s拼接，拼接后的字符串一定会是个回文串int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2));if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;else month[2] = 28;if (m < 1 || m > 12 || d < 1 || d > month[m]) return "-1";return s;
}// 判断日期是否是ABABBABA型回文
string check2(int date) {string s = to_string(date), t = to_string(date);reverse(t.begin(), t.end()); // 翻转s += t;if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return s;return "-1";
}signed main() {cin >> date;string ans1 = "";for (int i = date / 10000;; i++) {// 注意：date（输入的日期）不能作为答案if (check(i) == "-1" || check(i) == to_string(date)) continue;if (ans1 == "") ans1 = check(i);if (check2(i) != "-1") {cout << ans1 << '\n' << check2(i) << '\n';return 0;}}return 0;
}

三、赢球票：

【问题描述】

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出N张卡片（上面写着1,...,N的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数: 1,2,3...

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一张卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

卡片排列是123，我们从1号卡开始数，就把1号卡拿走。再从2号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了1张球票。

还不算太坏！如果我们开始就傻傻地从2或3号卡片数起，那就一张卡片都拿不到了。

如果运气好，卡片排列是213，那我们可以顺利拿到所有的卡片！

本题目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）。

【输入格式】

第一行一个整数N(N⩽100)，表示卡片数目。第二行N个整数，表示顺时针排列的卡片。

【输出格式】

输出一行，一个整数，表示最好情况下能赢得多少张球票。

【样例输入】

3 123

【样例输出】

解析：

比如：

这是一道十分经典的模拟题。刚着手解决本题时，可能绝大部分人都会提出4个问题。

问题1. 题目给定的是一个环（圆圈），我们需要如何模拟在环上的移动呢?

问题2. 如何表示被拿走的卡片呢?

问题3. 从哪个位置（起点）开始数数能拿走最多的卡片呢?

问题4. 游戏什么时候会结束呢? 下面依次对这4个问题进行分析。

对于问题1

对于在序列上的移动，如果想从当前位置顺时针移动到下一个位置，只要让下标+1即可。但当处于第n个位置时，由于没有第n+1个位置，所以无法移动。而对于环，第n+1 个位置即第1个位置，所以从第n个位置移动到下一个位置只要让下标为1即可，其他位置的移动和序列相同。

对于问题2：

可以对被拿走的卡片打上标记。定义flag[]，其中flag[i]表示第i张是否被取走（flag[i]=1 表示被取走，flag[i]=0 表示没有被取走）。下图展示了第2张卡片被拿走的情况。

对于问题3：

不知道。既然不知道，就将每个位置都作为一次起点并模拟整个过程，再从中选出最大的卡片和（即答案）。

对于问题4：

游戏结束分为以下两种情况。

• 取走所有的卡片（即取走n张卡片）。

• 当前数的数大于n（不可能再取走卡片了）。

解决了上述4个问题，就可以开始解题了。

按照上面的分析，我们需要完成以下几点。

（1）枚举起点，并在每次枚举了一个起点后将所有卡片的flag初始化为0。

（2）有了起点后就可以模拟数数的过程，流程图如下。

•判断游戏是否结束。

•判断当前位置的卡片是否被取走（若被取走，则移动到下一个位置）。

•判断当前位置的卡片的值是否和数的数的值相同（相同则取走该卡片，并重新开始数数）。

•判断这次模拟得到的结果是否可以作为答案。

代码如下：

#include <bits/stdc++.h>
using namespace std;const int N = 1e2 + 10;
int n, a[N], flag[N];signed main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int ans = 0; // ans 表示答案for (int i = 1; i <= n; i++) { // i 表示枚举的起点// 将所有卡片的 flag 初始化为 0for (int j = 1; j <= n; j++) flag[j] = 0; // flag[j] = 1 表示卡片被取走，反之没被取走int num = 1, pos = i, sum = 0, cnt = 0; // num 表示数的数的值，pos 表示当前位置，sum 表示以 i 为起点数数所能取走的卡片的和，cnt 表示拿走的卡片的数量// 开始模拟while (1) {// 判断游戏是否结束if (cnt == n || num > n) break; // 如果取走了所有卡片，或者数的数大于 n（不可能再取走卡片了），则游戏结束// 判断当前位置的卡片是否被取走if (flag[pos] == 1) { // 如果该卡片已被取走，则移动到下一个位置if (pos == n) pos = 1;else pos++;continue;}// 数的数和当前位置卡片的值相同时取走该卡片（a[pos] 表示第 pos 张卡片的值）if (num == a[pos]) {sum += a[pos]; // 取走卡片的和 + a[pos]cnt++; // 取走的卡片个数 + 1num = 1; // 取走卡片后要重新数数flag[pos] = 1; // 取走卡片后该卡片对应的 flag 置为 1// 移动到下一个位置if (pos == n) pos = 1;else pos++;} else {// 数的数和当前位置卡片的值不相同时num++; // 数的数的值 + 1// 移动到下一个位置if (pos == n) pos = 1;else pos++;}}// 模拟结束，判断该模拟结果是否可以作为答案if (sum > ans) ans = sum;}cout << ans << '\n';return 0;
}

四、既约分数

【问题描述】

如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。

例如 $\frac{3}{4}$ , $\frac{1}{8}$ , $\frac{7}{1}$ ，都是既约分数。

请问，有多少个既约分数，分子和分母都是1到2020之间的整数（包括1和2020）？

【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解析：

用一句话概括题意，即统计分子、分母的范围均为1∼2020且分子、分母的最大公约数（gcd）为 1 的分数的个数。

解题的思路较为简单，只需从1∼2020枚举分子，再从1∼2020枚举分母，然后判断分子、分母的最大公约数是否为1（若为1则答案个数+1）即可。不过在此之前，我们需要知道如何求解两个数的最大公约数。

求最大公约数的方法很多，如果想图个方便，可以直接调用 C++ 的 algorithm 库中的＿gcd() 函数来求解。如果不知道这个函数也没有关系，因为想求解两个数的最大公约数并不难。我们可以采用常用的辗转相除法（国际上也称“欧几里得算法”），它的代码如下。

【复杂度为 O(log)】

int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}

知道了如何求解两个数的最大公约数后，就可以枚举统计答案了。

【复杂度为 O(N2logN)】

#include <bits/stdc++.h>
using namespace std;signed main() {int ans = 0;for (int i = 1; i <= 2020; i++) {for (int j = 1; j <= 2020; j++) {if (gcd(i, j) == 1) ans++;}}cout << ans << '\n';return 0;
}

最终答案为2481215。

拓展提高:

我们来考虑一下如何优化程序的时间复杂度。

若两个数 i,j（j ⩽ i）的最大公约数为1，则 $\frac{j}{i}$ 是一个既约分数， $\frac{i}{j}$ 也是一个既约分数。所以我们可以从1∼2020枚举i，从1∼i枚举j，这样得到的i,j 就满足j ⩽ i。接着判断 i, j 的最大公约数是否为1（若为1，则 $\frac{j}{i}$ 是既约分数）。若用 cnt 来统计有多少对 $\frac{j}{i}$ 满足j ⩽ i且 i,j 的最大公约数为1，则答案为 cnt× 2 − 1 （乘2是因为 $\frac{j}{i}$ 的倒数 $\frac{i}{j}$ 也是既约分数，减1是因为 $\frac{1}{1}$ 的倒数还是 $\frac{1}{1}$ ，重复计算了一次，要减掉，见下图）。

这样就可以细微地优化程序计算的次数了。

不过程序的复杂度仍为O(N2logN)。有没有什么办法能降低复杂度呢?答案自然是有。

这里我们要用到 唯一分解定理 欧拉函数欧拉筛

对于最大公约数为1的两个整数，我们称它们的关系为互质。在数论中，1∼n中与n 互质的数的个数被称为欧拉函数（记作phi[n]）。

由欧拉函数的定义可知满足j⩽i，且i,j 最大公约数为1的 $\frac{j}{i}$ 的个数就为phi[i]。

我们要求的是1∼2020 内满足j⩽i且i,j 最大公约数为1的 $\frac{j}{i}$ 的个数，即1∼2020 内所有数的欧拉函数的和，即 cnt =

欧拉函数的通项公式：

其中p1,p2,...,pk 为 n 的所有不重复质因子。

要想得到n的所有不重复质因子，我们可以采用数论利器——唯一分解定理。

提示如下：：：：：：：：：：：：：：：：：

综上，我们可以写出如下代码，完成对n的不重复质因子的求解。

int p[N]; // p[] 记录因子，p[1] 是最小因子int getPrime(int n) {int k = 0; // k 记录 n 的质因子的个数for (int i = 2; i * i <= n; i++) {if (n % i == 0) {p[++k] = i;while (n % i == 0) n /= i; // 把 n 重复的质因子去掉}}if (n > 1) p[++k] = n; // n 没有被除尽，是素数return n; 
}

再根据欧拉函数的通项公式

int getPhi(int n) {int phi = n, k = getPrime(n);for (int i = 1; i <= k; i++) { // 枚举所有质因子：p1, p2, ..., pkphi = phi - phi / p[i]; // (phi - phi / p[i]) 等价于 phi * (1 - 1/p[i])}return phi;
}

因为在本题中质因子的作用只是为了计算欧拉函数，所以可以不用开辟数组记录质因子，而是每得到一个质因子就将其放入欧拉函数的通项公式中计算，这样两份代码就能合并在一起，具体代码可见如下参考代码的第4∼16行。

#include <bits/stdc++.h>
using namespace std;int solve(int n) {int phi = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) { // i 是 n 的质因子phi = phi - phi / i; // 将其丢入欧拉函数的通项公式中计算while (n % i == 0) n /= i; // 把 n 重复的质因子去掉}}if (n > 1)phi = phi - phi / n; // n 没有被除尽，是素数，将其丢入欧拉函数的通项公式中计算return phi;
}signed main() {int ans = 0;for (int i = 1; i <= 2020; i++)ans += solve(i);cout << ans * 2 - 1 << '\n';return 0;
}

当然，求一个数的欧拉函数还有更好的求法，比如用Pollard_Rho寻找因子、用Miller_ Rabin测试质数，以将复杂度优化到O(N1 4)。不过这种做法码量极大，所涉及的知识点难度也高，蓝桥杯赛场上几乎是不可能用上的。

此外，我们还可以使用欧拉筛，它的作用是以O(N)的时间复杂度求出1∼N中每个数的欧拉函数。这样，程序的复杂度就可以被进一步优化。

#include <bits/stdc++.h>
using namespace std;int n, phi[2021], prime[2021];signed main() {// 欧拉筛phi[1] = 1;for (int i = 2; i <= 2020; i++) {if (!prime[i]) {prime[++n] = i;phi[i] = i - 1;}for (int j = 1; j <= n && i * prime[j] <= 2020; j++) {prime[i * prime[j]] = 1;if (i % prime[j] == 0) {phi[i * prime[j]] = phi[i] * prime[j];break;}phi[i * prime[j]] = phi[i] * (prime[j] - 1);}}int cnt = 0;for (int i = 1; i <= 2020; i++)cnt += phi[i];cout << 2 * cnt - 1 << '\n';return 0;
}

以上就是这次博客的内容了

别忘了请点个赞+收藏+关注支持一下博主喵！！！

关注博主，更多蓝桥杯nice题目静待更新:)