版权信息
书名：程序设计竞赛专题挑战教程
ISBN：978-7-115-60150-6
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
版 权
著 罗勇军 杨培林
责任编辑 李 莎
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e60150”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
内容提要
本书面向蓝桥杯全国软件和信息技术专业人才大赛的软件类赛项（以下简称蓝桥杯软件类大赛），从数据结构和算法的维度帮助广大读者训练编程思维和计算思维，掌握编程方法和解题技巧。
本书共10章，第1章主要介绍了蓝桥杯软件类大赛的基本情况，归类汇总了其涉及的知识点（包括算法知识点），详细介绍了其在线评测系统以说明评分情况。第2~10章则由浅入深、由易到难地介绍了各类知识点，包括手算题和杂题、基础数据结构、基本算法、搜索、高级数据结构、动态规划、数学、字符串、图论等，对于每一类知识点都简明扼要地进行说明，并以真题作为例题进行细致讲解，以更好地帮助读者实现学用结合的学习效果。需要特别说明的是，本书例题的代码部分，分别由C++、Python、Java三种语言来实现（书中仅提供以C++、Python语言编写的代码，以Java语言编写的代码可从本书的配套数字资源中获取）。
本书不仅适合作为蓝桥杯软件类大赛参赛者的备赛用书，还适用于备赛其他编程或算法类大赛（如全国青少年信息学奥林匹克竞赛NOI、国际大学生程序设计竞赛ICPC、中国大学生程序设计竞赛CCPC、中国高校计算机大赛−团体程序设计天梯赛GPLT等）。此外，本书还可作为本科生和研究生的相关算法课程的教材或参考资料。
写在前面的话
欢迎开始“蓝桥杯软件类大赛”的学习与备赛！
蓝桥杯软件类大赛实质上是算法竞赛，本书定位的读者是初学者，他有这样的初始能力：
（1）刚学过编程语言，C/C++、Java、Python这三种语言任何一个都行；
（2）具备了基本的编码能力，不需要再问语法问题；
（3）编码仍然不熟练；不懂算法，遇到较难的问题没有思路。
他有这样的学习目标：
（1）深入学习算法知识，提高自己的计算思维能力；
（2）做有难度的编码，提高编码能力；
（3）参加蓝桥杯软件类大赛并获奖。
如果你符合上述初学者画像，那么本书就是你高效实现目标的“脚手架”。
下面就来了解算法竞赛的相关事宜，以及如何高效地备赛。
正确看待算法竞赛
在大学学习过程中，既有面向学位要求的专业课程，又有面向非学位要求的竞赛、创新项目、课题等学习活动。虽然参加竞赛活动是课余的、非强制性的，但是竞赛活动能有力地帮助参赛者强化巩固所学的专业知识，提高思维和动手能力，提升专业水平。不少竞赛活动的含金量也足以证明学生的专业能力，从而使学生在保研、找工作时获得优势。
在权威的全国普通高等院校的学科竞赛排行榜上，蓝桥杯大赛名列其中，是广受欢迎的信息类专业竞赛。其中，蓝桥杯软件类大赛目前已成为参赛人数最多的大学计算机编程竞赛，获得了高校和就业单位的广泛认可，其奖牌是大学生计算机编程能力的一个有力证明。
通过本书的学习，读者不仅有能力获得蓝桥杯软件类大赛的奖项，也有能力在其他算法竞赛中获奖，而且将来在找工作面试时遇到算法题也不用紧张。
从就业需求看，算法竞赛可以说是十分实用的，甚至是带些许“功利色彩”的竞赛。其他类别的一些竞赛活动也能有助于参赛者提高思维能力或锻炼动手能力，但不一定能将这些能力的提升直接体现到就业竞争力上，而通过算法竞赛培养出的计算思维能力、编程能力，则能直接服务于计算机专业工作中，因而算法竞赛的获奖者是企业非常欢迎的人才。常看到这样的新闻：有人在中学时参加了全国青少年信息学奥林匹克竞赛，上大学后从大一开始就能找到公司实习，并且能力超出一般的大学毕业生。不少非计算机专业的学生，在算法竞赛获奖之后，也能从事计算机程序员的工作，并且能力很强。更何况计算机专业的学生，他们在学习算法竞赛后则如虎添翼，能力上升一个大台阶！
算法竞赛具体培养哪些能力？从就业角度看，一名出色的程序员需要经过以下几方面的锻炼。
1．编写大量代码
编程不是纸上谈兵，而是动手写出合格并高效的代码。在编写代码上进行大量的训练，是成为杰出程序员必下的功夫。
2．学习各种算法知识
算法是计算机程序的灵魂，每个计算机问题都需要采用适当的算法来解决，例如分析算法的时间复杂度、空间复杂度，从而通过代码来高效地完成任务。竞赛主要考核如何根据具体情况灵活地应用算法，这能很好地促进参赛者对算法的理解与掌握。
3．培养计算思维和逻辑思维
一道竞赛题往往需要参赛者综合运用多种知识与方法，例如数据结构、算法知识、数学方法、流程和逻辑等，这是计算思维和逻辑思维能力的体现。
4．掌握多种编程语言
对于蓝桥杯软件类大赛而言，其用到的编程语言就有C/C++、Java、Python。其中，C/C++因运行效率高、拥有丰富的STL函数库，最受参赛者欢迎。Java和Python也很常用，特别是Python，其上升势头越来越明显。当然，对于这几种编程语言，就业市场上都有大量的相应岗位需求，参赛者掌握得好，就业要容易得多。
如何高效备赛
刚接触蓝桥杯软件类大赛的参赛者往往有这样的困惑：大赛似乎很难、很花时间，不仅难以入门，而且学习成本很高，往往需要半年以上，甚至一年、两年的勤奋学习，才能获得较好的成绩。
本书正是为了解除这样的困惑而编写的：通过本书的学习，你能从一名算法竞赛的“小白”，开始成长为熟悉算法知识、构建起算法思维、拥有高效编码能力的计算机编程人才。
好学上进的你肯定有这样的期望：我想得奖，尽快得奖！
这本书是得奖的捷径吗？答案是确定的！然而，“捷径”往往是“艰难”的代名词。“捷径”并不一定意味着省力，正如爬山的捷径往往更陡峭、更令人费力一样。在算法竞赛的学习这件事上，“捷径”意味着要付出更大的努力，要进行高强度的学习。本书之所以能成为得奖的“捷径”，是因为所提供的知识点更为集中、讲解更清晰、题目设置更有针对性。是否能走通这个“捷径”，取决于你愿意付出多少时间和精力。
学习算法竞赛，请注意以下几个重要问题。
1．刷题
在面向算法竞赛的所有学习方法中，最重要的一种方法是“刷题”。也就是大量做题，在做题时进行建模训练和编码练习。只读理论、只看书，而不做题，学习效果只会略大于零，能力得不到提高，肯定不能得奖。《天龙八部》里的王语嫣，是位武学理论大师，但手无缚鸡之力，打不过一个没学过任何武功的人。要成为真正的编程高手，只能通过大量做题，才能真正理解算法知识、提高编程能力，并在竞赛中发挥出水平。
那么，“刷”多少题合适？本书介绍了算法竞赛中处于初级和中级层次的知识点，读者可每个知识点做10～20题，总共要做600～1000题，多多益善！
初学者问：“啊，要做这么多题吗？太累了！”
我的回答：“没其他办法，这是算法竞赛的必由之路。”
2．速度
参加算法竞赛，编程速度极为重要。蓝桥杯软件类大赛要求在4小时内完成10道题，时间非常紧张。因而，编程速度是所获奖项级别的重要影响因素。
如何提高编程速度？读题要快！对于每道题，都需要建模后才能进行编程。在竞赛时能快速读完题目并思考出合适的算法，是需要经过大量做题训练的。训练会提高大脑的兴奋度，用最快的速度理解题目并建立计算机编程模型。
此外，为加快做题速度，还需要注意以下3点。
（1）熟练掌握集成编译环境。
（2）减少调试，最好是写完程序后，争取一次能通过测试样例。为了减少调试，尽量使用不容易出错的方法，例如少用指针、多使用静态数组、将逻辑功能模块化等。注意，不要使用动态调试方法，不要用单步跟踪、断点等调试工具。因为这样会很慢，况且算法竞赛的代码不长，用不着这样做。如果需要查看中间的运行结果，就在代码中的关键地方打印出调试信息。
（3）使用库函数。如果题目涉及比较复杂的数据处理，或者像sort()这样需要灵活排序的函数，用库函数可以大大地减少编码量，并减少错误的发生。注意积累C++、Java、Python编程语言的库函数。
3．模板
模板是某些数据结构、算法的标准代码，可谓计算机科学发展过程中众多高手提炼出的“精华”。
初学者问：我想速成，来不及做很多题，不过我可以多准备一些模板，竞赛的时候套一套模板，是不是也能获奖？
我的回答：模板有用且需要掌握，但是，在赛场上模板的作用有限。
模板很有用，例如并查集模板、快速幂模板、埃氏筛模板等，需要参赛者牢记并熟练应用。学习经典算法时，往往也需要整理模板并要多次地学习和使用。有必要强调的是，对于模板中的代码，参赛者得真正理解并多次使用过，才能在做题时快速地应用于编程。
有的算法竞赛可以带纸质资料进场，相当于开卷考试，例如ICPC、CCPC，有不少参赛者带了打印出来的厚厚一沓代码资料和各种书籍进场竞赛。但是，蓝桥杯软件类大赛采用的是闭卷形式，禁止带任何资料进场，因而参赛者要完全靠脑力，模板要靠“背”！这就增加了一定的难度。
不过，把模板带到赛场上用处大吗？答案是“90%的否定”！换句话说，想靠模板速成、急着用来参赛获奖是不现实的。
首先，赛场上的题目基本是新题，也就是以前没有出现过的（按道理是这样，至于命题人是不是按道理办事，就是主办方的责任了）。做题少、对知识点理解不深的初学者难以知道应该套用哪个模板。
其次，不能直接套用模板。不同的编程题目，即使用到相同的算法或数据结构，也往往不能直接使用同样的代码，而是要作出很多修改，因为不同环境下的变量和数据规模是不同的。对于模板的学习和使用，需要花时间融会贯通，不能急于求成。参赛者应在深入理解和熟练地掌握模板之后，才能将之应用到竞赛解题中。为了避免参赛者直接套用模板，蓝桥杯软件类大赛的命题人甚至会在出题上“绕圈子”。因而不能原封不动地“抄”模板，而是要灵活运用。
初学者看到这里，可能想打退堂鼓了。但是，请记住“成本越高，收益越大”。学习备赛累、提高编码水平累，这的确是一道门槛，但也正是如此才能筛选出真正的计算机编程能手。如果一个技能很容易掌握，那这个技能大多是大众化的，含金量不高；而像蓝桥杯这样的竞赛，的确是不好学且学习成本高，但能学出来的就是高手，毕业后也能有更光明的就业前景。
有学生是零基础，是刚开始学编程语言，想等学完之后再开始算法竞赛的学习。不要等！因为算法竞赛的编码用不着复杂语法，而且初学者也能将竞赛题当成编程语言的练习题来做。
自主学习，最大的动力是自己！也要找同学一起学，不要自己一个人，有难度的学习，需要互相鼓励，一起进步。
让我们一起走进算法竞赛的“星辰大海”！
蓝桥杯大赛官方资源的获取
蓝桥云课是蓝桥杯大赛的官方资源平台。对于本书所提供的题目，读者都可以在蓝桥云课上进行模拟训练，其内嵌了在线评测系统，能进行自动判题，并返回有关正误的提示，从而帮助读者可以完全自主地高效学习编程。蓝桥云课所提供资源的相关链接如下。
● 链接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。
需要特别指出的是，lanqiaoOJ提供了海量的算法竞赛经典例题及蓝桥杯软件类大赛的历年真题，真题所使用的评测数据与大赛评分时使用的测试数据一致。如果你参加了大赛，那在赛后于蓝桥云课的“链接3”或“链接4”中提交源代码，可得到最接近于实际成绩的结果。如果你正在备赛，那么可以在蓝桥云课中找到完整的算法学习路线与训练体系，其能在很大程度上帮助你取得好成绩。
对于本书例题的解答，虽然书中以C++为主，并在必要时提供了Python的代码以供读者对照学习，但实际上每道题均提供了C++、Java、Python三种语言的参考代码，所有的参考代码均可在本书配套资源中获取。
此外，蓝桥云课的社区资源相当丰富，不仅有专为蓝桥杯软件类大赛展开的话题，还涵盖了计算机相关岗位求职就业的内容。
罗勇军
2022年8月，上海
资源与支持
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
配套资源
本书提供如下资源：
● 本书配套源代码；
● 本书配套PPT课件。
要获得以上配套资源，请在异步社区本书页面中点击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e60150”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。
提交勘误
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
扫码关注本书
扫描下方二维码，您将会在异步社区微信服务号中看到本书信息及相关的服务提示。
第1章 蓝桥杯软件类大赛介绍
蓝桥杯全国软件和信息技术专业人才大赛（以下简称蓝桥杯大赛）的主办单位是工业和信息化部人才交流中心，由国信蓝桥数字科技有限公司承办。第一届蓝桥杯大赛于2010年举办，在十多年的发展中，该大赛的举办得到了各省教育厅和相关院校的积极响应，2022年，参赛学校超过1600所，几乎所有的高校都参加了，蓝桥杯大赛进入全国普通高校学科竞赛排行榜。蓝桥杯软件类大赛目前已成为参赛人数最多的大学计算机编程竞赛之一。
蓝桥杯软件类大赛分为省赛、全国赛两级，设一等奖、二等奖、三等奖，获省赛一等奖即可入围全国赛。
蓝桥杯大赛的参赛人数快速增长。2022年约有14万大学生参加蓝桥杯大赛，与2021年相比，2022年的参赛人数总计增长45.4%，其中C/C++组增长46%，Java组增长32.6%，Python组增长61.7%。
3种编程语言的参赛人数的占比也在变化。2021年，C/C++组占67.4%，Java组占23.6%，Python组占9%。2022年，C/C++组占68%，Java组占19%，Python组占13%。可以看出，C/C++组的参赛人数基本稳定，Python组的参赛人数增长较快。
1.1 蓝桥杯软件类大赛的竞赛规则
蓝桥杯软件类大赛的参赛对象：具有正式全日制学籍并且符合相关科目报名要求的研究生、本科生、高职高专及中职中专学生，以个人为单位进行竞赛。本节内容参考的是《第十三届蓝桥杯全国软件和信息技术专业人才大赛个人赛（软件类）竞赛规则及说明》。
1．组别
竞赛按编程语言、院校进行分组。
（1）按编程语言分组。个人赛软件类按编程语言分为3种：C/C++程序设计、Java程序设计、Python程序设计。
（2）按院校分组。设研究生组、大学A组、大学B组、大学C组。每个组再按照3种编程语言分类，如大学A组C/C++、大学A组Java、大学A组Python等。研究生只能报研究生组。重点本科院校（985、211）的本科生只能报大学A组及以上组别。其他本科院校的本科生可报大学B组及以上组别。其他高职高专、中职中专院校的学生可自行选报任意组别。
目前每位选手每个赛季只能申请参加其中一个组别一种语言的竞赛，如大学A组Python。各个组别单独评奖。
2．竞赛赛程
竞赛在每年的春季举办，有省赛和全国赛，获省赛一等奖即可参加全国赛。每次竞赛的时长为4小时，所有组别同时进行。
3．竞赛形式
个人赛，一人一机，全程机考。选手机器通过局域网连接到各个赛场的竞赛服务器。选手在答题过程中无法访问互联网，也不允许使用除本机以外的资源（如USB连接）。竞赛系统以“服务器-浏览器”方式发放试题、回收选手答案。
4．参赛选手的机器环境
以2022年第十三届蓝桥杯软件类大赛省赛为例。
选手机器配置：x86兼容机器，内存不小于1GB，硬盘不小于60GB。操作系统：Windows 7、Windows 8或Windows 10。
C/C++语言开发环境：Dev-cpp 5.4.0、C/C++ API帮助文档。
Java语言开发环境：JDK 1.8、Eclipse-java-2020-06、API帮助文档。
Python编程环境：Python 3.8.6、IDLE（Python自带编辑器）。
5．试题形式
竞赛题目全部为客观题型，以选手提交的答案的测评结果为评分依据。题型有以下两种。
（1）结果填空。题目描述一个具有确定解的问题，要求选手填写问题的解。不要求解题过程，不限制解题手段（可以使用任何开发语言或工具，甚至可以动手计算），只要求填写最终的结果。最终的解是一个整数或者一个字符串，且可以使用ASCII字符表达。
（2）编程大题。题目包含明确的问题描述、输入和输出格式，以及用于解释问题的样例数据。对于编程大题所涉及的问题，一定有明确、客观的标准来判断结果是否正确，并可以通过程序对结果进行评判。选手应当根据问题描述，编写程序来解决问题。在评测时，选手的程序应当从标准输入读入数据，并将最终的结果输出到标准输出中。在问题描述中会明确说明给定的条件和限制，明确问题的任务，选手的程序应当能解决在给定条件和限制下的所有可能的情况。选手的程序应当具有普遍性，不能只适用于题目的样例数据。为了测试选手给出解法的性能，评分时用的测试用例可能包含大数据量的压力测试用例，选手选择算法时要尽可能考虑其可行性和效率问题。
6．试题考查范围
试题考查选手解决实际问题的能力，对于结果填空题，选手可以使用手算、软件、编程等方法解决；对于编程大题，选手只能编程解决。
竞赛侧重考查选手对于算法和数据结构的灵活运用能力，很多试题需要使用算法才能被有效解决。
考查范围如下（标*部分只限于研究生组、大学A组）。
C/C++程序设计基础：考查选手使用C/C++编写程序的能力。该部分不考查选手对某一语法的理解程度，选手可以使用自己喜欢的语句编写程序。选手可在C语言程序中使用标准C语言的库函数，在C++程序中使用标准C++的库函数（包括C库、STL等）。
Java程序设计基础：考查选手使用Java编写程序的能力。该部分不考查选手对某一语法的理解程度，选手可以使用自己喜欢的语句编写程序。选手可在程序中使用JDK中自带的类，但不能使用其他的第三方类。
Python程序设计基础：考查选手使用Python编写程序的能力。该部分不考查选手对某一语法的理解程度，选手可以使用自己喜欢的语句编写程序。
计算机算法：枚举、排序、搜索、计数、贪心、动态规划（Dynamic Programming，DP）、图论、数论、博弈论*、概率论*、计算几何*、字符串算法等。
数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构*、嵌套数据结构*等。
7．答案提交
只有在竞赛时间内提交的答案内容才可以被用来评测，竞赛结束之后，任何提交内容均无效。选手应使用考试指定的网页来提交代码，任何其他方式的提交（如邮件、U盘）都不作为评测依据。
选手可在竞赛中的任何时间查看自己之前提交的代码，也可以重新提交任何题目的答案，对于每道试题，仅有最后一次的提交结果被保存并作为评测的依据。在竞赛中，评测结果不会显示给选手，选手应当在没有反馈的情况下自行设计数据来调试自己的程序。对于每道试题，选手应将试题的答案内容复制粘贴到网页上进行提交。程序中应只包含计算模块，不要包含任何其他的模块，例如图形、系统接口调用、系统中断等。所有系统接口的调用都应通过标准库来进行。程序中引用的库应该在程序中以源代码的方式写出，在提交时也应当和程序的其他部分一起提交。Python程序仅可以使用Python自带的库，评测时不会安装其他的扩展库。
8．评分
全部使用机器进行自动评分。
对于结果填空题，题目保证只有唯一解，选手的结果只有和解完全相同才得分，出现格式错误或有多余内容时不得分。
对于编程大题，评测系统将使用多个评测数据来测试程序。每个评测数据都有对应的分数。选手所提交的程序将分别用每个评测数据作为输入来运行。对于某个评测数据，如果选手程序的输出与正确答案是匹配的，则选手获得该评测数据的分数。
评测使用的评测数据一般与试题中给定的样例输入输出不一样。因此建议选手在提交程序前使用不同的数据测试自己的程序。
提交的程序应严格按照输出格式的要求来输出，包括输出空格和换行的要求。如果程序没有遵循输出格式的要求将被判错。请注意，程序在输出的时候多输出了内容也属于没有遵循输出格式要求的一种情况，所以在输出的时候请不要输出任何多余的内容，例如调试输出的内容。
C/C++选手请务必选择正确的编译器，如果编译器选择错误，可能导致编译不通过而得0分。请务必让主函数的返回值为0，当返回非0时程序会被看作执行错误而得0分。所有依赖的函数必须明确地在源文件#include <xxx>中，不能通过工程设置而省略常用头文件。Java选手请务必不要使用package语句，并且确保自己的主类名称为Main，否则会导致评测系统在运行时找不到主类而得0分；如果在程序中引用了类库，那么在提交时必须将import语句与程序的其他部分同时提交。该大赛只允许使用Java自带的类库。
1.2 竞赛题示例
蓝桥杯软件类大赛的竞赛题目共10题，总分为150分，竞赛时间为4小时。对于“结果填空”和“编程大题”这两种题型，现作以下特别提示。
（1）结果填空：要求选手根据题目描述直接填写结果。求解方式不限，不要求编写源代码。把答案直接通过网页提交即可，不要写多余的内容。结果填空题每题5分。
（2）编程大题：要求选手设计的程序对于给定的输入能给出正确的输出结果。选手的程序只有能运行出正确结果才有机会得分。每道题目会给出多个测试数据，其中20%～40%是弱测试数据，可以用“暴力”或简单方法编程得分；其他是强测试数据，只有用高效算法进行编程才能得分。由于题量大、时间紧张，因此在难题不会做或来不及用高效算法进行编程时，可以用“暴力”方法编程，以获取20%的分数。程序设计题每题10～25分。
以2022年（第十三届）省赛为例，竞赛分为4个组，大学A组、大学B组、大学C组、研究生组，题目难度相差不大。一般情况下，省赛一等奖获得者的要求是5～7题每道题得100%分数，其他题得部分分数。
现就竞赛中使用的3种编程语言的题目难度情况作了统计，详见表1.1～表1.3。表格中具体题目名称后面的数字表示难度评分，最低难度是1，最高难度是5，最后一行统计了总体难度。
表1.1 第十三届C/C++组题目难度统计
| 竞赛分组 |
大学A组 |
大学B组 |
大学C组 |
研究生组 |
分数 |
| 结果填空 |
裁纸刀1 灭鼠先锋4 |
九进制转十进制1 顺子日期1 |
排列字母1 特殊时间2 |
裁纸刀1 灭鼠先锋4 |
5 5 |
| 编程大题 |
求和2 选数异或3 爬树的甲壳虫4 青蛙过河3 最长不下降子序列5 扫描游戏5 数的拆分4 推导部分和4 |
刷题统计2 修剪灌木2 X进制减法3 统计子矩阵3 积木画4 扫雷4 李白打酒加强版4 砍竹子4 |
纸张尺寸2 求和2 数位排序2 选数异或3 消除游戏4 重新排序4 技能升级4 重复的数4 |
质因数个数2 选数异或3 GCD 2 爬树的甲壳虫4 全排列的价值4 扫描游戏5 数的拆分4 重复的数4 |
10 10 15 15 20 20 25 25 |
| 总体难度 |
35 |
28 |
28 |
33 |
|
表1.2 第十三届Java组题目难度统计
| 竞赛分组 |
大学A组 |
大学B组 |
大学C组 |
研究生组 |
分数 |
| 结果填空 |
裁纸刀1 寻找整数2 |
星期计算1 山1 |
排列字母1 特殊时间2 |
排列字母1 灭鼠先锋4 |
5 5 |
| 编程大题 |
求和2 GCD 2 蜂巢4 全排列的价值4 青蛙过河3 因数平方和4 最优清零方案5 推导部分和4 |
字符统计2 最少刷题数3 求阶乘3 最大子矩阵4 数组切分4 回忆迷宫4 红绿灯4 拉箱子4 |
纸张尺寸2 求和2 矩形拼接3 选数异或3 GCD 2 青蛙过河3 因数平方和4 最长不下降子序列5 |
质因数个数2 数位排序2 蜂巢4 爬树的甲壳虫4 重新排序4 技能升级4 最优清零方案5 推导部分和4 |
10 10 15 15 20 20 25 25 |
| 总体难度 |
31 |
30 |
27 |
34 |
|
表1.3 第十三届Python组题目难度统计
| 竞赛分组 |
大学A组 |
大学B组 |
大学C组 |
研究生组 |
分数 |
| 结果填空 |
裁纸刀1 寻找整数2 |
排列字母1 寻找整数2 |
排列字母1 特殊时间2 |
裁纸刀1 寻找整数2 |
5 5 |
| 编程大题 |
质因数个数2 矩形拼接3 消除游戏4 重新排序4 全排列的价值4 最长不下降子序列5 最优清零方案5 数的拆分4 |
纸张尺寸2 数位排序2 蜂巢4 消除游戏4 全排列的价值4 技能升级4 最长不下降子序列5 最优清零方案5 |
纸张尺寸2 数位排序2 矩形拼接3 GCD 2 蜂巢4 重新排序4 青蛙过河3 因数平方和4 |
质因数个数2 矩形拼接3 消除游戏4 爬树的甲壳虫4 技能升级4 因数平方和4 扫描游戏5 数的拆分4 |
10 10 15 15 20 20 25 25 |
| 总体难度 |
34 |
33 |
27 |
33 |
|
1.3 算法知识点总览
蓝桥杯软件类大赛是算法竞赛，主要考核数据结构和算法的相关知识。算法竞赛涉及丰富的知识点和高难度的编程。不过不用太担心，算法竞赛题目的难度是分级、分阶段的，难题、罕见题并不多，能做出来的参赛选手也少。参赛选手可以把学习的重点放在基础的、常见的算法上，并通过大量的实战练习提高编程能力，以期在蓝桥杯大赛的省赛甚至全国赛上获奖。
计算机数据结构和算法的知识点非常多，这些知识点是计算机科学发展的过程中，经过无数科学家和程序员研究、实践而总结出的精华，是计算机科学这片天空中的“星星”。学习和掌握它们，是成为一名合格程序员的必经之路。当然，蓝桥杯软件类大赛只考一小部分。按所涉及的知识点可以将算法竞赛题目分为这几个大类：杂题、数据结构、基本算法、搜索、DP、数学、字符串、图论等。其中的“杂题”是指不需要使用什么算法和数据结构，或者不方便归类的题目，但其目的都是考查参赛选手的思维和编程能力，杂题也可能很难。
本节会列出除“杂题”外的绝大多数算法竞赛知识点，并按难度将它们分成一星（*）、二星（**）、三星（***）知识点。读者应努力掌握一星、二星知识点，本书的内容也主要涉及一星和二星知识点。
✧ 提示：知识点的难度和题目的难度并不一定对应，对于简单的知识点也可能会出难题。
1．基本数据结构
| * |
链表、队列、优先队列、栈、哈希、二叉树 |
| ** |
堆、二叉堆、单调队列、单调栈、排序（冒泡排序、交换排序、快速排序、归并排序、基尔排序） |
2．基础算法
| * |
打表、枚举、倍增、离散化、前缀和、差分、尺取 |
| ** |
分治、贪心（哈夫曼编码）、二分、三分、整体二分、ST算法（Sparse Table，稀疏表） |
3．搜索
| * |
基本深度优先搜索（Depth First Search，DFS）、DFS记忆化搜索、基本广度优先搜索（Breadth First Search，BFS）、连通性判断、洪水填充 |
| ** |
BFS扩展（双向广搜、优先队列）、剪枝、爬山算法、随机增量法、迭代加深搜索（Iterative Deepening Depth First Search，IDDFS） |
| *** |
IDA*、模拟退火、BFS扩展（双端队列）、A* |
4．高级数据结构
| * |
并查集（带权）、分块、块状链表 |
| ** |
莫队算法、树状数组、线段树、二叉搜索树、替罪羊树、树堆（Treap）、笛卡尔树 |
| *** |
FHQ treap树、伸展（splay）树、可持久化线段树、动态树（LCT）、树套树、CDQ分治、后缀平衡树、K-D树 |
5．动态规划（DP）
| * |
DP问题的性质（重叠子问题、最优子结构、无后效性）、编码方法（记忆化递归、递推）、滚动数组 常见线性DP问题：0/1背包问题、分组背包、多重背包、最长公共子序列、最长递增子序列、编辑距离、最小划分、行走问题、矩阵最长递增路径、子集和问题、矩阵链乘法、布尔括号问题 |
| ** |
区间DP、状态压缩DP、树形DP、数位DP、计数类DP、概率DP |
| *** |
插头DP、基环树DP DP优化：数据结构优化、单调队列优化、斜率优化、分治优化、四边形不等式优化 |
6．数学
数学是一个大类。
（1）简单数学，只用到中小学的数学知识，但是相应题目也可能很难。
（2）初等数论。
| * |
模运算、GCD、LCM、素数判定、埃氏筛 |
| ** |
整数拆分、ExGCD、欧拉筛（线性筛）、威尔逊定理、原根、费马小定理、欧拉定理、欧拉函数、整除分块、同余、逆元、高斯消元、线性基、中国剩余定理、积性函数、0/1分数规划、丢番图方程 |
| *** |
狄利克雷卷积、默比乌斯函数和默比乌斯反演、Min-25筛、杜教筛、洲阁筛 |
（3）组合数学。
| * |
排列、组合、二项式定理、杨辉三角、鸽巢原理、常见恒等式、帕斯卡恒等式、容斥原理、错排问题、斐波那契数列 递推方程：线性递推方程、非线性递推方程、求解递推方程（模板） |
| ** |
卢卡斯定理、catalan数列、stirling数列、普通母函数、指数母函数、泰勒级数 |
| *** |
博弈论（公平组合游戏，巴什游戏、P-position、N-position、尼姆游戏、威佐夫游戏）、图游戏与Sprague-grundy函数、Burnside定理、Pólya定理、L级数、贝尔级数、狄利克雷级数 |
（4）其他。
| * |
高精度、快速幂、矩阵乘法、矩阵快速幂 |
| ** |
概率与期望、Simpson积分、高等数学 |
| *** |
单纯形法解线性规划、快速傅里叶变换（Fast Fourier Tramsform，FFT） |
（5）几何。
| * |
点积、叉积、点、线、面、二维几何、面积、体积 |
| ** |
三维几何、凸包、最近点对、半平面交、旋转卡壳、三角剖分、最小圆覆盖 |
| *** |
三维凸包、最小球覆盖 |
7．字符串
| * |
进制哈希 |
| ** |
字典树、Manacher回文算法、回文树、KMP、后缀树、后缀数组、AC自动机、后缀自动机 |
8．图论
| * |
图的存储（矩阵、邻接表、链式前向星）、最短路（BFS）、树的重心、树的直径 |
| ** |
最短路（dijkstra、bellman-ford、spfa、floyd）、最小生成树（kruskal、prim）、拓扑排序、二分图匹配、差分约束、无向图的连通性、有向图的连通性、强连通分量、割点、割边、缩点、桥、2-SAT、树上分治、LCA、树分块、虚树、基环树 |
| *** |
树链剖分、最大流（Dinic、Sap、ISAP）、最小割、费用流 |
1.4 历年真题知识点统计
本节盘点2017～2022年（第八届 ～ 第十三届）省赛C/C++大学A组60道题的知识点，把这60道题分类填到对应的知识点表格中，如表1.4所示，其中有些题目是综合题，一道题考了几个知识点。C/C++大学A组的知识点具有代表性，其他语言和组别的题目涉及的知识点与之类似。
表1.4 第八届～第十三届蓝桥杯软件类大赛省赛C/C++大学A组题目所涉知识点统计
| 知识点 |
题目 |
| 杂题 |
2017油漆面积，2018付账问题、2019最大降雨量、2019外卖店优先级、2020蛇形填数、2020成绩分析、2020回文日期、2022裁纸刀 |
| 基本数据结构 |
二叉树（2019完全二叉树的值） |
| 基础算法 |
枚举（2018打印图形、2021卡片）、差分（2018三体攻击）、倍增 |
| 二分法（2017分巧克力、2022青蛙过河）、前缀和（2022求和） |
| 搜索 |
DFS（2017迷宫、2017方格分割、2017正则问题）、BFS（2017跳蚱蜢、2018全球变暖、2019迷宫） |
| 高级数据结构 |
并查集（2019修改数组、2020七段码、2022推导部分和）、线段树（2022选数异或、2022最长不下降子序列、2022扫描游戏） |
| 动态规划 |
线性DP（2017字母组串，2017最大公共子串、2017包子凑数、2020字串排序、2021砝码称重、2021括号序列）、记忆化搜索 |
| 状态压缩DP（2019糖果、2021回路计数）、树形DP（2021左子结点右兄弟）、单调优化（2021分果果） |
| 数学 |
简单数学：2018分数、2018星期一、2018乘积尾零、2018第几个幸运数、2019平方和、2019数列求值、2020门牌制作、2020平面分割 |
| 数论：余数（2018倍数问题）、GCD（2017包子凑数，2020既约分数）、质因数分解（2021货物摆放）、素数（2022数的拆分）、逆元（2022爬树的甲壳虫） |
| 组合数学：burnside引理（2017魔方状态）、卢卡斯定理（2019组合数问题）、博弈论（2021异或数列、2022灭鼠先锋） |
| 其他：快速幂（2019 RSA解密） |
| 几何：叉积、面积（2020荒岛探测）、2021直线、2022扫描游戏 |
| 字符串 |
简单字符串处理（2018航班时间、2020子串分值） |
| 图论 |
最短路BFS（2019迷宫）、最短路Floyd（2021路径） |
表1.4中涉及的知识点不算多，不过蓝桥杯软件类大赛的考点在逐年增多。
从表1.4中可以看出，省赛涉及的知识点比较基础，考核的是基本的算法思维、算法、编程能力。要想获奖，最重要的是通过大量做基础题目，培养自己的计算思维，并提高自己的建模和编程能力。
有一些知识点是必考的，因为它们是整个算法竞赛知识库的基础，现举例如下。
（1）杂题。杂题是指不需要使用算法和数据结构，只需要进行逻辑推理的题目，可难可易。考查的是参赛选手的思维能力和编程能力，这只能通过大量做题来提高。
（2）广度优先搜索（Breadth First Search，BFS）和深度优先搜索（Depth First Search，DFS）就是暴力搜索。这是非常基础的算法，是基础中的基础。
（3）动态规划。涉及线性DP及一些DP应用，例如状态压缩DP、树形DP等。
（4）简单数学和简单数论。
（5）简单的字符串处理、输入与输出。
（6）基本算法，例如排序、排列、二分、倍增、差分、贪心。
（7）基本数据结构，例如队列、栈、链表、二叉树等。
1.5 蓝桥杯软件类大赛的评测系统
本书的例题和习题选自蓝桥杯大赛官网题库（在本书中简称lanqiaoOJ），lanqiaoOJ中有历年真题和一些训练题。
lanqiaoOJ里面的“判题机器人”如何判断你提交的代码是否正确？
能否直接通过看代码的方式，检查每一行代码的逻辑的正确性？这几乎是不可能实现的，因为看别人的代码极其痛苦，往往会让人晕头转向。即使是常年进行计算机编程教学的老师在检查别人的代码时也不例外，像程序设计这样的题目，如果改卷的老师不是用机器验证，而是手动批阅，将很难打分。
所以lanqiaoOJ中的“判题机器人”如果看不懂你提交的代码，它干脆就不看代码，而是直接检验你提交代码的正确性。这一方法简单粗暴（即用黑盒测试），步骤如下。
（1）准备好标准测试数据，包括输入data.in和对应的输出data.out。
（2）运行你提交的代码，读入输入数据data.in，产生输出数据my.out。
（3）如果超出限定时间，代码还没运行结束，那就是没有产生输出，则判错。
（4）对比data.out和my.out，如果完全一样，则判为正确，否则判错。
蓝桥杯软件类大赛的判题规则允许选手得部分分数。一道题包含多组测试数据，一般是10组，每组占10%的分数。有的测试数据比较简单，容易通过，能够让选手得一些分数。
下面说明lanqiaoOJ的使用方法。输入链接地址（www.lanqiao.cn/problems）之后，出现图1.1所示的页面，单击“标签”，然后按“年份”或其他算法分类查询题目。
图1.1 lanqiaoOJ题库
做lanqiaoOJ中的题目时，需要输入相应的代码让“判题机器人”判断。下面分别就结果填空题（以下简称填空题）和编程大题举例说明。
1．结果填空题
例题1-1．平方和
2019年（第十届）省赛，填空题，lanqiaoOJ题号599
【题目描述】小明对数位中含有2、0、1、9的数字很感兴趣，在1到40中这样的数包括1、2、9、10至32、39和40，共28个，它们的和是574，平方和是14362。注意，平方和是指将每个数分别平方后求和的结果。请问，在1到2019中，所有这样的数的平方和是多少？
✧ 提示：这一题的链接是https://www.lanqiao.cn/problems/599/learning/，题号599。本书后面的题目只给出题号，省略完整的链接。
这是一道填空题，只需要写出答案即可，不过仍需要编写代码以求得答案，这一题的求解过程参见2.1.4小节“巧用Python”中的例题2-12“平方和”。
（1）编写并提交代码。这一题的答案是2658417853，在lanqiaoOJ中的测试方法如图1.2所示。
图1.2 测试lanqiaoOJ 599题
单击页面下方的“提交检测”，系统返回测试结果。
（2）查看错误提示。单击页面左边的时钟符号
，可以看到自己提交的这一题的记录，如图1.3所示。单击“FAIL”可以看到判题说明。
图1.3 lanqiaoOJ 599题的测试记录
（3）看题解。lanqiaoOJ的一个优点是提供了题解功能，能看到其他人的题解。单击页面左边的“答 题解”，可以看到此题的各种编程语言的题解，非常方便。单击此题的“Python3”题解，可以看到有123个题解，如图1.4所示。读者做题后也可以发布自己的题解，方便别人学习你的解题思路。
图1.4 lanqiaoOJ 599题的“Python3”题解
2．编程大题
编程大题有多组测试数据。下面用一道题说明“判题机器人”如何用这些数据测试出你的代码的正确性。
例题1-2．刷题统计
2022年（第十三届）省赛，lanqiaoOJ题号2098
时间限制：1s 内存限制：256MB
【题目描述】小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做a道题，周六和周日每天做b道题。请你帮小明计算，按照计划他将在第几天实现做题数大于等于n题？
【输入格式】输入一行，包含3个整数a、b和n。
【输出格式】输出一个整数代表天数。
【评测用例规模与约定】对于50%的评测用例，1≤a, b, n≤106；对于100%的评测用例，1≤a, b, n≤1018。
下面的代码可以简单地模拟题目的操作：周六、周日每天做b道题，周一到周五每天做a道题，累计到n题时输出天数。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main(){
4 long long a,b,n; cin>>a>>b>>n; //注意用long long
5 long long sum=0,day=0;
6 while(sum<=n){
7 day++;
8 if(day%7==6||day%7==0) sum+=b; //周六、周日每天做b道题
9 else sum+=a; //周一至周五每天做a道题
10 }
11 cout << day;
12 }
提交代码后，只能通过50%的测试。这意味着若是10分的题，只能得到5分。
为什么只能通过50%的测试？因为代码的运行效率低。在while循环中，每循环一次，day加1，所做题目数量累加为sum，直到sum＞n，这样做效率非常低。本题要求“时间限制：1s”，对于100%的数据，1≤a, b, n≤1018，上面代码的运行时间显然会超过1s。
判题机器人会将超时的代码判为“错误”，例如下面这组测试数据：
7089 7494 500000014592.
答案是69399007，即while循环了69399007次，运行时间约2s，超时了。
这一题如果要100%通过测试，可参见8.1节“模运算”中关于该题的解析。
小结
本章介绍了蓝桥杯软件类大赛的基本规则和考核内容，让读者对该大赛有了基本的了解，从而可以有目的地开始后续知识的学习。算法是内涵极其丰富的“综合性学习内容”，它包含大量的知识点、复杂的编程技术、高难度的建模、崭新的计算思维。对算法的学习不存在“速成”，只有一步一步、脚踏实地地学习才能走向成功。
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e60150”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
