1. 项目概述一次硬核的算法能力大考“蓝桥杯”这个名字对于国内计算机相关专业的学生和算法爱好者来说绝对不陌生。它不仅仅是一个竞赛更像是一个检验编程基本功、算法思维和临场解决问题能力的试金石。而“国赛B组”更是其中的巅峰战场汇聚了从省赛中脱颖而出的佼佼者。今天我想和大家深入复盘一下2020年第十一届蓝桥杯C/C国赛B组的真题。这不仅仅是一份“赛后答案”我更想从一个参赛者和出题人思维的角度去拆解每一道题目背后的核心考点、解题思路的构建过程以及那些在考场上容易忽略的“坑点”。无论你是正在备赛的选手还是希望提升自己算法能力的开发者相信这次对国赛真题的深度剖析都能让你对“如何解决一个复杂的工程化算法问题”有更深刻的理解。我们将一起看到国赛级别的题目是如何将基础数据结构、数学思维、动态规划、搜索优化等知识点巧妙地融合在一个个看似抽象、实则贴近实际应用场景的问题中的。2. 整体赛题风格与核心能力考察2020年的国赛B组整体上延续了蓝桥杯“重思维、重基础、轻套路”的一贯风格。它不像一些纯竞技性的算法比赛那样追求极致的算法模板和奇技淫巧而是更侧重于考察选手将基础知识灵活应用于解决新问题的能力。这套题目的一个显著特点是“梯度明显”——有可以快速拿下的签到题也有需要深思熟虑、多步推导的中等题更有需要综合多种高级算法和进行大量优化才能触碰的压轴题。这种设计很好地拉开了不同层次选手的差距。从能力维度上看本次比赛重点考察了以下几个方面扎实的代码实现能力即便思路正确代码在边界条件、数据类型尤其是大整数、输入输出格式上的任何疏忽都可能导致丢分。国赛的环境是严格的没有第二次提交的机会。数学建模与抽象能力很多题目描述了一个具体的场景如扩散、分配、序列选手需要第一时间将其抽象为熟悉的数学模型如图论、数论、动态规划状态机。对算法时空复杂度的敏感度这是区分“暴力枚举”选手和“优化算法”选手的关键。题目数据范围的设计往往就是最大的提示直接告诉你朴素的解法行不通必须寻找更优的算法。搜索与剪枝的优化技巧在状态空间巨大的问题中如何设计搜索顺序如何设计有效的剪枝条件是解决许多“填空题”和“编程大题”的核心。动态规划的状态设计能力动态规划是国赛的常客也是难点。如何定义状态如何找到状态转移方程如何处理后效性是衡量选手算法功底的硬指标。接下来我们将选取本届比赛中有代表性的几道题目进行从题目理解、思路分析、到代码实现、再到优化细节的完整拆解。3. 核心题目深度解析与实战复盘3.1 试题A美丽的2签到题中的思维陷阱题目简述在1到2020之间包含1和2020有多少个整数的十进制表示中包含数字‘2’。这通常是第一道题意在让选手快速进入状态并建立信心。但即便是签到题也暗含考察点。思路解析 最直接的思路是遍历1到2020的每一个数将其转换为字符串然后检查字符串中是否包含字符‘2’。这种方法简单直观在数据范围很小的情况下完全可行。代码实现与细节#include iostream #include string using namespace std; int main() { int count 0; for (int i 1; i 2020; i) { // 将数字转换为字符串进行查找 string s to_string(i); if (s.find(2) ! string::npos) { count; } } cout count endl; return 0; }或者使用取模运算逐位判断int count 0; for (int i 1; i 2020; i) { int x i; while (x) { if (x % 10 2) { count; break; // 找到一个2就跳出循环避免重复计数 } x / 10; } }避坑指南与心得注意虽然题目简单但这里有一个初学者容易忽略的效率问题。to_string和string::find在循环内频繁调用会有一定的开销。对于这道题2020次循环完全无压力。但在更大型的比赛或对性能有要求的场景下对于这种数值范围遍历问题使用数学方法数位统计或者高效的逐位取模法是更优的选择。这道题提醒我们即使是最简单的任务也要有选择合适工具的意识和习惯。答案具体数字需计算本身不难但确保计算过程准确无误是拿分的关键。3.2 试题B扩散模拟与优化策略题目简述在一个无限的网格中初始有四个点位于(0,0), (2020,11), (11,14), (2000,2000)。每一分钟每个已标记的点会向上、下、左、右四个方向扩散一格新点也被标记。问经过2020分钟后有多少个点被标记。思路拆解 这是一个典型的“模拟扩散”或“BFS广度优先搜索模拟”问题。最朴素的想法是用一个集合如setpairint,int来存储所有已被标记的点。每一分钟遍历当前集合中的所有点将它们的四个邻居加入一个新集合最后用新集合替换旧集合循环2020次。核心难点与优化状态爆炸经过2020分钟扩散范围的理论边长超过4000点数量级可能达到千万甚至更多。直接模拟并存储所有点对内存和时间的压力极大。去重使用set自动去重但set的插入和查找是O(log n)的在数据量巨大时非常慢。对称性观察初始点它们并非关于原点对称无法利用对称性大幅减少计算量。优化策略使用布尔数组与坐标偏移由于扩散范围可以预估初始坐标±2020我们可以定义一个足够大的二维布尔数组如bool grid[10000][10000]并将原点偏移到数组中心。访问和标记都是O(1)。使用队列进行BFS这是更优的方法。我们关心的是“时间”。使用队列进行BFS每个节点记录其坐标和达到该点的时间。从四个初始点时间为0入队开始。每次从队列取出一个点如果其时间t 2020则检查其四个方向如果该方向上的点未被访问过则将其标记为已访问并将其坐标 时间t1入队。这样每个点只会被访问一次时间复杂度约为O(被访问的点数)空间复杂度亦然。使用unordered_set并自定义哈希如果不想处理大数组的偏移可以用unordered_set存储点的坐标自定义哈希函数将pairint,int映射为一个long long其平均访问复杂度为O(1)比set快。BFS模拟代码框架#include iostream #include queue #include unordered_set using namespace std; // 自定义哈希将坐标对映射为一个唯一整数 struct pair_hash { template class T1, class T2 std::size_t operator () (const std::pairT1, T2 p) const { auto h1 std::hashT1{}(p.first); auto h2 std::hashT2{}(p.second); // 一个简单的组合方式 return h1 ^ (h2 1); } }; using Point pairint, int; int dirs[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int main() { // 初始点 vectorPoint starts {{0,0}, {2020,11}, {11,14}, {2000,2000}}; unordered_setPoint, pair_hash visited; // 已访问点集 queuepairPoint, int q; // 队列存储(点 到达时间) for (auto p : starts) { visited.insert(p); q.push({p, 0}); } long long ans starts.size(); // 初始点数 while (!q.empty()) { auto [pos, t] q.front(); q.pop(); if (t 2020) continue; // 时间已到不再扩散 for (auto d : dirs) { Point nxt {pos.first d[0], pos.second d[1]}; if (!visited.count(nxt)) { visited.insert(nxt); q.push({nxt, t 1}); ans; // 新的点被标记 } } } cout ans endl; return 0; }注意此代码框架中ans的初始值应为4然后在BFS过程中每发现一个新点就加1。由于2020较大运行此程序需要一定时间且对内存visited集合的大小有要求。在实际比赛中可能需要进一步优化例如利用扩散的对称性和范围限制或者使用更紧凑的数据结构如位图。这道题完美体现了从“暴力模拟”到“优化搜索”的思维跃迁。3.3 试题C阶乘约数数论与质因数分解题目简述定义f(n)为n的约数个数。求f(1!) * f(2!) * ... * f(2020!)的最后几位具体位数看题目要求可能是最后5位或9位。思路解析 这是一道纯数论题。直接计算每个阶乘然后求约数个数是不可行的因为2020!是一个天文数字。 核心知识正整数的约数个数公式。如果一个数N的质因数分解为N p1^a1 * p2^a2 * ... * pk^ak那么它的约数个数d(N) (a11)*(a21)*...*(ak1)。因此问题转化为如何快速得到1!, 2!, ..., 2020!每个数的质因数分解形式 这里需要利用阶乘的质因数分解定理勒让德定理对于质数p在n!的质因数分解中p的指数等于[n/p] [n/p^2] [n/p^3] ...其中[x]表示对x向下取整。解题步骤找出所有质数使用筛法如埃拉托斯特尼筛法找出2020以内的所有质数。计算每个质数p的贡献对于每个质数p计算它在1!, 2!, ..., 2020!中分别的指数。但更高效的方法是我们最终需要的是乘积∏ f(i!)。而f(i!)可以根据i!的质因数分解用约数个数公式算出。 实际上我们可以递推计算。设exp[p][i]表示质数p在i!中的指数。那么有exp[p][i] exp[p][i-1] (i 中质因子p的个数)。 而i 中质因子p的个数可以通过循环除以p得到。计算乘积对于每个i从1到2020计算f(i!) ∏_{p是质数} (exp[p][i] 1)。然后将所有的f(i!)乘起来。由于题目可能只要求最后几位我们可以在乘法过程中始终对10^kk为要求的位数取模避免大数运算。代码实现要点#include iostream #include vector #include cmath using namespace std; const int MOD 100000; // 假设求最后5位 const int MAX_N 2020; int main() { // 1. 筛质数 vectorbool isPrime(MAX_N 1, true); vectorint primes; for (int i 2; i MAX_N; i) { if (isPrime[i]) { primes.push_back(i); for (int j i * i; j MAX_N; j i) { isPrime[j] false; } } } // 2. 计算每个i!的质因数指数二维数组开销大可以优化 // 更优直接计算每个质数p对最终答案的贡献。 // 最终答案 ∏_{i1}^{2020} f(i!) ∏_{i1}^{2020} ∏_{p} (exp_p(i!) 1) // 交换乘积顺序 ∏_{p} [ ∏_{i1}^{2020} (exp_p(i!) 1) ] // 而 exp_p(i!) 是单调不减的。对于每个p我们只需要知道有多少个i使得 exp_p(i!) 等于某个值。 // 实际上exp_p(i!) floor(i/p) floor(i/p^2) ... // 我们可以遍历每个i计算其阶乘的约数个数然后连乘取模。 long long ans 1; for (int i 1; i MAX_N; i) { // 计算 i! 的约数个数 long long divisor_cnt 1; int temp i; // 实际上我们需要基于 i-1! 的结果来计算 i!这里为了清晰独立计算每个i!。 // 更高效的做法是维护一个质数指数数组。 vectorint exp(primes.size(), 0); // 计算i的质因数分解并累加到全局指数数组中这里简化独立计算每个i!的d(i!) // 由于i最大2020我们可以直接对i进行质因数分解然后结合前一个阶乘的结果。 // 但这里展示另一种思路直接计算 i! 的d(i!) // 方法对于每个质数p计算它在i!中的指数e然后 divisor_cnt * (e1) for (size_t idx 0; idx primes.size(); idx) { int p primes[idx]; if (p i) break; int e 0; int power p; while (power i) { e i / power; power * p; // 注意可能溢出可用 long long } divisor_cnt (divisor_cnt * (e 1)) % MOD; } ans (ans * divisor_cnt) % MOD; } cout ans endl; return 0; }注意上述代码中对于每个i都重新计算了i!的质因数分解存在大量重复计算。在竞赛中更高效的做法是维护一个数组cnt[p]记录当前质数p在(i-1)!中的总指数。当计算i!时只需要将i的质因数分解结果累加到cnt数组中然后根据更新后的cnt计算d(i!)。这道题是数论应用的经典例题考察选手对约数个数公式和阶乘质因数分解的掌握程度以及对程序效率的优化意识。3.4 试题D本质上升序列动态规划与去重题目简述给定一个长度不超过200的字符串由小写字母组成要求计算其所有本质不同的上升子序列的数量。这里的“上升”指的是子序列中每个字符的ASCII码严格递增。思路解析 这是一个经典的动态规划计数问题且带有“本质不同”的条件增加了难度。 如果没有“本质不同”的条件我们可以定义dp[i]为以第i个字符结尾的严格递增子序列的个数。那么转移方程为dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。这里的1表示子序列只包含s[i]自身。最终答案是所有dp[i]的和。但是要求“本质不同”上述方法会重复计算相同的子序列。例如字符串“aba”以第二个‘a’结尾的子序列“a”和以第一个‘a’结尾的子序列“a”是同一个。如何处理去重我们需要确保对于同一个子序列只被计算一次。一个常见技巧是在动态规划过程中当遇到相同的字符时只保留最后一次出现时的计数贡献或者从后往前考虑。 更精确的状态定义和转移 定义dp[i]表示以字符i这里‘i’代表26个小写字母之一结尾的、本质不同的严格递增子序列的个数。 我们从左到右遍历字符串的每个字符c对应字母索引idx。 对于当前字符c新的以c结尾的子序列可以由两部分构成子序列只包含它自己1。所有以小于c的字母结尾的子序列后面加上c。即sum(dp[j])其中j是字母索引且j idx。但是如果字符串中后面再次出现相同的字符c直接这样加会重复。关键在于当我们处理到后面这个相同的字符时前面那个字符c所形成的所有子序列作为结尾已经被当前这个c所能形成的子序列所包含了。因为以当前c结尾可以在前面任意一个小于c的结尾子序列后追加这自然也包括了之前那个c所依赖的那些子序列。因此正确的做法是遍历字符串对于每个字符c我们计算new_count 1 sum(dp[j] for j idx)。然后我们将dp[idx]直接更新为new_count而不是累加。因为新的c的出现使得所有以c结尾的子序列被重新计算了旧的值被覆盖从而避免了重复。算法步骤初始化一个长度为26的数组dp全为0。dp[x]表示以字母x结尾的本质不同上升子序列个数。遍历字符串s的每个字符ch计算idx ch - a。计算total 1。这个1代表子序列[ch]。遍历所有字母j从 0 到idx-1total dp[j]。将dp[idx]更新为total。注意是赋值不是累加。遍历结束后答案就是dp[0] dp[1] ... dp[25]。代码实现#include iostream #include string #include vector using namespace std; int main() { string s; // 假设s已读入长度不超过200 cin s; vectorlong long dp(26, 0); // 可能结果很大用long long for (char ch : s) { int idx ch - a; long long new_val 1; // 单独自己作为一个子序列 for (int j 0; j idx; j) { new_val dp[j]; } dp[idx] new_val; // 关键直接赋值覆盖旧值 } long long ans 0; for (long long val : dp) { ans val; } cout ans endl; return 0; }心得与扩展这道题是动态规划去重计数的经典模型。它考察了两个关键点一是对“上升子序列”计数DP基本模型的掌握二是对“本质不同”这一约束条件的处理技巧。dp[idx] new_val这个赋值操作是去重的精髓所在它保证了对于同一个字符后续出现时会基于最新的、包含所有可能前缀的状态进行计算而不会与之前的状态产生重复累加。如果题目改为“非递减”允许相等处理方式又会不同需要仔细思考状态定义。这种题目在笔试面试中也经常出现变体理解其核心思想至关重要。4. 常见问题与实战调试技巧在解决这类算法竞赛题目时除了思路调试和验证能力同样重要。以下是一些常见问题及应对策略4.1 结果错误但样例通过这是最令人头疼的情况。可能的原因和排查手段数据范围与溢出这是最最常见的原因。检查所有中间变量和最终结果的数据类型。int是否足够long long呢在C中两个int相乘即使赋值给long long也会先以int相乘导致溢出。强制类型转换或直接使用long long进行计算。对于模运算乘法前先取模。技巧在编写代码时对于涉及大量计算或可能很大的数养成使用long long的习惯。定义常量typedef long long ll;可以节省时间。边界条件循环的起止点是否正确例如遍历数组是从0到n-1还是1到n动态规划的初始状态dp[0]是否设置正确题目中的“包含端点”是否处理妥当算法逻辑漏洞你的算法是否覆盖了所有情况是否存在某些特殊情况被忽略例如图论中是否有重边、自环字符串是否可能为空对于“本质上升序列”这类题去重逻辑是否完全正确一个有效的调试方法是构造大量的小规模随机数据用你的程序和一个绝对正确但低效的暴力程序如DFS枚举进行对比对拍。输入输出格式蓝桥杯经常要求输出特定格式比如换行、空格、保留小数等。务必仔细阅读输出要求。有时需要输出的是一个整数有时是字符串。4.2 程序超时或内存超限时间复杂度估算在动手前一定要根据数据范围估算最坏情况下的操作次数。例如n10^5O(n²)的算法操作次数约10^10必然超时需要O(n log n)或O(n)的算法。剪枝与优化在搜索DFS/BFS中是否应用了有效的剪枝在动态规划中状态转移是否可以优化如斜率优化、单调队列是否存在不必要的重复计算用记忆化搜索解决数据结构选择频繁查找用unordered_set/unordered_mapO(1)平均而非set/mapO(log n)。需要有序性时才用后者。数组访问比链表快。输入输出加速在C中对于大量数据输入输出使用ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);可以显著提升速度。避免使用endl它刷新缓冲区改用\n。内存使用检查是否开了过大的全局数组特别是二维数组。bool数组可以用bitset或vectorbool位压缩节省空间。递归深度过深可能导致栈溢出可以尝试改成迭代或显式栈。4.3 如何高效备赛与练习分专题突破不要盲目刷题。将算法分为几个大专题基础语法与模拟、枚举与递归、排序与查找、数据结构栈、队列、链表、树、图、动态规划、搜索DFS、BFS、剪枝、数论、字符串等。每个阶段集中攻克一个专题理解其经典模型和变体。精做真题像本文这样对每一道真题进行深度复盘。不仅要写出代码更要理解出题人的意图、考察的知识点、各种解法的优劣以及如何想到最优解。尝试一题多解。建立代码模板库将常用的、无误的算法代码整理成模板例如快速排序、二分查找、并查集、Dijkstra最短路径、线段树等。比赛时可以直接使用节省时间并减少错误。模拟赛环境定期进行限时模拟赛使用过去的真题。适应比赛的压力和节奏练习时间分配策略先易后难有舍有得。善用调试工具和“对拍”学习使用IDE的调试器。编写简单的数据生成器和暴力求解程序与你的优化程序进行“对拍”这是发现隐蔽错误的最强武器。回顾2020年的这套国赛题它没有在算法理论上设置过于高深的障碍而是扎实地考察了选手的基本功、思维严谨性和将知识融会贯通解决新问题的能力。从简单的数位判断到中等的模拟搜索优化再到需要深刻数学洞察力的数论题和精巧状态设计的动态规划题构成了一套层次分明、选拔性强的试卷。对于备赛者而言吃透这样的真题其价值远高于泛泛地刷很多简单题。它告诉你算法竞赛的终点不是背诵模板而是培养一种严谨、优化、创造性的计算思维。这种思维无论是在后续的学习中还是在真正的软件开发工作中都是无比宝贵的财富。 蓝桥杯国赛B组真题深度解析：从算法思维到工程实践
1. 项目概述一次硬核的算法能力大考“蓝桥杯”这个名字对于国内计算机相关专业的学生和算法爱好者来说绝对不陌生。它不仅仅是一个竞赛更像是一个检验编程基本功、算法思维和临场解决问题能力的试金石。而“国赛B组”更是其中的巅峰战场汇聚了从省赛中脱颖而出的佼佼者。今天我想和大家深入复盘一下2020年第十一届蓝桥杯C/C国赛B组的真题。这不仅仅是一份“赛后答案”我更想从一个参赛者和出题人思维的角度去拆解每一道题目背后的核心考点、解题思路的构建过程以及那些在考场上容易忽略的“坑点”。无论你是正在备赛的选手还是希望提升自己算法能力的开发者相信这次对国赛真题的深度剖析都能让你对“如何解决一个复杂的工程化算法问题”有更深刻的理解。我们将一起看到国赛级别的题目是如何将基础数据结构、数学思维、动态规划、搜索优化等知识点巧妙地融合在一个个看似抽象、实则贴近实际应用场景的问题中的。2. 整体赛题风格与核心能力考察2020年的国赛B组整体上延续了蓝桥杯“重思维、重基础、轻套路”的一贯风格。它不像一些纯竞技性的算法比赛那样追求极致的算法模板和奇技淫巧而是更侧重于考察选手将基础知识灵活应用于解决新问题的能力。这套题目的一个显著特点是“梯度明显”——有可以快速拿下的签到题也有需要深思熟虑、多步推导的中等题更有需要综合多种高级算法和进行大量优化才能触碰的压轴题。这种设计很好地拉开了不同层次选手的差距。从能力维度上看本次比赛重点考察了以下几个方面扎实的代码实现能力即便思路正确代码在边界条件、数据类型尤其是大整数、输入输出格式上的任何疏忽都可能导致丢分。国赛的环境是严格的没有第二次提交的机会。数学建模与抽象能力很多题目描述了一个具体的场景如扩散、分配、序列选手需要第一时间将其抽象为熟悉的数学模型如图论、数论、动态规划状态机。对算法时空复杂度的敏感度这是区分“暴力枚举”选手和“优化算法”选手的关键。题目数据范围的设计往往就是最大的提示直接告诉你朴素的解法行不通必须寻找更优的算法。搜索与剪枝的优化技巧在状态空间巨大的问题中如何设计搜索顺序如何设计有效的剪枝条件是解决许多“填空题”和“编程大题”的核心。动态规划的状态设计能力动态规划是国赛的常客也是难点。如何定义状态如何找到状态转移方程如何处理后效性是衡量选手算法功底的硬指标。接下来我们将选取本届比赛中有代表性的几道题目进行从题目理解、思路分析、到代码实现、再到优化细节的完整拆解。3. 核心题目深度解析与实战复盘3.1 试题A美丽的2签到题中的思维陷阱题目简述在1到2020之间包含1和2020有多少个整数的十进制表示中包含数字‘2’。这通常是第一道题意在让选手快速进入状态并建立信心。但即便是签到题也暗含考察点。思路解析 最直接的思路是遍历1到2020的每一个数将其转换为字符串然后检查字符串中是否包含字符‘2’。这种方法简单直观在数据范围很小的情况下完全可行。代码实现与细节#include iostream #include string using namespace std; int main() { int count 0; for (int i 1; i 2020; i) { // 将数字转换为字符串进行查找 string s to_string(i); if (s.find(2) ! string::npos) { count; } } cout count endl; return 0; }或者使用取模运算逐位判断int count 0; for (int i 1; i 2020; i) { int x i; while (x) { if (x % 10 2) { count; break; // 找到一个2就跳出循环避免重复计数 } x / 10; } }避坑指南与心得注意虽然题目简单但这里有一个初学者容易忽略的效率问题。to_string和string::find在循环内频繁调用会有一定的开销。对于这道题2020次循环完全无压力。但在更大型的比赛或对性能有要求的场景下对于这种数值范围遍历问题使用数学方法数位统计或者高效的逐位取模法是更优的选择。这道题提醒我们即使是最简单的任务也要有选择合适工具的意识和习惯。答案具体数字需计算本身不难但确保计算过程准确无误是拿分的关键。3.2 试题B扩散模拟与优化策略题目简述在一个无限的网格中初始有四个点位于(0,0), (2020,11), (11,14), (2000,2000)。每一分钟每个已标记的点会向上、下、左、右四个方向扩散一格新点也被标记。问经过2020分钟后有多少个点被标记。思路拆解 这是一个典型的“模拟扩散”或“BFS广度优先搜索模拟”问题。最朴素的想法是用一个集合如setpairint,int来存储所有已被标记的点。每一分钟遍历当前集合中的所有点将它们的四个邻居加入一个新集合最后用新集合替换旧集合循环2020次。核心难点与优化状态爆炸经过2020分钟扩散范围的理论边长超过4000点数量级可能达到千万甚至更多。直接模拟并存储所有点对内存和时间的压力极大。去重使用set自动去重但set的插入和查找是O(log n)的在数据量巨大时非常慢。对称性观察初始点它们并非关于原点对称无法利用对称性大幅减少计算量。优化策略使用布尔数组与坐标偏移由于扩散范围可以预估初始坐标±2020我们可以定义一个足够大的二维布尔数组如bool grid[10000][10000]并将原点偏移到数组中心。访问和标记都是O(1)。使用队列进行BFS这是更优的方法。我们关心的是“时间”。使用队列进行BFS每个节点记录其坐标和达到该点的时间。从四个初始点时间为0入队开始。每次从队列取出一个点如果其时间t 2020则检查其四个方向如果该方向上的点未被访问过则将其标记为已访问并将其坐标 时间t1入队。这样每个点只会被访问一次时间复杂度约为O(被访问的点数)空间复杂度亦然。使用unordered_set并自定义哈希如果不想处理大数组的偏移可以用unordered_set存储点的坐标自定义哈希函数将pairint,int映射为一个long long其平均访问复杂度为O(1)比set快。BFS模拟代码框架#include iostream #include queue #include unordered_set using namespace std; // 自定义哈希将坐标对映射为一个唯一整数 struct pair_hash { template class T1, class T2 std::size_t operator () (const std::pairT1, T2 p) const { auto h1 std::hashT1{}(p.first); auto h2 std::hashT2{}(p.second); // 一个简单的组合方式 return h1 ^ (h2 1); } }; using Point pairint, int; int dirs[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int main() { // 初始点 vectorPoint starts {{0,0}, {2020,11}, {11,14}, {2000,2000}}; unordered_setPoint, pair_hash visited; // 已访问点集 queuepairPoint, int q; // 队列存储(点 到达时间) for (auto p : starts) { visited.insert(p); q.push({p, 0}); } long long ans starts.size(); // 初始点数 while (!q.empty()) { auto [pos, t] q.front(); q.pop(); if (t 2020) continue; // 时间已到不再扩散 for (auto d : dirs) { Point nxt {pos.first d[0], pos.second d[1]}; if (!visited.count(nxt)) { visited.insert(nxt); q.push({nxt, t 1}); ans; // 新的点被标记 } } } cout ans endl; return 0; }注意此代码框架中ans的初始值应为4然后在BFS过程中每发现一个新点就加1。由于2020较大运行此程序需要一定时间且对内存visited集合的大小有要求。在实际比赛中可能需要进一步优化例如利用扩散的对称性和范围限制或者使用更紧凑的数据结构如位图。这道题完美体现了从“暴力模拟”到“优化搜索”的思维跃迁。3.3 试题C阶乘约数数论与质因数分解题目简述定义f(n)为n的约数个数。求f(1!) * f(2!) * ... * f(2020!)的最后几位具体位数看题目要求可能是最后5位或9位。思路解析 这是一道纯数论题。直接计算每个阶乘然后求约数个数是不可行的因为2020!是一个天文数字。 核心知识正整数的约数个数公式。如果一个数N的质因数分解为N p1^a1 * p2^a2 * ... * pk^ak那么它的约数个数d(N) (a11)*(a21)*...*(ak1)。因此问题转化为如何快速得到1!, 2!, ..., 2020!每个数的质因数分解形式 这里需要利用阶乘的质因数分解定理勒让德定理对于质数p在n!的质因数分解中p的指数等于[n/p] [n/p^2] [n/p^3] ...其中[x]表示对x向下取整。解题步骤找出所有质数使用筛法如埃拉托斯特尼筛法找出2020以内的所有质数。计算每个质数p的贡献对于每个质数p计算它在1!, 2!, ..., 2020!中分别的指数。但更高效的方法是我们最终需要的是乘积∏ f(i!)。而f(i!)可以根据i!的质因数分解用约数个数公式算出。 实际上我们可以递推计算。设exp[p][i]表示质数p在i!中的指数。那么有exp[p][i] exp[p][i-1] (i 中质因子p的个数)。 而i 中质因子p的个数可以通过循环除以p得到。计算乘积对于每个i从1到2020计算f(i!) ∏_{p是质数} (exp[p][i] 1)。然后将所有的f(i!)乘起来。由于题目可能只要求最后几位我们可以在乘法过程中始终对10^kk为要求的位数取模避免大数运算。代码实现要点#include iostream #include vector #include cmath using namespace std; const int MOD 100000; // 假设求最后5位 const int MAX_N 2020; int main() { // 1. 筛质数 vectorbool isPrime(MAX_N 1, true); vectorint primes; for (int i 2; i MAX_N; i) { if (isPrime[i]) { primes.push_back(i); for (int j i * i; j MAX_N; j i) { isPrime[j] false; } } } // 2. 计算每个i!的质因数指数二维数组开销大可以优化 // 更优直接计算每个质数p对最终答案的贡献。 // 最终答案 ∏_{i1}^{2020} f(i!) ∏_{i1}^{2020} ∏_{p} (exp_p(i!) 1) // 交换乘积顺序 ∏_{p} [ ∏_{i1}^{2020} (exp_p(i!) 1) ] // 而 exp_p(i!) 是单调不减的。对于每个p我们只需要知道有多少个i使得 exp_p(i!) 等于某个值。 // 实际上exp_p(i!) floor(i/p) floor(i/p^2) ... // 我们可以遍历每个i计算其阶乘的约数个数然后连乘取模。 long long ans 1; for (int i 1; i MAX_N; i) { // 计算 i! 的约数个数 long long divisor_cnt 1; int temp i; // 实际上我们需要基于 i-1! 的结果来计算 i!这里为了清晰独立计算每个i!。 // 更高效的做法是维护一个质数指数数组。 vectorint exp(primes.size(), 0); // 计算i的质因数分解并累加到全局指数数组中这里简化独立计算每个i!的d(i!) // 由于i最大2020我们可以直接对i进行质因数分解然后结合前一个阶乘的结果。 // 但这里展示另一种思路直接计算 i! 的d(i!) // 方法对于每个质数p计算它在i!中的指数e然后 divisor_cnt * (e1) for (size_t idx 0; idx primes.size(); idx) { int p primes[idx]; if (p i) break; int e 0; int power p; while (power i) { e i / power; power * p; // 注意可能溢出可用 long long } divisor_cnt (divisor_cnt * (e 1)) % MOD; } ans (ans * divisor_cnt) % MOD; } cout ans endl; return 0; }注意上述代码中对于每个i都重新计算了i!的质因数分解存在大量重复计算。在竞赛中更高效的做法是维护一个数组cnt[p]记录当前质数p在(i-1)!中的总指数。当计算i!时只需要将i的质因数分解结果累加到cnt数组中然后根据更新后的cnt计算d(i!)。这道题是数论应用的经典例题考察选手对约数个数公式和阶乘质因数分解的掌握程度以及对程序效率的优化意识。3.4 试题D本质上升序列动态规划与去重题目简述给定一个长度不超过200的字符串由小写字母组成要求计算其所有本质不同的上升子序列的数量。这里的“上升”指的是子序列中每个字符的ASCII码严格递增。思路解析 这是一个经典的动态规划计数问题且带有“本质不同”的条件增加了难度。 如果没有“本质不同”的条件我们可以定义dp[i]为以第i个字符结尾的严格递增子序列的个数。那么转移方程为dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。这里的1表示子序列只包含s[i]自身。最终答案是所有dp[i]的和。但是要求“本质不同”上述方法会重复计算相同的子序列。例如字符串“aba”以第二个‘a’结尾的子序列“a”和以第一个‘a’结尾的子序列“a”是同一个。如何处理去重我们需要确保对于同一个子序列只被计算一次。一个常见技巧是在动态规划过程中当遇到相同的字符时只保留最后一次出现时的计数贡献或者从后往前考虑。 更精确的状态定义和转移 定义dp[i]表示以字符i这里‘i’代表26个小写字母之一结尾的、本质不同的严格递增子序列的个数。 我们从左到右遍历字符串的每个字符c对应字母索引idx。 对于当前字符c新的以c结尾的子序列可以由两部分构成子序列只包含它自己1。所有以小于c的字母结尾的子序列后面加上c。即sum(dp[j])其中j是字母索引且j idx。但是如果字符串中后面再次出现相同的字符c直接这样加会重复。关键在于当我们处理到后面这个相同的字符时前面那个字符c所形成的所有子序列作为结尾已经被当前这个c所能形成的子序列所包含了。因为以当前c结尾可以在前面任意一个小于c的结尾子序列后追加这自然也包括了之前那个c所依赖的那些子序列。因此正确的做法是遍历字符串对于每个字符c我们计算new_count 1 sum(dp[j] for j idx)。然后我们将dp[idx]直接更新为new_count而不是累加。因为新的c的出现使得所有以c结尾的子序列被重新计算了旧的值被覆盖从而避免了重复。算法步骤初始化一个长度为26的数组dp全为0。dp[x]表示以字母x结尾的本质不同上升子序列个数。遍历字符串s的每个字符ch计算idx ch - a。计算total 1。这个1代表子序列[ch]。遍历所有字母j从 0 到idx-1total dp[j]。将dp[idx]更新为total。注意是赋值不是累加。遍历结束后答案就是dp[0] dp[1] ... dp[25]。代码实现#include iostream #include string #include vector using namespace std; int main() { string s; // 假设s已读入长度不超过200 cin s; vectorlong long dp(26, 0); // 可能结果很大用long long for (char ch : s) { int idx ch - a; long long new_val 1; // 单独自己作为一个子序列 for (int j 0; j idx; j) { new_val dp[j]; } dp[idx] new_val; // 关键直接赋值覆盖旧值 } long long ans 0; for (long long val : dp) { ans val; } cout ans endl; return 0; }心得与扩展这道题是动态规划去重计数的经典模型。它考察了两个关键点一是对“上升子序列”计数DP基本模型的掌握二是对“本质不同”这一约束条件的处理技巧。dp[idx] new_val这个赋值操作是去重的精髓所在它保证了对于同一个字符后续出现时会基于最新的、包含所有可能前缀的状态进行计算而不会与之前的状态产生重复累加。如果题目改为“非递减”允许相等处理方式又会不同需要仔细思考状态定义。这种题目在笔试面试中也经常出现变体理解其核心思想至关重要。4. 常见问题与实战调试技巧在解决这类算法竞赛题目时除了思路调试和验证能力同样重要。以下是一些常见问题及应对策略4.1 结果错误但样例通过这是最令人头疼的情况。可能的原因和排查手段数据范围与溢出这是最最常见的原因。检查所有中间变量和最终结果的数据类型。int是否足够long long呢在C中两个int相乘即使赋值给long long也会先以int相乘导致溢出。强制类型转换或直接使用long long进行计算。对于模运算乘法前先取模。技巧在编写代码时对于涉及大量计算或可能很大的数养成使用long long的习惯。定义常量typedef long long ll;可以节省时间。边界条件循环的起止点是否正确例如遍历数组是从0到n-1还是1到n动态规划的初始状态dp[0]是否设置正确题目中的“包含端点”是否处理妥当算法逻辑漏洞你的算法是否覆盖了所有情况是否存在某些特殊情况被忽略例如图论中是否有重边、自环字符串是否可能为空对于“本质上升序列”这类题去重逻辑是否完全正确一个有效的调试方法是构造大量的小规模随机数据用你的程序和一个绝对正确但低效的暴力程序如DFS枚举进行对比对拍。输入输出格式蓝桥杯经常要求输出特定格式比如换行、空格、保留小数等。务必仔细阅读输出要求。有时需要输出的是一个整数有时是字符串。4.2 程序超时或内存超限时间复杂度估算在动手前一定要根据数据范围估算最坏情况下的操作次数。例如n10^5O(n²)的算法操作次数约10^10必然超时需要O(n log n)或O(n)的算法。剪枝与优化在搜索DFS/BFS中是否应用了有效的剪枝在动态规划中状态转移是否可以优化如斜率优化、单调队列是否存在不必要的重复计算用记忆化搜索解决数据结构选择频繁查找用unordered_set/unordered_mapO(1)平均而非set/mapO(log n)。需要有序性时才用后者。数组访问比链表快。输入输出加速在C中对于大量数据输入输出使用ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);可以显著提升速度。避免使用endl它刷新缓冲区改用\n。内存使用检查是否开了过大的全局数组特别是二维数组。bool数组可以用bitset或vectorbool位压缩节省空间。递归深度过深可能导致栈溢出可以尝试改成迭代或显式栈。4.3 如何高效备赛与练习分专题突破不要盲目刷题。将算法分为几个大专题基础语法与模拟、枚举与递归、排序与查找、数据结构栈、队列、链表、树、图、动态规划、搜索DFS、BFS、剪枝、数论、字符串等。每个阶段集中攻克一个专题理解其经典模型和变体。精做真题像本文这样对每一道真题进行深度复盘。不仅要写出代码更要理解出题人的意图、考察的知识点、各种解法的优劣以及如何想到最优解。尝试一题多解。建立代码模板库将常用的、无误的算法代码整理成模板例如快速排序、二分查找、并查集、Dijkstra最短路径、线段树等。比赛时可以直接使用节省时间并减少错误。模拟赛环境定期进行限时模拟赛使用过去的真题。适应比赛的压力和节奏练习时间分配策略先易后难有舍有得。善用调试工具和“对拍”学习使用IDE的调试器。编写简单的数据生成器和暴力求解程序与你的优化程序进行“对拍”这是发现隐蔽错误的最强武器。回顾2020年的这套国赛题它没有在算法理论上设置过于高深的障碍而是扎实地考察了选手的基本功、思维严谨性和将知识融会贯通解决新问题的能力。从简单的数位判断到中等的模拟搜索优化再到需要深刻数学洞察力的数论题和精巧状态设计的动态规划题构成了一套层次分明、选拔性强的试卷。对于备赛者而言吃透这样的真题其价值远高于泛泛地刷很多简单题。它告诉你算法竞赛的终点不是背诵模板而是培养一种严谨、优化、创造性的计算思维。这种思维无论是在后续的学习中还是在真正的软件开发工作中都是无比宝贵的财富。