蓝桥杯Day1入门题精讲：从枚举边界到并查集实战

1. 开篇：从“打卡”到“破题”，一个老选手的Day1复盘心法

又到了蓝桥杯的备赛季，看着各种“31天冲刺打卡”的Flag立起来，我仿佛看到了当年那个对着屏幕、从Day1开始一头雾水的自己。很多同学拿到一份题解，可能只关心“答案是什么”，敲完代码通过测试就匆匆标记“已完成”，然后陷入“Day2、Day3……”的循环，却忽略了最宝贵的破题训练。今天，我们不聊高深的算法，就扎扎实实地复盘“Day1”的几道经典入门题。我的目的不是给你一份可以Ctrl+C/V的代码，而是想和你一起，像下棋复盘一样，把解题的“第一性原理”和那些新手最容易踩进去的“思维坑”给挖出来。你会发现，吃透一道简单题的价值，远胜过盲目刷十道难题。

无论是“门牌制作”的枚举边界，还是“既约分数”的算法选择，亦或是“蛇形填数”的规律寻找，这些题目都精准地卡在了从“会编程”到“会竞赛”的转折点上。它们考察的不仅是语法，更是对问题本质的洞察力和将抽象描述转化为精确逻辑的能力。接下来，我会带你一道一道拆解，分享我在反复调试和教学过程中总结出的“条件反射式”的思考路径。相信我，这套心法练熟了，后面29天的路会好走很多。

2. 真题拆解一：“门牌制作”中的边界意识与整数处理陷阱

这道题题意很直白：从1到2020，统计所有这些数中，数字‘2’一共出现了多少次。比如，数字22就算出现了两次。很多新手一看，觉得这太简单了，不就是遍历+数‘2’吗？但恰恰是这种“简单”题，最容易在细节上翻车。

2.1 暴力枚举法的正确打开方式

最直接的思路就是模拟。从1循环到2020，对每一个数i，我们需要提取它的每一位，判断是否为2。

核心实现逻辑：

count = 0 for i in range(1, 2021): # 注意Python的range是右开区间，所以要写到2021 num = i while num > 0: digit = num % 10 # 取出个位数 if digit == 2: count += 1 num //= 10 # 去掉个位数，继续检查下一位 print(count)

或者用字符串转换，更直观：

count = 0 for i in range(1, 2021): count += str(i).count('2') print(count)

> 注意：这里第一个坑就是循环的边界。range(1, 2021)才是包含2020的。如果你写成了range(1, 2020)，那就少算了2020这个数里的一个‘2’。在竞赛中，因为边界错误丢掉整道题的分数是最可惜的。我的习惯是，看到“从A到B”，立刻在脑子里或草稿纸上标出区间：[A, B]是闭区间，对应代码就是range(A, B+1)。

2.2 深入一步：数学方法的思维体操

除了编程，我们能不能心算或者找到规律？这锻炼的是数位统计的思维。我们可以按位（个位、十位、百位、千位）来考虑‘2’出现的次数。

• 个位：每10个数出现一次‘2’（2,12,22,...）。1到2020有多少个完整的10循环？2020 // 10 = 202个。每个循环贡献1个‘2’，所以是202次。再看余下的部分：2020 % 10 = 0，余下的0个数（2021到2020？不，我们只到2020）个位没有额外的‘2’。所以个位总计202次。
• 十位：每100个数，十位上是‘2’的情况会出现10次（20-29）。2020 // 100 = 20个完整百循环，贡献 20 * 10 = 200次。再看余下2020 % 100 = 20，这20个数（2001到2020）中，十位是‘2’吗？看十位数字，这20个数是00,01,...,19,20？不对，应该是2001到2020，它们的十位分别是0,0,...,1,2。只有最后一个数2020的十位是2，且个位是0，在区间内。所以额外贡献1次。十位总计201次。
• 百位：每1000个数，百位是‘2’的情况会出现100次（200-299）。2020 // 1000 = 2个完整千循环，贡献 2 * 100 = 200次。余下2020 % 1000 = 20，这20个数（2001到2020）的百位都是0（因为都在2000-2019和2020这个区间，2000-2019百位是0，2020百位是0），没有额外贡献。百位总计200次。
• 千位：只有1000-1999和2000-2020。千位是‘2’的只有2000-2020这21个数。所以千位总计21次。

总和 = 202 + 201 + 200 + 21 = 624。

> 实操心得：对于入门题，用编程暴力验证数学推导是一个极好的习惯。写完循环程序后，输出结果（624），再和你手算的结果对比。如果一致，说明你的数位分析逻辑是正确的；如果不一致，就回去检查你的“余下部分”分析，这里是手算最容易出错的地方。这个过程能极大地强化你对数字和区间关系的理解。

3. 真题拆解二：“既约分数”与算法基石：辗转相除法的本质

题目：如果一个分数的分子和分母的最大公约数是1，则称为“既约分数”。请问，分子和分母都是1到2020之间的整数，有多少个既约分数？

这道题是经典的“欧拉函数”概念的二维扩展。不是求单个数的互质个数，而是求所有数对(i, j)中互质的对数。暴力二重循环判断是可行的，但这里的关键在于：如何高效、准确判断两个数互质？这直接引出了我们编程竞赛中最重要的算法基石之一——最大公约数（GCD）算法。

3.1 为什么是辗转相除法（欧几里得算法）？

判断互质，即判断gcd(i, j) == 1。求gcd的方法有很多，为什么我们首选辗转相除法？

1. 效率极高：它的时间复杂度是O(log min(a,b))，对于1到2020的范围，比试除法快了几个数量级。
2. 实现简洁：递归或迭代只需几行代码，不易出错。
3. 理解深刻：它基于一个核心定理：gcd(a, b) = gcd(b, a % b)。直到余数为0时，除数就是最大公约数。

迭代实现（推荐，避免递归深度问题）：

def gcd(a, b): while b != 0: a, b = b, a % b return a

递归实现（更直观）：

def gcd(a, b): return a if b == 0 else gcd(b, a % b)

有了gcd函数，主程序就非常简单：

count = 0 for i in range(1, 2021): for j in range(1, 2021): if gcd(i, j) == 1: count += 1 print(count)

3.2 优化与思考：对称性与去重

上面的代码会进行2020*2020约400万次循环和gcd计算，在现代计算机上可以接受。但我们可以思考更多：

• 分数i/j和j/i算两个吗？题目通常默认i/j，即分子分母有序，所以1/2和2/1是不同的。我们的二重循环正好覆盖了所有有序对。
• 能否利用对称性减半计算？如果题目问的是“组合”而不是“有序对”，即认为i/j和j/i相同（且i不等于j），那么总数会不同。但本题明确是“分数”，且未说明相等，通常按有序对处理。
• 更优的数学方法？这实际上可以转化为求sum_{i=1}^{n} sum_{j=1}^{n} [gcd(i,j)==1]，可以用数论中的莫比乌斯反演来优化到O(n log n)甚至O(n)，但对于2020这个规模，暴力足矣。了解其数学背景能为后续学习更高级的数论知识打下基础。

> 踩坑记录：我曾见过有同学写gcd函数时，没有处理a<b的情况。实际上，欧几里得算法不需要预先判断大小。例如gcd(8,12)：第一轮a=8,b=12，计算a%b=8，然后a=12, b=8，自动完成了交换。所以上面的实现是完备的。这是理解算法鲁棒性的一个小例子。

4. 真题拆解三：“蛇形填数”的规律挖掘与坐标映射

这道题描述了一个蛇形填充的数字矩阵，要求找出第20行第20列的数。矩阵的填充方式如下图所示（以5x5为例）：

1 2 6 7 15 3 5 8 14 16 4 9 13 17 22 10 12 18 21 23 11 19 20 24 25

（注：实际题目可能方向略有不同，但蛇形“Z”字形填充的核心不变）

直接模拟填充整个矩阵直到第20行第20列，对于计算机来说很简单，但竞赛中可能限制内存或时间（虽然本题规模小），更重要的是，这题考察的是观察规律和建立数学模型的能力。

4.1 模拟法：最稳妥的保底策略

首先，我们确保能用代码模拟出来。关键在于理清填充方向的变化规律。 通常，填充沿两条对角线方向进行：从左上到右下（称为“方向1”），和从左下到右上（称为“方向2”），两种方向交替进行，当碰到边界时转向。

模拟步骤：

1. 初始化一个足够大的二维数组（如40x40），所有值为0。定义当前坐标(x, y)，初始为(0,0)或(1,1)（根据习惯）。
2. 定义当前数字num=1，定义当前方向dir（例如1表示从左上到右下，-1表示从左下到右上）。
3. 在一个大循环中（while num <= 需要填充的最大位置值）：
   • 将num填入当前(x, y)。
   • 根据dir计算下一个目标位置(nx, ny)。
   • 如果下一个位置超出矩阵边界或者已经被填充过（值不为0），则需要改变方向dir = -dir，并根据当前所在边界重新计算下一个合法位置。这是逻辑最易错点。
   • 更新(x, y)到下一个位置，num++。
4. 模拟完成后，直接输出matrix[19][19]（如果从0开始索引）或matrix[20][20]（如果从1开始索引）。

> 实操心得：模拟法的调试核心是可视化。对于小规模（比如5x5），一定要把每一步填充后的矩阵打印出来，和你手画的图对照。常见的错误在于边界转向的逻辑，比如在矩阵左上角向右下填充时，碰到右边界应该向下转向，还是碰到下边界应该向右转向？必须结合题目示例明确。把转向的几种情况（碰右边界、碰下边界、碰上边界、碰左边界、以及碰已填充位置）用if-else理清楚。

4.2 数学规律法：快速求解的钥匙

对于第n行第n列（对角线上的点），往往有简洁公式。观察上面5x5矩阵的对角线：1, 5, 13, 25, ... 寻找规律：

• 位置(1,1): 1
• 位置(2,2): 5 = 1 + 4
• 位置(3,3): 13 = 5 + 8
• 位置(4,4): 25 = 13 + 12
• 加数4, 8, 12...是一个公差为4的等差数列。

因此，a[n] = a[n-1] + 4*(n-1)，其中a[1]=1。 推导通项公式：a[n] = 1 + 4*(1 + 2 + ... + (n-1)) = 1 + 4 * (n-1)*n / 2 = 1 + 2*n*(n-1)。 验证：n=1时，1+210=1；n=2时，1+221=5；n=3时，1+232=13。符合。 所以第20行第20列的数：1 + 2*20*19 = 1 + 760 = 761。

> 核心技巧：遇到这种找规律题，一定要从特殊位置（如对角线、边界）入手。先通过模拟或手算得到前几个值，然后列出数列，观察差值（一级差、二级差）。如果二级差是常数，那通项公式一定是二次的。本题中，数列1,5,13,25,...的一级差是4,8,12,...，二级差是常数4，所以通项是an^2+bn+c的形式，代入三个点解方程组即可。掌握这个技巧，很多数列题都能秒杀。

5. 真题拆解四：“七段码”与抽象建模：并查集实战

“七段码”题目通常描述：一个数码管的7个段（a,b,c,d,e,f,g）可以发光，选择其中若干个段发光，要求所有发光的段必须连成一体（连通），求有多少种合法的发光组合。这是一道经典的组合数学+图论连通性判断的题目。

5.1 问题抽象：从物理段落到图模型

第一步也是最关键的一步是抽象建模。我们把7个段看成7个顶点。如果两个段在物理上是相邻的（共用端点），我们就在它们对应的顶点之间连一条边。这样就得到了一个“七段码图”。

这个图的结构是固定的（像一个“日”字形）：

a f b g e c d

边的关系：a-b, a-f, b-g, b-c, f-g, f-e, g-c, g-d, e-d, e-c, c-d。（根据具体题目图示可能微调，但原理不变）

问题转化为：在一个给定的无向图中，有多少个非空顶点子集，使得该子集对应的导出子图是连通的。

5.2 暴力枚举与连通性校验

7个段，每个段有“选”或“不选”两种状态，总共2^7 = 128种子集（去掉全不选的1种，剩127种）。对于计算机来说，枚举127种情况并检查每种情况是否连通，是完全可行的。

核心步骤：

1. 枚举所有子集：可以用0到127的二进制表示来枚举，二进制位为1代表选择该段。
2. 构建子图：对于每一种枚举状态，根据二进制位找出被选中的顶点集合。
3. 连通性判断：
   • BFS/DFS：从任意一个被选中的顶点出发，进行搜索，标记所有能访问到的被选中顶点。最后检查是否所有被选中的顶点都被标记了。这是最直观的方法。
   • 并查集（Disjoint Set Union, DSU）：这是更高效、更竞赛化的方法。初始化每个被选中的顶点为自己的父亲。然后遍历所有边（根据之前建立的边列表），如果这条边连接的两个顶点都被选中，就用并查集的union操作把它们合并到同一个集合。最后检查所有被选中的顶点是否在同一个集合里。

并查集实现示例：

# 并查集模板 class DSU: def __init__(self, n): self.parent = list(range(n)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx != ry: self.parent[ry] = rx # 主逻辑片段 edges = [(0,1),(0,5),(1,6),(1,2),(5,6),(5,4),(6,2),(6,3),(4,3),(4,2),(2,3)] # a-g映射为0-6 total = 0 for state in range(1, 1<<7): # 枚举1到127 selected = [i for i in range(7) if (state >> i) & 1] if not selected: continue dsu = DSU(7) # 只初始化被选中的点？这里有个技巧：我们可以只关心被选中的点是否连通。 # 更简单的做法：遍历所有边，如果边的两端点都被选中，就合并。 for u, v in edges: if ((state >> u) & 1) and ((state >> v) & 1): dsu.union(u, v) # 检查所有被选中的点是否属于同一个集合 root = dsu.find(selected[0]) if all(dsu.find(x) == root for x in selected): total += 1 print(total)

> 深度解析：为什么这道题值得深究？因为它完美结合了二进制枚举和并查集这两个竞赛高频考点。二进制枚举是处理小型组合问题的利器，而并查集是处理动态连通性问题的标准工具。通过这道题，你可以深刻理解“状态压缩”和“图连通性”的检查方法。我建议你不仅要写出代码，还要手动验证几个简单情况（比如只选一个段，选两个相邻的段，选两个不相邻的段），确保你的连通性判断逻辑是正确的。

6. Day1复盘总结：超越“通过”的四个思维习惯

做完这四道题，如果只是得到了四个答案，那收获就太有限了。Day1的真正价值，在于建立正确的解题思维习惯。我来分享一下我从这些基础题里提炼出的，贯穿整个竞赛生涯的四个习惯：

习惯一：边界与特例的“条件反射”。看到循环、数组下标、区间描述，大脑就要自动拉响警报：“边界处理好了吗？”、“零值、负值、最大值怎么处理？”、“题目给的例子覆盖了所有情况吗？”。像“门牌制作”的range(1, 2021)，就是这种条件反射的练习。

习惯二：从暴力到优化的“思维跃迁”。永远先想最直观、最笨的办法（暴力枚举、模拟），让它正确运行。这是你的“保底分数”和“调试基准”。然后，再观察数据规模、寻找数学规律、应用经典算法。就像“既约分数”，先写出二重循环，你才能安心地去思考欧拉函数；“蛇形填数”，先模拟出小矩阵，才能验证你找到的数学公式。不要一开始就追求奇技淫巧。

习惯三：将具象问题抽象为模型的“翻译能力”。这是区分普通程序员和算法选手的关键。“七段码”本质上不是关于数码管，而是关于图连通性和子集枚举。训练自己剥离问题表面的“故事”，看到背后的数据结构（图、树、数组）和算法需求（搜索、动态规划、并查集）。每道题都问自己：这本质上是在考什么？

习惯四：严谨的自我验证与调试。不要相信一次提交。用你的程序去计算题目中给出的样例。如果可能，构造更多边缘数据（比如最小输入、最大输入、有特殊关系的输入）。对于“蛇形填数”，手动画出5x5的矩阵和程序输出的5x5矩阵对比；对于“七段码”，手动列出所有只选1段、2段的情况，看程序结果是否合理。调试能力比写代码能力更重要。

Day1的这几道题，就像木工的基本功：刨、锯、凿。看起来简单，但每一道都直指一个核心思维。把这些习惯内化，在接下来的打卡中，你才不会陷入“刷了忘，忘了刷”的循环，而是能真切地感受到自己解题“手感”的提升。记住，冲刺不是匀速跑，而是一开始就把姿势练对。