蓝桥杯20×21网格直线计数：一般式与gcd去重实战-北京尧图网络

如果你准备过蓝桥杯C/C软件赛省赛2021年B组那道“20×21整点网格直线计数”的填空题应该不陌生。当年我在赛场上第一眼看到它脑子里想的是这不就是给网格点两两连线然后数一数有多少条吗直到我写出第一版代码看到屏幕上跳出来的数字反复对不上预期才意识到这道题看起来人畜无害实际上考的是去重计数而且是个很容易踩坑的去重。这道题的原题场景是这样的在一个由20×21个整点组成的网格里任意两个不同的整点可以确定一条直线问一共有多少条不同的直线。注意这里说的是“直线”不是“线段”也不是“点对连线”。也就是说如果三个整点恰好在同一条直线上那么这三个点两两组成的三个点对只能算作同一条直线。重复计数是这道题唯一的坑也是唯一的考点。这道题非常适合正在准备蓝桥杯、或者其他算法竞赛的初学者拿来练习。它不考高深的算法也不考复杂的数据结构核心就三件事怎么表示一条直线、怎么把相同直线归一化、怎么保证不重不漏。把这三点想明白代码很容易写出来。反过来如果这三件事没想清楚哪怕枚举点对的循环写得再熟练答案也一定对不上。1. 这道题到底在问什么别急着写代码先看清“直线”的坑1.1 原题场景与真正的约束条件先理清楚网格的规模。这里的“20×21整点网格”指的是横坐标x从0到20一共21列纵坐标y从0到21一共22行。所以网格里全部整点个数是(201)×(211) 21×22 462也就是网格里有462个点。任意两个点能确定一条直线在不考虑任何去重的情况下点对数量是C(462,2)462×461÷2 106491这个数字很容易让人误以为就是答案。但网格里有大量三点共线的情况。最典型的就是水平方向同一行的点全在一条水平线上。第二行如果从左往右有22个整点那这22个点两两能组成C(22,2)231个点对但它们其实都在同一条水平直线上。竖线同理斜线也同理比如一条对角线可能经过很多个网格点。所以题目真正的问题不是“有多少个点对”而是“这些点对都落在哪些直线上”。因此必须把每一条直线用一个唯一的方式表示出来然后数一数不同的表示有多少个。真正需要满足的约束条件有三个直线至少经过两个网格整点但可以经过更多个同一条直线无论由哪两个点得到最终都应该被归一到同一个表示两条完全相同的直线不能重复计数哪怕它们是由不同的点对枚举出来的。1.2 为什么C(462,2)不是答案重复计数的两个来源很多人第一反应是先算总点对数再减去重复。如果只是简单地说“减去三点共线”这个复杂度很大因为一条直线上可能经过4个、5个、甚至更多的点重复次数不是固定值。重复计数其实来自两个层面第一个层面是“同一个点对交换顺序”带来的重复。比如点P和点Q连成一条线那Q和P连成的还是这条线。宏观上看C(462,2)本来就是无序组合枚举的时候如果不注意顺序就会凭空多出一倍。但这个重复好解决写循环时限制x2x1之类就行。第二个层面才是真正的难点三个或更多点共线。比如(0,0)、(1,1)、(2,2)三个点任意取两个点都能确定直线yx。但三个点能产生三个点对分别得到三个“看似不同”的计算过程。如果程序用斜率加截距的方式表示直线只要斜率和截距算出来是一样的那这三个点对自然会合并成一个。问题在于怎么保证“算出来一模一样”而不是“浮点数恰好相等”。所以去重的核心不是人为去数几点共线而是把每条直线转成一个“唯一的、可哈希的身份证”然后交给set一类的容器去重。1.3 这道题适合谁来练、考察什么能力这道题放在省赛B组填空题的位置难度其实不算高但它很典型地反映了蓝桥杯软件赛“重在思维、代码量小”的一贯风格。对备赛的人来说这道题至少能锻炼三个能力把几何对象转化成计算机可以比较的数学表示的能力在枚举方案中主动发现重复、设计去重规则的能力用小规模样例验证程序正确性的习惯。我见过不少准备蓝桥杯的朋友刷题时只爱刷那种“一眼就知道用什么算法”的题遇到这种纯计数题反而容易轻视。实际上像这种填空题代码跑得再快也没用答案对不对完全取决于模型建得准不准。后面我会把每个关键决策的来龙去脉都拆开看完你就能完全理解为什么最终答案是40257。2. 一次搞定去重用“直线一般式”当唯一身份证2.1 把一条直线变成一个三元组(A,B,C)表示一条直线的方式有不少常见的有点斜式y-y1k(x-x1)需要处理斜率无穷大的竖直线斜截式ykxb同样要单独处理竖直线方向向量加截距这个更容易搞混截距的定义稍微一歪就重复一般式AxByC0这个最统一不用区分水平线、竖直线还是斜线。我建议直接用一般式。给定两个整点(x1,y1)和(x2,y2)可以构造出A y1 - y2B x2 - x1C x1×y2 - x2×y1然后把(A,B,C)直接扔进set里。这样做的底气和别人的不一样水平线yk在一般式里表现为A0B≠0C-Bk竖直线xp表现出来是B0A≠0C-Ap。完全不需要分类讨论非常省心。举个例子。用点(0,0)和(1,2)算一遍A 0 - 2 -2B 1 - 0 1C 0×2 - 1×0 0得到(-2,1,0)。如果把两个点反过来用(1,2)和(0,0)算A 2 - 0 2B 0 - 1 -1C 1×0 - 0×2 0得到(2,-1,0)。这两个三元组看起来不一样但它们其实是同一条直线只是整体差了一个负号。所以光构造出(A,B,C)还不够得做归一化也就是2.3节要讲的标准化。2.2 为什么不能用double算斜率精度和符号都是雷有人可能会说用斜率和截距不行吗比如斜截式ykxbk和b都用double存然后扔进set多简单。我刚开始也试过这个方案结果在小网格上勉强能跑但心里始终不踏实。蓝桥杯的样例坐标虽然只有0到21斜率算出来不太会出现特别夸张的浮点误差但浮点数比较天然就有问题。比如理论上两条直线斜率应该相等但一个存成2.0000000000000004另一个存成2.0000000000000000set就会判定为两条直线。等到网格规模变大或者以后做类似题目时坐标范围变成几万、几十万double的误差只会更明显。更麻烦的是竖直线。竖直线的斜率是无穷大的double没法直接表示。虽然可以单独if判断x1x2的情况但这是给代码埋雷只要漏掉一个分支答案就错。所以在这类计数问题里最稳的方式永远是整数运算连浮点数都不要出现。用一般式加gcd约分所有系数都用整数表示既没有精度问题也避开了斜率无穷大的特判。2.3 标准化的三个规则与gcd约分拿到了(A,B,C)之后需要做两步标准化。第一步约分。计算A、B、C三个数的最大公约数g然后把三个数同时除以g。这样做的原因是同一条直线可能由不同点对得到系数会差一个倍数。比如(0,0)和(2,4)确定的直线算出来是(-4,2,0)和(0,0)、(1,2)算出来的(-2,1,0)其实就是同一条因为前者的三个系数是后者的2倍。除以最大公约数之后就都变成了统一的比例。这里有个编程小坑求gcd时三个数里可能有0。C17里的std::gcd支持两个数对gcd(a,0)会返回|a|。所以可以分两步先算ggcd(|A|,|B|)再算ggcd(g,|C|)。不过如果A和B都为0这种情况只有在两个点重合时才会出现枚举时已经跳过了所以不用担心。第二步统一符号。因为(A,B,C)和(-A,-B,-C)表示的是同一条直线得规定一个“正方向”。我习惯的规则是如果A0保持不动如果A0三个数全部取反如果A0则要求B0否则取反。这个规则说白了就是让“第一个不为零的系数为正”。这样两个点交换顺序计算得到的(2,-1,0)和(-2,1,0)就会统一成同一个(2,-1,0)。标准化做完(A,B,C)就等价于一条直线的“身份证号”满足“同一条直线必相同不同直线必不同”的原则。2.4 复杂度分析为什么暴力枚举完全可行很多第一次看到这题的人会担心四个循环枚举两个点会不会超时咱们算一笔账。总点数只有462个。如果两重循环枚举点对最坏情况下点对数量是106491。每个点对需要做一次三元组计算、一次gcd约分、一次符号统一最后插入set。整个过程中set里的元素个数最多也就是答案数量40257个插入和查询的复杂度大约是log(40257)非常小。整体运行时间在普通电脑上就是几十毫秒的量级根本构不成压力。所以这道题完全不需要什么巧妙优化直接暴力枚举再set去重就是最优解。这也是我想强调的一个竞赛观填空题不是越炫越好能确定答案的暴力方案往往是最可靠的选择。3. 完整代码与实测从2×2小网格推到20×213.1 C版核心代码可直接跑下面是我最后提交时用的C代码我加上了注释方便你直接复现。#include bits/stdc.h using namespace std; struct Line { long long A, B, C; // 放进set必须要重载小于号 bool operator(const Line other) const { if (A ! other.A) return A other.A; if (B ! other.B) return B other.B; return C other.C; } }; long long mygcd(long long a, long long b) { if (b 0) return a; return mygcd(b, a % b); } int main() { const int W 20; // x范围0..20 const int H 21; // y范围0..21 setLine lines; for (int x1 0; x1 W; x1) { for (int y1 0; y1 H; y1) { for (int x2 0; x2 W; x2) { for (int y2 0; y2 H; y2) { if (x1 x2 y1 y2) continue; long long A y1 - y2; long long B x2 - x1; long long C 1LL * x1 * y2 - 1LL * x2 * y1; // gcd约分 long long g mygcd(abs(A), abs(B)); g mygcd(g, abs(C)); A / g; B / g; C / g; // 统一符号第一个非零系数为正 if (A 0 || (A 0 B 0)) { A -A; B -B; C -C; } lines.insert({A, B, C}); } } } } cout lines.size() endl; return 0; }这段代码在本地跑出来最终输出是40257。当年官方和各大题解给出的标准答案也是40257。如果你之前看到过别的数字那大概率不是题目数据有问题而是去重逻辑里有一个细节没处理好。3.2 Python版对照实现如果你平时用的是Python下面的代码也能跑出同样结果。Python里元组天然支持放入set代码会显得更短一些。from math import gcd W, H 20, 21 lines set() for x1 in range(W 1): for y1 in range(H 1): for x2 in range(W 1): for y2 in range(H 1): if x1 x2 and y1 y2: continue A y1 - y2 B x2 - x1 C x1 * y2 - x2 * y1 g gcd(gcd(abs(A), abs(B)), abs(C)) A // g B // g C // g if A 0 or (A 0 and B 0): A, B, C -A, -B, -C lines.add((A, B, C)) print(len(lines))python版唯一的缺点就是跑得比C慢一点但在这个规模下影响不大结果还是40257。3.3 小网格验证3×3点阵手算等于20条如果只跑出来一个40257心里还是不够踏实那一定要做小规模验证。把W改成2、H改成2也就是3×3共9个点的点阵再用同一套代码跑一下。这样做的原因是3×3点阵规模小到可以手算一旦手算结果和程序结果对上了就说明去重逻辑是对的。9个点两两组合有C(9,2)36个点对。再看三点共线的情况水平线3条每条上有3个点每条产生C(3,2)3个点对但只算1条线所以每条减去2个重复点对竖直线3条同样每条减去2个重复点对两条对角线每条3个点也各减去2个重复点对。总共减去的重复点对数是(332)×216。36减16正好是20条。程序把W和H改成2之后跑出来的结果就是20。这一步验证通过才敢放心跑完整的数据规模。3.4 跑出40257之后如何确认它不是巧合小网格验证通过之后还可以再多做一层检查把程序里的set去掉只输出点对数看看是不是等于106491。这个数字能侧面确认网格规模和枚举范围没有写错。如果发现点对数不对那基本是循环边界写错了。比如有人会把x范围写成0到20、y范围也写成0到20那总点数就变成了21×21441个点对数会少一大截最终答案当然也不对。另外可以把标准化的符号规则反过来比如强制A0再跑一遍。如果代码正确输出应该还是40257因为符号翻转只影响三元组的具体写法不影响去重结果。如果输出变了说明符号规则内部有漏洞大概率是漏了“A0且B0”的重合点判断或者gcd求出了问题。4. 我在刷这道题时踩过的坑排查与避坑实录4.1 用斜率截距的double方案为什么会翻车我第一次写这道题用的就是pairdouble,double一个存斜率k一个存截距b。当时觉得坐标最大才21double精度绰绰有余。结果程序跑出来是40000出头但心里总觉得不太对。后来排查了一下最主要的麻烦来自竖直线。x坐标相同的两个点斜率是无穷大double没法存。我当时的补救办法是把斜率为无穷大的情况单独用一个标志位表示比如斜率存成1e9这样的“伪无穷大”。这个办法在小范围样例里碰巧没出问题但本质上是个很脆弱的方案。另外一个隐患是如果网格规模变大某些斜率的差值会小于double的精度阈值set会把两条本来不同的直线误判成同一条。虽然本题坐标小实际没触发但写代码不能靠运气。所以后来果断改成整数一般式再也没为精度问题操过心。4.2 竖直线和水平线的特殊处理其实根本不用处理我最早还犯过一个更傻的错误写分支特判竖直线和水平线。竖直线单独存一种类型水平线单独存一种类型斜线再按斜率存。这样做的问题在于类型一多set里的比较规则就变得复杂稍微一个分支忘写就会导致重复计数。直到我换成一般式之后才发现水平线和竖直线在一般式里根本没有任何特殊性。水平线的A0竖直线B0和斜线一样都是整数三元组放进同一个set即可。这也算是我在实际做题中体会到的“把几何问题代数化”的好处。所以我的建议是遇到直线计数问题不管有没有水平线和竖直线直接统一用一般式不要再去做分类讨论。分类越多出错概率越高。4.3 符号不统一导致的重复与漏算还有一个很容易忽略的细节符号规则。如果只做gcd约分不做符号统一那么同一条直线可能会以两个三元组出现。比如(2,-1,0)和(-2,1,0)这俩是同一件事但set会当成两个元素。最终答案就会偏大。反过来如果符号统一规则写得不对也可能把两条不同的直线误合并成一条。比如规定“B0且A0”这样是不行的因为当A和B都大于0时是正常但当A0、B0时既满足不了A0翻转又满足不了B0翻转会产生矛盾。最稳妥的规则就是前面写的A0若A0则B0。确保第一个不为零的系数为正其他都不用管。如果你想验证自己的符号规则是否正确可以故意在枚举点对时不做“x1x2”之类的顺序限制而是让所有点对都枚举一遍。如果代码正确set依然会去重得干干净净最终答案不变。这也是一种检验方式。4.4 蓝桥杯环境与代码提交的实操细节很多人在本地跑得好好的一到比赛环境就开始出问题。这里有几个细节经验分享蓝桥杯省的测评环境未必支持C17所有特性。比如std::gcd在C17才有如果不确定环境版本就自己手写一个gcd函数最保险。long long乘法。计算Cx1y2-x2y1时x1和y2都可能是两位数相乘最大也就几百int够用。但为了扩展性建议全用long long养成习惯。如果是在填空题里不需要提交代码只需要填最终答案。那你完全可以在本地用自己熟悉的语言写一个暴力程序跑出答案填上去就行。不要觉得暴力丢人填空题的核心是答案正确。4.5 这类填空题的通用做题套路经历了这道题之后我总结了一个比较通用的填空题做题流程先手算或设计一个最小规模的样例比如2×2网格摸清问题的重复规律然后写最直白的暴力程序把结果跑出来再用第二个样例验证程序正确性确认无误后改成题目要求的规模跑最终答案。这个流程听着简单但很实用。很多填空题不是难在最后的答案而是难在中间某个去重条件想漏了。如果一开始就直接跑20×21的大数据错了也不知道错在哪。从小样例开始错了能快速定位这是最省时间的做法。5. 这道题还能怎么延伸从比赛到日常5.1 扩展到N×M网格的通用解法这道题的代码稍微改动两个变量就能变成通用解法。比如以后遇到“在N×M的整点网格中有多少条不同的直线”只需要把W和H换成对应数值其余代码不用动。唯一的复杂度考量是当N和M变得很大时点对数量会达到O(N²M²)级别暴力枚举可能变成几十亿次跑不动。这时候可以用一个更优雅的数学方法枚举互质方向向量(dx,dy)对每个方向统计直线数量。核心思想是把方向标准化成互质形式然后对网格内的每个点计算dxy-dyx的值不同的值对应不同的平行直线用set统计个数即可。这个方法把复杂度降到O(NM×方向数)适合更大规模的变体。不过对于蓝桥杯这道原题暴力的10万点对完全够用没必要升级。5.2 同一个思维在其他算法题里的变体去重计数这个思路在算法题里太常用了。比如求一个点集中所有点对之间的不同距离数量就可以用距离平方去重比如求所有子串里不同子串的数量本质也是把重复的表示合并再比如几何题里求不同斜率数量也是gcd约分加set。这道题的启发在于当你在处理“由多个元素能生成同一个结果”的问题时首要任务不是数生成过程次数而是找到一个稳定的结果表示再做集合去重。这个思维模式一旦建立了很多看起来复杂的计数题都能快速转化为“构造唯一表示set”的套路。5.3 给正在备赛的朋友几句实在话写到最后说点题外的。很多人觉得蓝桥杯C/C软件赛的填空题不如编程大题有分量花时间抠这种题不值当。但我看到最近有人讨论第十七届蓝桥杯嵌入式/单片机的备赛包括蓝桥杯单片机的国赛客观题其实很多模块设计、状态判重的问题和这道网格去重题的底层逻辑是相通的。这道题教会我的最深的一课是竞赛里越是不起眼的题目越要稳扎稳打。每次看到“这不就暴力一下吗”的题我都提醒自己多看一眼有没有隐藏的重复计数、有没有边界条件、有没有浮点陷阱。20×21网格直线计数这道题表面上是一个简单的枚举计数实际上是一块很好的“试金石”能试出你对去重建模的敏感度。至少到现在我做新题时还会偶尔想起这组数字106491个点对归一化之后是40257条直线。

蓝桥杯20×21网格直线计数：一般式与gcd去重实战

相关推荐

G-Helper 完整指南：免费轻量控制华硕笔记本性能、风扇与 GPU 模式

写出 AI Agent 能读懂的 DESIGN.md：用 73 份现成设计系统文档生成品牌同款 UI 的完整指南

STM32双轮平衡循迹小车：从PID控制到姿态解算的完整技术链路

更多资讯

零门槛上手Maestro录制:4步生成第一个完整的测试视频

免费管好全部 IT 资产：开源资产管理系统 Snipe-IT 落地实操

GHelper 免费开源：5 分钟配好华硕笔记本的性能控制与风扇曲线

基于STM32F4的机房巡检机器人环境监测系统设计与实现

如何 30 分钟本地部署 Duix-Avatar：离线 AI 数字人完整教程

Golang-Gin 框架写的免杀平台，内置分离、捆绑等多种BypassAV方式

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？