C/C++程序设计竞赛真题实战特训教程（图解版）

版权信息

书名：C/C++程序设计竞赛真题实战特训教程（图解版）

ISBN：978-7-115-60135-3

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

组  编 蓝桥杯大赛组委会

编  著 张　航　唐鑫程　郑　未

责任编辑 王旭丹

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

读者服务：

微信扫码关注【异步社区】微信公众号，回复“e60135”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。

内 容 提 要

本书面向蓝桥杯全国软件和信息技术专业人才大赛的软件类赛项（以下简称蓝桥杯软件类大赛）中的C/C++语言组的备赛，从数百道历年真题中精选具有代表性的题目作为例题进行分类详解。

全书共7章，由浅入深、由易到难地介绍了各类例题，主要包括枚举与模拟、搜索与查找、思维与贪心、简单数论、字符串算法、动态规划、数据结构等。每一类例题的讲解，不只是简单地给出解析及参考代码，而是注重通过提供不同的解题方案训练读者的计算思维、编程思维，不仅有助于读者提高解题能力和竞赛水平，还有助于形成自己的编程思想，实现“以赛促学”的学习目标。

本书不仅适合作为蓝桥杯软件类大赛C/C++语言组的备赛用书，还适合作为本科生和研究生相关编程语言课程的教材或参考资料。

写在前面的话

请坚信，你曾艰苦奋斗的日日夜夜，绝不会允许你在比赛中充当 “分母”。

“或许我们可以为蓝桥杯出版一本教材！”

这是我们蓝桥杯软件类大赛教研团队在某次工作会议时的结束语，也是本书的起点。

在我们团队过去十几年的发展过程中，无论是教育培训，还是程序开发，我们都得心应手。但对于出版教材这事，我们却是 “零经验”。

“出书是一件艰难的事情，因为我们要面对的是一种全新的思维模式。” 团队负责人笑着说道，“这也必然是个巨大的挑战！”

截至 2022 年，蓝桥杯软件类大赛（实质上也是算法竞赛）已成为参赛人数最多的大学计算机编程竞赛：1600 余所高校参赛，累计参赛人数超过 60 万人。大赛对大学生综合评测、奖学金评定、升学考研、就业都有一定助益，但是，能用于大赛辅导的教材却寥寥无几，这也是我们出书的主要原因。

怎样才能写好一本书，就成了我们日思夜想的问题。

经过多方几轮的讨论，我们决定从参赛选手的视角，以训练计算思维和逻辑思维为出发点，采用逐级递进的方式细致地讲解真题，带领读者由浅入深地掌握蓝桥杯软件类大赛的核心考点和解题技巧。同时，为了降低读者在阅读过程中的枯燥感，我们几乎在每道真题的讲解中都添加了代码注释、示意图等有助于更好地学习与掌握算法知识、提高解题能力的 “助推器”；考虑到难题的解读门槛，我们特地补充了难题的 “低分” 解法（可通过部分测试数据的解题方法），例如只能拿 20% 分数、40% 分数的解法，以保证具有不同编程水平的人能各取所需、各有所得。

“我们能做的就这么多了，接下来看他们的吧！” 在编写工作的收尾期，我们这些创作者都不由自主地发出感叹。

由于参赛人数众多，蓝桥杯软件类大赛堪称 “严酷”。我们所能提供的支持已尽在书中，如果你们想在算法竞赛的 “星辰大海” 中乘风破浪，还要靠自我驱动、奋勇前行。接下来就看你们的了！

下面就先来了解蓝桥杯软件类大赛的相关事宜，以及如何使用本书来学习和备赛。

关于赛制

蓝桥杯软件类大赛可分为省赛和总决赛两级。

1. 省赛

每个组别分别设立一、二、三等奖，原则上各奖项的比例为 10%、20%、30%。获奖比例仅作为参考，组委会专家组将根据赛题难易程度及整体答题情况，制定获奖最低分数线，未达到获奖最低分数线者不得奖。

2. 国赛

每个组别分别设立一、二、三等奖及优秀奖。其中，一等奖不高于 5%，二等奖占 20%，三等奖不低于 35%，优秀奖不超过 40%，零分卷不得奖。

关于题型

每场蓝桥杯软件类大赛设有 10 道题目，总分为 150 分，竞赛时长为 4 小时。对于同一道题目，参赛选手可多次提交答案，评分时以最后一次提交的答案为准。

参赛选手必须通过浏览器方式提交自己的答案，在其他位置作答或以其他方式提交的答案无效。试题设有 “结果填空” 和 “编程大题” 两种题型。

1. 结果填空

要求参赛选手根据题目描述直接填写结果。求解方式不限，不要求源代码。参赛选手将答案直接通过浏览器提交即可，不要书写多余的内容。

2. 编程大题

要求参赛选手设计的程序对于给定的输入能给出正确的输出结果。参赛选手所编写的程序只有在能运行出正确结果的情况下才有机会得分。

关于本书的学习

本书适合具有一定编程基础，对蓝桥杯软件类大赛有浓厚兴趣的算法竞赛爱好者及各类高等院校计算机专业的师生阅读。

如前所述，本书在编写时考虑了不同编程水平读者的学习特点和竞赛需求，下面就详细介绍本书所设置的章节结构，以便读者在了解我们的编写思路之后，能更好地应用本书来进行学习和备赛。

本书对于大部分试题及其解答过程的写作结构，主要有题目信息、懒人速读、题目分析、拓展提高这 4 个栏目，其具体构成如下图所示。

（1）题目信息。主要提供两类信息，一类是基本的 “竞赛信息”，例如该试题的所属年份、组别、难度级别等；另一类是完整的试题信息，包括问题描述，输入、输出格式，输入、输出样例，样例说明，以及数据规模等。

（2）懒人速读。由于部分真题的描述显得烦琐，不利于读者快速把握题目的核心考点，我们通过此栏目带领读者高效地解读题目、准确地领会考查要点，有利于读者节省阅读与理解题意的时间，并能够快速地投入到解题的思考过程中。

（3）题目分析。从参赛选手的角度一步一步引出思考与解决问题的方式方法，此栏目下设置了两个重要模块：一是核心考点，用以给出题目主要考查的知识点；二是参考代码，用以给出试题对应的参考答案，而且大部分 “参考代码” 中都提供了贴心的注释。

（4）拓展提高。在原题目的基础上引导读者进行更深入的探讨，以拓展思路，掌握更多的解题技巧。

蓝桥杯大赛官方资源的获取

蓝桥云课是蓝桥杯大赛的官方资源平台。对于本书所提供的题目，读者都可以在蓝桥云课上进行模拟训练。蓝桥云课内嵌了在线评测系统，能进行自动判题，并返回有关正误的提示，从而帮助读者完全自主地高效学习编程。蓝桥云课所提供资源的相关链接如下。

链接 1：蓝桥杯大赛官方网站，dasai.lanqiao.cn。

链接 2：Python 3 自带标准库，https://docs.python.org/3/library/index.html。

链接 3：蓝桥杯大赛历届真题，https://www.lanqiao.cn/courses/2786。

链接 4：蓝桥杯官网题库，www.lanqiao.cn/problems，简称 lanqiaoOJ。

需要特别指出的是，蓝桥云课内嵌的在线评测系统提供了海量的算法竞赛经典例题及蓝桥杯软件类大赛的历年真题，真题所使用的评测数据与大赛评分时使用的测试数据一致。如果你参加了比赛，那么赛后在蓝桥云课的 “链接 3” 与 “链接 4” 中提交源代码，可得到最接近于实际成绩的结果。如果你正在备赛，那么可以在蓝桥云课中找到完整的算法学习路线与训练体系，能在很大程度上帮助你取得好成绩。

此外，蓝桥云课的社区资源相当丰富，不仅有专为蓝桥杯大赛展开的话题，还涵盖了计算机相关岗位求职就业的内容。

致谢

写作是一个痛苦并快乐的过程。在这个过程中，我们得到了蓝桥杯大赛负责人李艳萍老师的大力支持与指导；得到了华东理工大学程序设计竞赛主教练罗勇军老师提供的宝贵意见与建议；得到了蓝桥杯大赛参赛选手、算法竞赛爱好者刘子俊、常凤迪、刘会智、张晖的赞同与认可；得到了人民邮电出版社各位编辑给予的鼓励与帮助。在此深表感谢！

由于我们时间仓促、水平有限，书中难免存在错误或不当之处，恳请广大读者及时指正，以便 “去伪存真”。若有任何关于本书的意见或建议，欢迎随时与我们沟通联系，我们教研团队的邮箱是 LQbook@lanqiao.cn，出版社的联系邮箱是 wangxudan@ptpress.com.cn。

期待您的反馈！

编　者

2022 年 8 月

资源与支持

本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。

您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e60135”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。

配套资源

本书提供如下资源：

● 本书配套源代码；

● 本书配套PPT课件。

要获得以上配套资源，请在异步社区本书页面中点击，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。

如果您是教师，希望获得教学配套资源，请在社区本书页面中直接联系本书的责任编辑。

提交勘误

作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。

当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。

扫码关注本书

扫描下方二维码，您将会在异步社区微信服务号中看到本书信息及相关的服务提示。

与我们联系

我们的联系邮箱是contact@epubit.com.cn。

如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。

如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/ contribute即可）。

如果您是学校、培训机构或企业用户，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。

如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。

关于异步社区和异步图书

“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。

“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近40年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。

异步社区

微信服务号

第1章　枚举与模拟

1.1　卡片(★)

题目信息

2021 年省赛 - 填空题

● C/C++ A组第1题；C/C++ B组第2题

● Java B组第2题；Java C组第3题

● Python 组第1题

【问题描述】

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

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

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

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

现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少?

提示：建议使用计算机编程解决问题。

【答案提交】

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

懒人速读

小蓝有很多数字卡片，每张卡片上都必然刻有 中的一个数字。

卡片可以用来拼凑数字，假设小蓝拥有刻有数字 和数字 的卡片各一张，那么他可以利用这两张卡片拼凑出数字 这4个正整数。

现给定刻有数字 的卡片各 张，小蓝将利用这些卡片从 1 开始连续拼凑数字，请问他最大能拼到数字几（注意：每张卡片只能利用一次）?

题目分析

核心考点

● 枚举

● 模拟

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

定义 表示刻有数字的卡片张数。那么按照题目的意思，初始化 ，参考代码1-1-1如下。

参考代码1-1-1

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

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

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

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

参考代码1-1-2

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

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

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

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

参考代码1-1-3

  1   #include<bits/stdc++.h>
  2   using namespace std;
  3   int cnt[10];
  4   bool check(int x){  // x 表示当前枚举的数
  5       while(x){
  6           int b = x % 10; // 获取十进制下的每个数位
  7           if(b == 1) {
  8               if(cnt[1] == 0) return false;
  9               cnt[1] -- ;
 10           }
 11           x /= 10; // 将十位变为个位
 12       }
 13       return true;
 14   }
 15   signed main(){
 16       for(int i = 0 ; i <= 9 ; i ++) cnt[i] = 2021;
 17       for(int i = 1 ; ; i ++){
 18           if(!check(i)) return cout << i - 1 << '\n' , 0;
 19       }
 20       return 0;
 21   }

最终答案为3181。

1.2　回文日期(★)

题目信息

2020 年省赛 - 填空题

● C/C++ A组第7题；C/C++ B组第7题

● Java A组第7题

【问题描述】

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

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

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

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

【输入格式】

输入包含一个八位整数 ，表示日期。

对于所有评测用例，，保证是一个合法日期的8位数表示。

【输出格式】

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

【样例输入】

20200202

【样例输出】

20211202

21211212

【答案提交】

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

懒人速读

给定（输入）一个 位数的日期，请找出（输出）该日期之后的下一个回文日期以及下一个 ABABBABA 型回文日期。

若给定的日期为 20200202，则会有下列结果。

● 下一个回文日期为20211202。

● 下一个 ABABBABA 型回文日期为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。

对于本题，若用 、、、、、、、 分别存储每一位，则一个回文日期须满足:

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

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

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

参考代码1-2-1

 1  int date = 20050511;
 2  string s = to_string(date);  将整型转换为字符串, s = "20050511"
 3  
 4  // 判断回文日期
 5  bool check1(int date){
 6      string s = to_string(date);
 7      if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true;
 8      return false;
 9  }
10 // 判断 ABABBABA 型回文日期
11 bool check2(int date){
12     string s = to_string(date);
13     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;
14     return false;
15 }

2．如何枚举日期

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

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

参考代码1-2-2

  1   int month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
  2   bool check(int date){
  3       string s = to_string(date);
  4       // stoi -> 将字符串转为整型
  5       int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2));
  6       if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;
  7       else month[2] = 28;
  8       if(m < 1 || m > 12 || d < 1 || d > month[m]) return false;
  9       return true;
 10   }
 11   for(int i = date + 1 ; ; i ++){
 12       if(!check(i)) continue ;
 13       ...
 14   }

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

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

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

参考代码1-2-3

  1  int month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
  2  ...
  3  int date = 20050511;
  4  int y = date / 10000 , m = date / 100 % 100 , d = date % 100;
  5  // date = y * 10000 + m * 100 + d;
  6  
  7  for(int i = y ; ; i ++){
  8      if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29; // 闰年2月有29天
  9      else month[2] = 28;
 10      int j = (i == y) ? m : 1; // 如果是 i = y，则月份从 m 开始枚举，否则 m 从 1 开始枚举
 11      for(; j <= 12 ; j ++){
 12          int k = (i == y && j == m) ? d : 1;  // 如果 i = y 并且 j = m，则日从 d 开始枚举，否则 d 从 1 开始枚举
 13          for(; k <= month[j] ; k ++){
 14              // date = i * 10000 + j * 100 + k
 15              ...
 16          }
 17      }
 18  }

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

参考代码1-2-4　【枚举合法日期】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
 4 int date, ans1, ans2;
 5 // 判断日期是否为回文
 6 bool check1(int date){
 7     string s = to_string(date);
 8     if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true;
 9     return false;
10 }
11 // 判断日期是否满足 ABABBABA 型回文
12 bool check2(int date)
13 {
14     string s = to_string(date);
15     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;
16     return false;
17 }
18 signed main()
19 {
20     cin >> date;
21     int y = date / 10000, m = date / 100 % 100, d = date % 100;
22     for(int i = y ; ; i ++) {
23         if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29;
24         else month[2] = 28;
25         int j = (i == y) ? m : 1;
26         for(; j <= 12 ; j ++) {
27             int k = (i == y && j == m) ? d + 1 : 1;
28             for(; k <= month[j] ; k ++) {
29                 int date = i * 10000 + j * 100 + k;
30                 if(check1(date) && ans1 == 0) ans1 = date;
31                 if(check2(date)) return cout << ans1 << '\n' << date << '\n', 0; // 当找到了 ABABBABA 型回文日期时，结束程序
32             }
33         }
34     }
35     return 0;
36 }

参考代码1-2-5　【枚举年份】

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

1.3　赢球票(★)

题目信息

2016 年国赛-程序设计题

● C/C++ C组第4题

● Java C组第4题

【问题描述】

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

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

你可以从任意一张卡片开始顺时针数数:

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

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

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

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

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

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

【输入格式】

第一行一个整数，表示卡片数目。

第二行 个整数，表示顺时针排列的卡片。

【输出格式】

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

【样例输入】

3

1 2 3

【样例输出】

1

懒人速读

给定 张卡片，卡片上分别写着数字 。

现将这 张卡片围成一个圈。

我们可以从圈上任意一个位置开始顺时针数数：。

若当前数到的数字和卡片上的数字相同，则将卡片取走，并从下一张卡片所在位置重新数数：。

问我们取走的卡片上的数字之和最大可以是多少?

举例说明

若 ，则从第一张卡片所在位置开始数数的过程如下。

题目分析

核心考点

● 枚举

● 拆环成链

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

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

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

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

问题4．游戏什么时候会结束呢?

下面依次对这4个问题进行分析。

对于问题1：

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

对于问题2：

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

对于问题3：

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

对于问题4：

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

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

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

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

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

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

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

● 判断游戏是否结束。

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

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

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

参考代码1-3　【赢球票】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   const int N = 1e2 + 10;
 4   int n, a[N], flag[N];
 5   signed main(){
 6       cin >> n;
 7       for(int i = 1 ; i <= n ; i ++) cin >> a[i];
 8       int ans = 0; // ans 表示答案
 9       for(int i = 1 ; i <= n ; i ++){ // i 表示枚举的起点
10           // 将所有卡片的 flag 初始化为 0
11           for(int j = 1 ; j <= n ; j ++) flag[j] = 0; // flag[j] = 1 表示卡片被取走，反之没被取走
12           int num = 1 , pos = i , sum = 0, cnt = 0; // num 表示数的数的值，pos 表示当前位置，sum 表示以 i 为起点数数所能取走的卡片的和，cnt 表示拿走的卡片的数量
13   
14           // 开始模拟
15           while(1){
16               // 判断游戏是否结束
17               if(cnt == n || num > n) break; // 如果取走了所有卡片，或者数的数大于 n（不可能再取走卡片了），则游戏结束
18               // 判断当前位置的卡片是否被取走
19               if(flag[pos] == 1) { // 如果该卡片已被取走，则移动到下一个位置
20                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
21                   if(pos == n) pos = 1;
22                   else pos ++;
23                   continue ;
24               }
25               // 数的数和当前位置卡片的值相同时取走该卡片（a[pos] 表示第pos张卡片的值）
26               if(num == a[pos]){
27                   sum += a[pos]; // 取走卡片的和 + a[pos]
28                   cnt ++;        // 取走的卡片个数 + 1
29                   num = 1;       // 取走卡片后要重新数数
30                   flag[pos] = 1; // 取走卡片后该卡片对应的 flag 置为 1
31                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
32                   if(pos == n) pos = 1;
33                   else pos ++;
34               } else {
35                   // 数的数和当前位置卡片的值不相同时
36                   num ++ ; // 数的数的值 + 1
37                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
38                   if(pos == n) pos = 1;
39                   else pos ++;
40               }
41           }
42           // 模拟结束，判断该模拟结果是否可以作为答案
43           if(sum > ans) ans = sum;
44       }
45       cout << ans << '\n';
46       return 0;
47   }

1.4　既约分数(★)

题目信息

2020 年省赛-填空题

● C/C++ A组第2题；C/C++ B组第2题

● Java A组第2题

【问题描述】

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

例如 ， 都是既约分数。

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

【答案提交】

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

题目分析

核心考点

● gcd（最大公约数）

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

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

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

参考代码1-4-1　【复杂度为】

 1   int gcd(int a , int b){
 2       if(b == 0) return a;
 3       return gcd(b, a % b);
 4   }

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

参考代码1-4-2　【复杂度为】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   signed main()
 4   {
 5       int ans = 0;
 6       for(int i = 1 ; i <= 2020 ; i ++){
 7           for(int j = 1 ; j <= 2020 ; j ++){
 8               if(＿gcd(i , j) == 1) ans ++ ;
 9           }
10       }
11       cout << ans << '\n';
12       return 0;
13   }

最终答案为2481215。

拓展提高

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

若两个数 （）的最大公约数为 1，则 是一个既约分数， 也是一个既约分数。所以我们可以从 枚举 ，从 枚举 ，这样得到的 就满足 。接着判断 的最大公约数是否为 1（若为 1，则 是既约分数）。

若用 cnt 来统计有多少对 满足 且 的最大公约数为 1，则答案为 （乘2是因为 的倒数 也是既约分数，减 1 是因为 的倒数还是 ，重复计算了一次，要减掉，见下图）。

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

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

核心考点

● 唯一分解定理

● 欧拉函数

● 欧拉筛

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

由欧拉函数的定义可知满足 ，且 最大公约数为 的 的个数就为 。

我们要求的是 内满足 且 最大公约数为 1 的 的个数，即 内所有数的欧拉函数的和，即 。

欧拉函数的通项公式：

其中 为 的所有不重复质因子。

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

提示

唯一分解定理就是对于一个大于 的整数 ，要么其本身是个质数，要么能被分解为有限个质数的乘积。

若用数学公式表示，则 ， 表示质数（即 的质因子）， 表示 的个数。

例如， 就可以表示为 ，它的质因子有 、。其中质因子 的个数为 ，质因子 的个数为 。

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

参考代码1-4-3

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

再根据欧拉函数的通项公式 写出代码。

参考代码1-4-4

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

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

参考代码1-4-5　【时间复杂度为 】

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

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

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

参考代码1-4-6　【时间复杂度为 】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   int n , phi[2021] , prime[2021];
 4   signed main(){
 5       // 欧拉筛
 6       phi[1] = 1;
 7       for(int i = 2 ; i <= 2020 ; i ++){
 8           if(!prime[i]) prime[++ n] = i, phi[i] = i - 1;
 9           for(int j = 1 ; j <= n && i * prime[j] <= 2020 ; j ++){
10               prime[prime[j] * i] = 1;
11               if(i % prime[j] == 0){
12                   phi[i * prime[j]] = phi[i] * prime[j];
13                   break ;
14               }
15               phi[i * prime[j]] = phi[i] * (prime[j] - 1);
16           }
17       }
18       int cnt = 0;
19       for(int i = 1 ; i <= 2020 ; i ++) cnt += phi[i];
20       cout << 2 * cnt - 1 << '\n';
21       return 0;
22   }

1.5　数的分解(★)

题目信息

2019 年省赛-填空题

● C/C++ B组第4题

● Java B组第4题

【问题描述】

把 分解成 个各不相同的正整数之和，并且要求每个正整数都不包含数字 和 ，一共有多少种不同的分解方法?

注意交换 个整数的顺序被视为同一种方法，例如 和 被视为同一种。

【答案提交】

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

题目分析

核心考点

● 枚举

本题可以用枚举来解决。不过在此之前，先来分析以下两个问题。

问题1．如何判断一个整数是否包含 2 或 4?

问题2． 如何解决重复情况?

对于问题 1，只要取出该整数在十进制下的每一位的数字，并判断这些数字是否等于 2 或 4 即可，具体代码可见参考代码1-5-1第行。

对于问题 2，已知一个方案是由3个数组成（第1个数，第2个数，第3个数），这3个数互不相同且和为 2019。假设这3个数分别为，那么它们可以构造出 、、、、、 6 种方案。根据题意，这 6 种方案只能视为一种，所以可以先求出满足条件的所有方案数，再将总方案数除 6 即可。

分析完上述两个问题，就能轻松写出以下代码。

参考代码1-5-1　【复杂度为，是check()函数的复杂度】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   // 如果 x 包含 2 或 4 返回 false，否则返回 true
 4   bool check(int x){
 5       while(x){
 6           if(x % 10 == 2 || x % 10 == 4) return false;
 7           x /= 10;
 8       }
 9       return true;
10   }
11   signed main(){
12       int ans = 0;
13       for(int i = 1 ; i <= 2019 ; i ++)
14           for(int j = 1 ; j <= 2019 ; j ++)
15               for(int k = 1 ; k <= 2019 ; k ++)
16                   // i, j, k 互不相同
17                   // i + j + k = 2019
18                   // i, j, k 都不包含 2 和 4
19                   if(i != j && i != k && j != k && i + j + k == 2019 && check(i) && check(j) && check(k)){
20                       ans ++ ;
21                   }
22       ans /= 6;
23       return 0;
24   }

虽然能轻松写出以上代码，但本题的规模为 2019，代码要运行很久才可得出答案。因此，我们需要对复杂度进行优化。怎么优化呢?可以考虑从以下3点入手。

(1) 添加约束条件。对于任意一个方案，只有当该方案中的第1个数小于第2个数、第2个数小于第3个数时才视该方案为合法方案，如下图所示。这样不仅能保证任意3个整数只能构造出一个方案（符合题意），而且可以减少枚举次数（第2个数从第1个数+1开始枚举，第3个数从第2个数+1开始枚举）。

参考代码1-5-2

 1      for(int i = 1 ; i <= 2019 ; i ++)
 2          for(int j = i + 1 ; j <= 2019 ; j ++) // i < j，所以 j 从 i + 1 开始枚举
 3              for(int k = j + 1 ; k <= 2019 ; k ++) // j < k，所以 k 从 j + 1 开始枚举
 4                  if(i + j + k == 2019 && check(i) && check(j) && check(k))
 5                      ans ++ ;

不过这样的复杂度还是 ，并没有起到很好的效果。

(2) 减少枚举变量。对于任意一个方案，它的3个整数的和都为 2019，即只要知道了第1个数和第2个数的值，就能确定第3个数的值（第3个数第1个数− 第2个数）。这样，就可以省去对第3个数的枚举，复杂度降至 。

参考代码1-5-3

 1      for(int i = 1 ; i <= 2019 ; i ++)
 2          for(int j = i + 1 ; j < 2019 - i - j ; j ++) // i < j < 2019 - i - j
 3              if(check(i) && check(j) && check(2019 - i - j))
 4                  ans ++;

(3) 提前检查、标记所有数。除了上述两步优化，还可以在枚举开始前对不包含 2 和 4 的整数进行标记，方法是定义数组，如果整数不包含 2 和 4，则 ，否则 。这样在枚举的过程中，就可以通过 数组以 O(1) 的复杂度判断一个数是否包含 2 和 4，复杂度降至 ，具体代码见参考代码1-5-4第行。最终答案为40785。

参考代码1-5-4　【时间复杂度为 】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   // 如果 x 包含 2 或 4 返回 false，否则返回 true
 4   bool check(int x){
 5       while(x){
 6           if(x % 10 == 2 || x % 10 == 4) return false;
 7           x /= 10;
 8       }
 9       return true;
10   }
11   bool flag[2020];
12   signed main(){
13       int ans = 0;
14       for(int i = 1 ; i <= 2019 ; i ++) if(check(i)) flag[i] = 1; // 在枚举前判断一个数是否包含 2 和 4，避免在枚举过程中判断
15       for(int i = 1 ; i <= 2019 ; i ++)
16           for(int j = i + 1 ; j < 2019 - i - j ; j ++) // i < j < 2019 - i - j
17               if(flag[i] && flag[j] && flag[2019 - i - j]) // 通过 flag 判断，复杂度 O(1)
18                   ans ++;
19       cout << ans << '\n';
20       return 0;
21   }

拓展提高

如果觉得 的复杂度还是太高，那么再来进一步降低复杂度吧！

核心考点

● （多维）数位 dp

本题可以对3个数同时进行数位 dp。不过在开始 dp 之前，需要先考虑维护的信息。

假设现在有3个整数 ，要使它们能构成一组合法方案，按照题意须满足以下条件。

(1) 互不相等。

(2) 。

(3) 都不包含 2 或 4。

(4) 、、、、、都属于一种方法。

要如何处理这些条件呢?

● 对于条件 1、条件4，可以采用前文优化 方法中的第1点，即添加约束条件。这样不仅能保证 互不相等，也能保证只能构造出一种方法。我们可以在数位 dp 中添加两个信息 ，分别维护是否小于、是否小于（ok1 = 1 表示 ，ok2 = 1 表示 ）。

● 对于条件 2，可以在数位 dp 中添加一个信息 sum，用来记录的和。

● 对于条件 3，由于数位 dp 是在数位上进行操作的，所以可以在操作时直接判断是否包含 2 或 4。

此外，的范围是 。为了防止在 dp 的过程中出现等于 0 的情况，我们可以添加一个信息 ok3 ，来判断是否大于 0（ok3 = 1 表示）。

如此，当 时其含义就为，且的和为 2019。

有了这些信息，就可以定义 ，其中： len 表示当前计算到了十进制下的第 len 位，limit1 表示 当前数位的上限是否受到限制，limit2 表示 当前数位的上限是否受到限制，limit3 表示 当前数位的上限是否受到限制。然后，应用记忆化搜索即可得出答案。具体代码见参考代码1-5-5，该代码可以处理数位长度规模为 的情况。

参考代码1-5-5　【时间复杂度为 】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dp[5][2][2][2][2][2][2][2020] , num[5] , p[5];
 4 int dfs(int len , bool limit1 , bool limit2 , bool limit3 , bool ok1 , bool ok2 , bool ok3, int sum){
 5     if(!len) return sum == 2019 && ok1 && ok2 && ok3 ;
 6     if(~dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum]) return dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum];
 7     int res = 0;
 8     // num[4] = 2, num[3] = 0 , num[2] = 1 , num[1] = 9
 9     int up1 = limit1 ? num[len] : 9; // i 当前数位是否达到上限
10     int up2 = limit2 ? num[len] : 9; // j 当前数位是否达到上限
11     int up3 = limit3 ? num[len] : 9; // k 当前数位是否达到上限
12     for(int i = 0 ; i <= up1 ; i ++){
13         if(i == 2 || i == 4) continue ;  // 如果 i 当前数位的值为 2 或 4 则跳过这种情况
14         int d1 = ok1 ? 0 : i;             // 如果 j 还没有大于 i，为保证 j > i，当前数位上的数字需要从 i 开始枚举
15         for(int j = d1 ; j <= up2 ; j ++){
16             if(j == 2 || j == 4) continue ; // 如果 j 当前数位的值为 2 或 4 则跳过这种情况
17             int d2 = ok2 ? 0 : j;            // 如果 k 还没有大于 j，为保证 k > j，当前数位上的数字需要从 j 开始枚举
18             for(int k = d2 ; k <= up3 ; k ++){
19                 if(k == 2 || k == 4) continue ; // 如果k当前数位的值为2或4则跳过这种情况
20                 // 如果 i, j, k 的和超过 2019 则跳过这种情况
21                 if(sum + i * p[len - 1] + j * p[len - 1] + k * p[len - 1] > 2019) break;
22                 res += dfs(len - 1 , limit1 && i == up1 , limit2 && j == up2 , limit3 && k == up3 ,
23                            // 只要存在一个数位，在该数位下 j 的值大于 i 的值，ok1 就等于 1
24                            // 只要存在一个数位，在该数位下 k 的值大于 j 的值，ok2 就等于 1
25                            // 只要存在一个数位，在该数位下 i 的值大于 0，ok3 就等于 1
26                            ok1 || i < j , ok2 || j < k , ok3 || i,
27                            sum + i * p[len - 1] + j * p[len - 1] + k * p[len - 1]);
28             }
29         }
30     }
31     return dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum] = res;
32 }
33 int solve(int x){
34     memset(dp , -1 , sizeof(dp));
35     int len = 0;
36     while(x){  // 取出 x（2019）的每一位数字存储在 num 中，进行数位 dp
37         num[++ len] = x % 10;
38         x /= 10;
39     }
40     // 传入的 x = 2019，则 num[4] = 2, num[3] = 0, num[2] = 1, num[1] = 9
41     return dfs(len, 1, 1, 1, 0, 0, 0, 0);
42 }
43 signed main(){
44     // p[i] 表示 10 的 i 次方，即 p[1] = 10^1 = 10 , p[2] = 10^2 = 100,...]
45     p[0] = 1;
46     for(int i = 1 ; i <= 4 ; i ++) p[i] = p[i - 1] * 10;
47     cout << solve(2019) << '\n';
48     return 0;
49 }

1.6　巩固与练习

读者服务：

微信扫码关注【异步社区】微信公众号，回复“e60135”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。