蓝桥杯c++算法学习【1】之枚举与模拟(卡片、回文日期、赢球票:::非常典型的比刷例题!!!)

embedded/2024/11/8 22:36:59/

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

关注博主,更多蓝桥杯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                                                                                                                                  样例输出】                                                                                                                                                1

解析:

比如: 

         这是一道十分经典的模拟题。刚着手解决本题时,可能绝大部分人都会提出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;
}

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

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

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


http://www.ppmy.cn/embedded/136007.html

相关文章

如何在算家云搭建CodeGeeX4(文本生成)

一、 大模型 CodeGeeX4 简介 CodeGeeX4 模型系列的开源版本 CodeGeeX4-ALL-9B。它是一个在 GLM-4-9B 上持续训练的多语言代码生成模型&#xff0c;显著增强了其代码生成能力。使用单个 CodeGeeX4-ALL-9B 模型&#xff0c;它可以支持代码补全和生成、代码解释器、网页搜索、函数…

人工智能——小白学习指南

知孤云出岫 目录 1. **智能评测系统**2. **个性化学习路径推荐**3. **虚拟学习助手**4. **学习行为分析**5. **数据驱动的教学决策**6. **自动化课程推荐**7. **数据隐私与安全保护** 人工智能知识点的总结和学习路线&#xff0c;以数据表格形式呈现&#xff0c;并附带在教育行…

A Consistent Dual-MRC Framework for Emotion-cause Pair Extraction——论文阅读笔记

前言 这是我第一次向同学院同年级的学生和老师们汇报的第一篇论文,于2022年发表在TOIS上,属于CCF A类,主要内容是将MRC应用到情感原因对抽取中。 论文链接:用于情绪-原因对提取的一致双 MRC 框架 |信息系统上的 ACM Transactions 这里我就不放上我自己翻译的中文版还有我…

【网络安全 | 漏洞挖掘】通过有趣的逻辑漏洞实现账户接管

未经许可,不得转载。 文章目录 正文正文 我受邀参加某公司的一个私密漏洞赏金项目。在测试时,我发现该平台采用 PIN 码登录系统,而不是传统密码。每次登录尝试时,系统会发送一个 6 位数的 PIN 码。 系统设置了频率限制,防止暴力破解 PIN 码。 同时我发现,每次更改账号邮…

Axure设计之左右滚动组件教程(动态面板)

很多项目产品设计经常会遇到左右滚动的导航、图片展示、内容区域等&#xff0c;接下来我们用Axure来实现一下左右滚动的菜单导航。通过案例我们可以举一反三进行其他方式的滚动组件设计&#xff0c;如常见的上下滚动、翻页滚动等等。 一、效果展示&#xff1a; 1、点击“向左箭…

Spring Boot 与 Vue 共筑卓越租车管理新平台

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 &#x1f345;获取源码联系方式请查看文末&#x1f345; 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目…

循环神经网络RNN

概念 大家在学习深度学习时&#xff0c;都是按照“人工神经网络”、“卷积神经网络”的顺序来学习的。我们在学习的过程中可能会发现这样网络可能不适用一些带有“时间序列”的问题。 比如下面&#xff0c;要预测股票价格&#xff1a; 时间特征1特征2特征3特征4价格2024-11-…

3种最难学习和最容易学习的 3 种编程语言

无论您是想改变职业方向还是扩展程序员的技能&#xff0c;您选择学习的语言都会显着影响您的时间投入和前景。 一些语言使用熟悉的语法&#xff0c;欢迎为繁重的工作提供最少的代码命令&#xff0c;并且是开源的&#xff0c;具有有用的开发人员社区&#xff0c;可指导用户充分利…