如果你准备过CCF CSP认证应该对这两道题不陌生稀疏向量、回收站选址。它们分别出现在第19次和第18次认证的第二题风格高度相似——读题不难、代码不长但一不留神就丢分。恰好它们踩中了同一个核心考点面对超大范围的数据上亿的向量维度、正负十亿的坐标你怎么把存储和查找组织得又快又稳。这篇就把两题拆开讲透顺便聊聊为什么“第二题”是认证里性价比最高的100分。1. 这两道题在认证里是什么地位1.1 题号与场次对照CCF CSP认证的题目编号有个规律前两位是年份中间两位是当年第几次认证最后一位是题号。这两题的官方信息如下题目题号场次题目类型核心知识点稀疏向量202006-2第19次计算题双指针 / 哈希判存回收站选址201912-2第18次模拟题坐标集合判存从编号能看出来它们都在“第二题”的位置上。CSP认证的题目难度曲线非常固定第一题是送分题只要读懂题就能拿满第二题开始上强度但强度有限属于“稍微动点脑子就能AC”的档位从第三题开始才是真刀真枪的算法与实现综合题。1.2 为什么第二题是“分水岭”很多考过CSP的人都有同一个感受200分是一道大坎。为什么是200分因为第一题100分基本必拿第二题如果也能AC总分就站稳200了。第三题通常来不及完整写出来或者写出来也容易因为细节过多而拿不到满分。但也正因为第二题处在“送分和拉分”的临界位置它成了翻车高发区。我见过不少同学第一题10分钟AC第二题卡了一个半小时最后总分只有100多。原因无非几类被数据范围唬住不知道用什么数据结构看懂了题但实现时边界条件写错复杂度估算失误简单写法直接超时输入输出处理不当在IO上白白丢分。稀疏向量和回收站选址恰好把这些问题各暴露了一遍。前者教你如何在“维度极大但非零极少”的场景下高效求内积后者教你如何在“坐标范围极大但点数量有限”的场景下做邻域判断。把这两题吃透第二题这个档位的套路你就掌握了八成。2. 稀疏向量读懂“稀疏”才不会开错数组2.1 题目到底在问什么题目给的是两个n维向量u和v但n可以大到10的9次方上下显然不可能开一个长度为n的数组。好在输入只给出各自非零的项第一行给三个数n、a、b接下来a行是u的非零下标和值再接下来b行是v的非零下标和值。两组输入都按下标升序排列最后要求计算两个向量的内积。内积的定义很简单只有相同下标位置的数值才相乘再把所有乘积加起来。问题在于这两个向量绝大部分位置都是0如果老老实实遍历1到n哪怕只遍历到10的8次方都会超时更别说10的9次方了。所以这道题真正的考点是怎么用非零项列表高效计算内积。这里先厘清一个容易混淆的地方。两个向量各自有a和b个非零项如果某个下标只在u里出现、不在v里出现那它对内积的贡献是0。真正有贡献的是那些“在两个输入里同时出现且下标相等”的位置。换句话说你要找的是两个有序列表的“交集”。2.2 双指针为什么是这个题的正解因为两个列表都按下标升序排列这给了我们一个天然的线索用双指针像归并排序合并有序序列那样同步扫描。具体做法是指针i指向u的第一个非零项指针j指向v的第一个非零项。比较下标如果u[i]的下标小于v[j]的下标说明u当前这个下标在v里找不到i往后移如果u[i]的下标大于v[j]的下标说明v当前这个下标在u里找不到j往后移如果下标相等这就是一次有效贡献把两个值相乘累加到答案里然后i和j都往后移。整个过程每个元素最多被扫一次复杂度是O(ab)空间上除了存输入以外不需要额外的大结构。有人会问用哈希表先存u的所有非零项再遍历v查表不也一样能做确实能哈希做法时间复杂度也是O(ab)而且在索引不是升序的时候是唯一简单方案。但双指针有两个优势一是完全不用处理哈希表的常数开销和冲突问题二是代码更短更不容易出错。既然题目保证升序那就别舍近求远。2.3 C与Python参考实现C版本用pair存下标和值#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, a, b; cin n a b; vectorpairint, long long u(a), v(b); for (int i 0; i a; i) { cin u[i].first u[i].second; } for (int i 0; i b; i) { cin v[i].first v[i].second; } long long ans 0; int i 0, j 0; while (i a j b) { if (u[i].first v[j].first) { i; } else if (u[i].first v[j].first) { j; } else { ans u[i].second * v[j].second; i; j; } } cout ans \n; return 0; }这里有个细节第一行的n读完以后并没有在代码里用到。它只是告诉你向量总体维度有多大提醒你不要开数组。这是这类“大维度稀疏输入”题的常规套路n往往只是吓唬人的。Python版本用sys.stdin.buffer加速输入import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) pos 0 n, a, b data[0], data[1], data[2] pos 3 u [] for _ in range(a): idx, val data[pos], data[pos 1] pos 2 u.append((idx, val)) v [] for _ in range(b): idx, val data[pos], data[pos 1] pos 2 v.append((idx, val)) ans 0 i j 0 while i a and j b: if u[i][0] v[j][0]: i 1 elif u[i][0] v[j][0]: j 1 else: ans u[i][1] * v[j][1] i 1 j 1 print(ans) if __name__ __main__: main()Python的大整数天然不会溢出所以这里不需要像C那样操心long long的问题。不过Python写起来更简洁但运行速度慢遇到10的5次方量级的输入时用buffer读取就非常关键了。2.4 容易踩的坑类型、指针、剩余元素这道题虽然代码短但坑一个比一个隐蔽。第一个坑是类型。C里value可能很大两个value相乘再累加用int承接必炸。我建议直接用long long存value和ans别赌数据大小。真实考场上因为类型溢出白丢100分的人每年都有。第二个坑是双指针的推进逻辑。有些同学在“下标相等且累加完”以后只移动一个指针导致同一个元素被重复计算结果偏大。记住相等时两个指针都必须前进。第三个坑是循环结束后的处理。有些同学习惯性地在循环后面再写一段处理剩余元素的代码比如“如果i还没走完就继续……”。这个题不需要。循环退出的条件是i和j至少有一个越界此时剩下的元素下标必然不会在另一个列表里出现对内积没有贡献。多写这段反而是错。第四个坑是误以为n是有效输入。n本身不参与计算但它决定了你的第一反应。看到n上亿就立刻明白数组法死刑只能用非零项列表。3. 回收站选址别让“坐标范围”骗了你3.1 题目背景与候选条件这道题结构也很清晰。平面上有n个已知坐标的垃圾点要从这些垃圾点里选一些位置建回收站。选中的条件有两个该位置本身有垃圾该位置的上、下、左、右四个相邻位置都有垃圾。满足条件的点才能成为候选回收站然后给它评分看它的左上、右上、左下、右下四个对角方向上分别有多少个位置有垃圾有几个就算几分分数范围是0到4。最后按分数0、1、2、3、4统计数量各输出一行。注意一个关键逻辑候选点本身必须来自输入的垃圾点列表。题目不是问“地图上哪些位置可以建站”而是“在这些已有的垃圾点里哪些适合建站”。所以遍历对象就是输入的n个点。另外上下左右四个方向是“都有垃圾”不是“至少有一个”。我见过有人把条件写成四方向任意一个存在就合格那是另外一个题目了。四个方向必须同时满足缺一个都直接淘汰。3.2 为什么不能开二维数组这道题坐标范围很容易让人犯迷糊x和y的绝对值可以到10的9次方。如果按坐标范围开二维数组内存直接爆炸连编译都过不了。正确思路是离散化判存不需要知道地图上所有格子有没有垃圾只需要回答“某个具体坐标是否是垃圾点”这个问题。n本身只有10的5次方量级把n个点的坐标放进一个集合每次查一个坐标是否存在用平衡树或哈希都是O(n log n)或O(n)的复杂度。这种模型在算法题里太常见了。一个超大平面里只撒了有限几个点你要做的所有判断都只围绕这些点展开那就把点存成可哈希的对象然后用集合解决一切。不要被坐标范围吓到它不是让你去遍历整张地图而是告诉你怎么做一定会超时。有人会问C里能不能用unordered_map存pair标准库没有给pairint,int提供哈希得自己写哈希函数。现场写那个东西容易写错又慢又麻烦。直接用setpairint,int就行set的查询是O(log n)n1e5时完全够用代码还短。3.3 参考实现C版本用set存坐标#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int points(n); setpairint, int s; for (int i 0; i n; i) { int x, y; cin x y; points[i] {x, y}; s.insert({x, y}); } int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int sx[4] {1, 1, -1, -1}; int sy[4] {1, -1, 1, -1}; int ans[5] {0}; for (auto p : points) { int x p.first, y p.second; bool ok true; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (s.count({nx, ny}) 0) { ok false; break; } } if (!ok) continue; int score 0; for (int k 0; k 4; k) { int nx x sx[k]; int ny y sy[k]; if (s.count({nx, ny}) 0) { score; } } ans[score]; } for (int i 0; i 5; i) { cout ans[i] \n; } return 0; }Python版本逻辑一样代码更短import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) n data[0] points set() order [] pos 1 for _ in range(n): x, y data[pos], data[pos 1] pos 2 points.add((x, y)) order.append((x, y)) dx [1, -1, 0, 0] dy [0, 0, 1, -1] sx [1, 1, -1, -1] sy [1, -1, 1, -1] ans [0] * 5 for x, y in order: ok True for k in range(4): if (x dx[k], y dy[k]) not in points: ok False break if not ok: continue score 0 for k in range(4): if (x sx[k], y sy[k]) in points: score 1 ans[score] 1 sys.stdout.write(\n.join(map(str, ans)) \n) if __name__ __main__: main()对拍一下这几段代码逻辑是完全一致的先判上下左右再算对角分数最后按分数落桶。3.4 现场易错点这道题真正的失分点不在算法而在实现细节。第一个坑是方向数组写错。上下左右和四个对角是两组不同的方向增量混在一起就会出大问题。建议用两组数组分别存一组dx/dy管上下左右一组sx/sy管对角不要省事写在一个循环里。第二个坑是合格判定提前跳过。一旦发现某个正方向不存在当前点直接不可能是候选回收站应立刻break结束判断并continue到下一个点。别把所有四个方向都检查完再统一判断那样逻辑容易乱也容易把“某个方向不存在”和“不存在也能评分”混淆。第三个坑是输出顺序。答案是按分数0到4递增输出5行而不是按回收站数量从大到小。这个如果考前没注意样例一眼就会暴露但考场上紧张就容易忽略。第四个坑是坐标运算的符号。检查(x1, y)、(x-1, y)、(x, y1)、(x, y-1)四个位置时不要手滑写成(x1, y1)之类的对角方向。用方向数组就能把这种低级失误降到最低。第五个坑是集合查询的对象。set.count写的是pair也就是坐标对而不是单独一个x或y。我曾经见过有人把坐标拆开存两个set然后判断“x在setX里且y在setY里”那是完全不等的逻辑结果自然错得离谱。4. 两道题放在一起看第二题的通用通关套路4.1 从数据范围判断算法把稀疏向量和回收站选址放在一起复盘能提炼出一套应对第二题的决策思路拿到题先看数据范围再决定数据结构。我把常见的数据范围信号整理如下平时练习时可以直接套用看到的数据范围通常暗示数组长度达到10的9次方但只给少量元素不要开满数组用哈希或双指针处理稀疏数据坐标值达到正负10的9次方但点数只有10的5次方不要开二维标记数组用set或哈希存坐标对输入序列保证升序多半可以用双指针在O(n)解决n在10的5次方量级O(n log n)的set/排序写法安全O(n^2)必死n在10的6次方量级需要O(n)级别算法加快速输入输出这两道题正好把表格里的第一行和第二行各演示了一遍。遇到“超大范围少量有效数据”时一个关键思维要刻在脑子里存储什么取决于查询什么。稀疏向量需要按下标做交集查询所以存非零项列表回收站选址需要回答“某坐标周围有没有垃圾点”所以用集合存坐标。4.2 做题顺序与时间分配CSP认证一共5题考试时间比较紧张。我的建议是前两题必须快、准、稳因为它们决定了你的下限。具体时间分配可以按这个节奏来读题阶段3分钟内迅速锁定数据范围和题目类型判断该用哪个数据结构构思阶段5分钟内在草稿纸上写清楚核心步骤尤其是判断条件编码阶段10到15分钟一口气把代码写完避免边写边想测试阶段5分钟至少过一遍题目样例再自己造两个小用例验证边界。第二题总耗时控制在30分钟左右比较健康。如果超过40分钟还没AC建议先跳到第三题看看别死磕。我自己的习惯是写完代码后一定会手造几个特殊用例。比如稀疏向量我会造一个“完全没有公共下标”的用例输出必须为0回收站选址我会造一个“某点缺少一个正方向”的用例它必须被淘汰而不是得低分。这些特殊用例往往就是AC和WA的分界线。5. 实战中的常见问题速查与修复实录5.1 稀疏向量问题排查现象可能原因修复方式输出一直是0双指针比较下标的逻辑写反或循环条件写错检查是u[i].first v[j].first还是大于方向别反大样例输出负数或异常大C里用int存乘积或累加结果全部改用long long超时对每一对非零项都做遍历比较复杂度变成O(a*b)必须用双指针把复杂度降到O(ab)编译不通过试图开vector长度为n的数组n过大只存非零项列表还有一个很容易被忽略的场景如果a或b为0说明有一个向量是全零向量内积必然是0。双指针写法天然能处理这种情况循环直接不进入输出0完全没问题。5.2 回收站选址问题排查现象可能原因修复方式合格点数量偏少四方向判断写成了“或”导致该淘汰的没淘汰改成只要有一个方向不存在就break并continue分数全部为0对角判断误用了上下左右的方向数组单独定义对角方向数组sx/sy输出行数不对或顺序不对输出顺序不是按分数0到4递增按ans[0]、ans[1]、ans[2]、ans[3]、ans[4]输出运行时超时输入输出没优化C加ios::sync_with_stdio(false)Python用buffer读取集合查询结果异常用两个set分别存x和y再分开判断必须用pair整体存坐标整体查询5.3 考场上容易忽略的IO细节IO问题在CSP认证里是真能要命的。很多同学明明算法写对了最后却因为IO太慢在最后几个大样例上超时非常可惜。C选手养成两个习惯一是所有main函数开头写上ios::sync_with_stdio(false); cin.tie(nullptr);二是换行一律用\n而不是endl。endl每调一次都会强制刷新缓冲区在输出量稍大的题目里会拖慢速度。Python选手更要注意input()逐行读在输入量达到几十万行时会很吃力。直接用sys.stdin.buffer.read().split()一次性读入全部数据再按位置解析速度能快好几倍。上面给的代码就是这个模式考场上直接套用就行。另外一个实用技巧样例通过只是最低标准。我一般会再花两分钟手算一个自造小样例比如回收站选址里构造一个得分分别为0和4的两个点确认输出对应行数正确。这种简单的“人肉单步执行”能拦住大半低级错误。6. 一点真实备考心声这两道题放在一起讲是因为它们在策略上有同一个启示别让极端的数据范围打乱你的编程节奏。维度上亿坐标上天这些数字看着吓人实际上都在逼你换一个存储思路而已。我在备考时把近几场认证的第二题都做了一遍发现高频考点真的就那几个双指针、集合判存、前缀和、二分查找、简单模拟。其中双指针和集合判存出现频率尤其高考场上遇到它们的概率非常大。稀疏向量和回收站选址正好是这两个知识点的入门代表。如果你现在还在为CSP认证发愁我的建议特别简单拿出历次认证的第一题和第二题每道题刷三遍。第一遍限时40分钟自己做第二遍对照题解看有没有更优的存储方案第三遍隔天闭卷默写。这个方法很笨但确实管用。第二题不是考天才的是考熟练度的。下一篇我打算接着拆线性分类器和报数这种“看似简单但坑点密集”的第一、二题组合。把这一档的分数都拿稳了后面的第三题才有从容思考的底气。你在刷这两题时如果遇到别的奇怪问题也可以拿我这份排查表先对一遍基本上能解决八成。 
长河君 · 2026/10/17 23:03:30 · 阅读 1.2k CCF CSP第二题套路：稀疏向量与回收站选址的双指针与集合判存
如果你准备过CCF CSP认证应该对这两道题不陌生稀疏向量、回收站选址。它们分别出现在第19次和第18次认证的第二题风格高度相似——读题不难、代码不长但一不留神就丢分。恰好它们踩中了同一个核心考点面对超大范围的数据上亿的向量维度、正负十亿的坐标你怎么把存储和查找组织得又快又稳。这篇就把两题拆开讲透顺便聊聊为什么“第二题”是认证里性价比最高的100分。1. 这两道题在认证里是什么地位1.1 题号与场次对照CCF CSP认证的题目编号有个规律前两位是年份中间两位是当年第几次认证最后一位是题号。这两题的官方信息如下题目题号场次题目类型核心知识点稀疏向量202006-2第19次计算题双指针 / 哈希判存回收站选址201912-2第18次模拟题坐标集合判存从编号能看出来它们都在“第二题”的位置上。CSP认证的题目难度曲线非常固定第一题是送分题只要读懂题就能拿满第二题开始上强度但强度有限属于“稍微动点脑子就能AC”的档位从第三题开始才是真刀真枪的算法与实现综合题。1.2 为什么第二题是“分水岭”很多考过CSP的人都有同一个感受200分是一道大坎。为什么是200分因为第一题100分基本必拿第二题如果也能AC总分就站稳200了。第三题通常来不及完整写出来或者写出来也容易因为细节过多而拿不到满分。但也正因为第二题处在“送分和拉分”的临界位置它成了翻车高发区。我见过不少同学第一题10分钟AC第二题卡了一个半小时最后总分只有100多。原因无非几类被数据范围唬住不知道用什么数据结构看懂了题但实现时边界条件写错复杂度估算失误简单写法直接超时输入输出处理不当在IO上白白丢分。稀疏向量和回收站选址恰好把这些问题各暴露了一遍。前者教你如何在“维度极大但非零极少”的场景下高效求内积后者教你如何在“坐标范围极大但点数量有限”的场景下做邻域判断。把这两题吃透第二题这个档位的套路你就掌握了八成。2. 稀疏向量读懂“稀疏”才不会开错数组2.1 题目到底在问什么题目给的是两个n维向量u和v但n可以大到10的9次方上下显然不可能开一个长度为n的数组。好在输入只给出各自非零的项第一行给三个数n、a、b接下来a行是u的非零下标和值再接下来b行是v的非零下标和值。两组输入都按下标升序排列最后要求计算两个向量的内积。内积的定义很简单只有相同下标位置的数值才相乘再把所有乘积加起来。问题在于这两个向量绝大部分位置都是0如果老老实实遍历1到n哪怕只遍历到10的8次方都会超时更别说10的9次方了。所以这道题真正的考点是怎么用非零项列表高效计算内积。这里先厘清一个容易混淆的地方。两个向量各自有a和b个非零项如果某个下标只在u里出现、不在v里出现那它对内积的贡献是0。真正有贡献的是那些“在两个输入里同时出现且下标相等”的位置。换句话说你要找的是两个有序列表的“交集”。2.2 双指针为什么是这个题的正解因为两个列表都按下标升序排列这给了我们一个天然的线索用双指针像归并排序合并有序序列那样同步扫描。具体做法是指针i指向u的第一个非零项指针j指向v的第一个非零项。比较下标如果u[i]的下标小于v[j]的下标说明u当前这个下标在v里找不到i往后移如果u[i]的下标大于v[j]的下标说明v当前这个下标在u里找不到j往后移如果下标相等这就是一次有效贡献把两个值相乘累加到答案里然后i和j都往后移。整个过程每个元素最多被扫一次复杂度是O(ab)空间上除了存输入以外不需要额外的大结构。有人会问用哈希表先存u的所有非零项再遍历v查表不也一样能做确实能哈希做法时间复杂度也是O(ab)而且在索引不是升序的时候是唯一简单方案。但双指针有两个优势一是完全不用处理哈希表的常数开销和冲突问题二是代码更短更不容易出错。既然题目保证升序那就别舍近求远。2.3 C与Python参考实现C版本用pair存下标和值#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, a, b; cin n a b; vectorpairint, long long u(a), v(b); for (int i 0; i a; i) { cin u[i].first u[i].second; } for (int i 0; i b; i) { cin v[i].first v[i].second; } long long ans 0; int i 0, j 0; while (i a j b) { if (u[i].first v[j].first) { i; } else if (u[i].first v[j].first) { j; } else { ans u[i].second * v[j].second; i; j; } } cout ans \n; return 0; }这里有个细节第一行的n读完以后并没有在代码里用到。它只是告诉你向量总体维度有多大提醒你不要开数组。这是这类“大维度稀疏输入”题的常规套路n往往只是吓唬人的。Python版本用sys.stdin.buffer加速输入import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) pos 0 n, a, b data[0], data[1], data[2] pos 3 u [] for _ in range(a): idx, val data[pos], data[pos 1] pos 2 u.append((idx, val)) v [] for _ in range(b): idx, val data[pos], data[pos 1] pos 2 v.append((idx, val)) ans 0 i j 0 while i a and j b: if u[i][0] v[j][0]: i 1 elif u[i][0] v[j][0]: j 1 else: ans u[i][1] * v[j][1] i 1 j 1 print(ans) if __name__ __main__: main()Python的大整数天然不会溢出所以这里不需要像C那样操心long long的问题。不过Python写起来更简洁但运行速度慢遇到10的5次方量级的输入时用buffer读取就非常关键了。2.4 容易踩的坑类型、指针、剩余元素这道题虽然代码短但坑一个比一个隐蔽。第一个坑是类型。C里value可能很大两个value相乘再累加用int承接必炸。我建议直接用long long存value和ans别赌数据大小。真实考场上因为类型溢出白丢100分的人每年都有。第二个坑是双指针的推进逻辑。有些同学在“下标相等且累加完”以后只移动一个指针导致同一个元素被重复计算结果偏大。记住相等时两个指针都必须前进。第三个坑是循环结束后的处理。有些同学习惯性地在循环后面再写一段处理剩余元素的代码比如“如果i还没走完就继续……”。这个题不需要。循环退出的条件是i和j至少有一个越界此时剩下的元素下标必然不会在另一个列表里出现对内积没有贡献。多写这段反而是错。第四个坑是误以为n是有效输入。n本身不参与计算但它决定了你的第一反应。看到n上亿就立刻明白数组法死刑只能用非零项列表。3. 回收站选址别让“坐标范围”骗了你3.1 题目背景与候选条件这道题结构也很清晰。平面上有n个已知坐标的垃圾点要从这些垃圾点里选一些位置建回收站。选中的条件有两个该位置本身有垃圾该位置的上、下、左、右四个相邻位置都有垃圾。满足条件的点才能成为候选回收站然后给它评分看它的左上、右上、左下、右下四个对角方向上分别有多少个位置有垃圾有几个就算几分分数范围是0到4。最后按分数0、1、2、3、4统计数量各输出一行。注意一个关键逻辑候选点本身必须来自输入的垃圾点列表。题目不是问“地图上哪些位置可以建站”而是“在这些已有的垃圾点里哪些适合建站”。所以遍历对象就是输入的n个点。另外上下左右四个方向是“都有垃圾”不是“至少有一个”。我见过有人把条件写成四方向任意一个存在就合格那是另外一个题目了。四个方向必须同时满足缺一个都直接淘汰。3.2 为什么不能开二维数组这道题坐标范围很容易让人犯迷糊x和y的绝对值可以到10的9次方。如果按坐标范围开二维数组内存直接爆炸连编译都过不了。正确思路是离散化判存不需要知道地图上所有格子有没有垃圾只需要回答“某个具体坐标是否是垃圾点”这个问题。n本身只有10的5次方量级把n个点的坐标放进一个集合每次查一个坐标是否存在用平衡树或哈希都是O(n log n)或O(n)的复杂度。这种模型在算法题里太常见了。一个超大平面里只撒了有限几个点你要做的所有判断都只围绕这些点展开那就把点存成可哈希的对象然后用集合解决一切。不要被坐标范围吓到它不是让你去遍历整张地图而是告诉你怎么做一定会超时。有人会问C里能不能用unordered_map存pair标准库没有给pairint,int提供哈希得自己写哈希函数。现场写那个东西容易写错又慢又麻烦。直接用setpairint,int就行set的查询是O(log n)n1e5时完全够用代码还短。3.3 参考实现C版本用set存坐标#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int points(n); setpairint, int s; for (int i 0; i n; i) { int x, y; cin x y; points[i] {x, y}; s.insert({x, y}); } int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int sx[4] {1, 1, -1, -1}; int sy[4] {1, -1, 1, -1}; int ans[5] {0}; for (auto p : points) { int x p.first, y p.second; bool ok true; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (s.count({nx, ny}) 0) { ok false; break; } } if (!ok) continue; int score 0; for (int k 0; k 4; k) { int nx x sx[k]; int ny y sy[k]; if (s.count({nx, ny}) 0) { score; } } ans[score]; } for (int i 0; i 5; i) { cout ans[i] \n; } return 0; }Python版本逻辑一样代码更短import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) n data[0] points set() order [] pos 1 for _ in range(n): x, y data[pos], data[pos 1] pos 2 points.add((x, y)) order.append((x, y)) dx [1, -1, 0, 0] dy [0, 0, 1, -1] sx [1, 1, -1, -1] sy [1, -1, 1, -1] ans [0] * 5 for x, y in order: ok True for k in range(4): if (x dx[k], y dy[k]) not in points: ok False break if not ok: continue score 0 for k in range(4): if (x sx[k], y sy[k]) in points: score 1 ans[score] 1 sys.stdout.write(\n.join(map(str, ans)) \n) if __name__ __main__: main()对拍一下这几段代码逻辑是完全一致的先判上下左右再算对角分数最后按分数落桶。3.4 现场易错点这道题真正的失分点不在算法而在实现细节。第一个坑是方向数组写错。上下左右和四个对角是两组不同的方向增量混在一起就会出大问题。建议用两组数组分别存一组dx/dy管上下左右一组sx/sy管对角不要省事写在一个循环里。第二个坑是合格判定提前跳过。一旦发现某个正方向不存在当前点直接不可能是候选回收站应立刻break结束判断并continue到下一个点。别把所有四个方向都检查完再统一判断那样逻辑容易乱也容易把“某个方向不存在”和“不存在也能评分”混淆。第三个坑是输出顺序。答案是按分数0到4递增输出5行而不是按回收站数量从大到小。这个如果考前没注意样例一眼就会暴露但考场上紧张就容易忽略。第四个坑是坐标运算的符号。检查(x1, y)、(x-1, y)、(x, y1)、(x, y-1)四个位置时不要手滑写成(x1, y1)之类的对角方向。用方向数组就能把这种低级失误降到最低。第五个坑是集合查询的对象。set.count写的是pair也就是坐标对而不是单独一个x或y。我曾经见过有人把坐标拆开存两个set然后判断“x在setX里且y在setY里”那是完全不等的逻辑结果自然错得离谱。4. 两道题放在一起看第二题的通用通关套路4.1 从数据范围判断算法把稀疏向量和回收站选址放在一起复盘能提炼出一套应对第二题的决策思路拿到题先看数据范围再决定数据结构。我把常见的数据范围信号整理如下平时练习时可以直接套用看到的数据范围通常暗示数组长度达到10的9次方但只给少量元素不要开满数组用哈希或双指针处理稀疏数据坐标值达到正负10的9次方但点数只有10的5次方不要开二维标记数组用set或哈希存坐标对输入序列保证升序多半可以用双指针在O(n)解决n在10的5次方量级O(n log n)的set/排序写法安全O(n^2)必死n在10的6次方量级需要O(n)级别算法加快速输入输出这两道题正好把表格里的第一行和第二行各演示了一遍。遇到“超大范围少量有效数据”时一个关键思维要刻在脑子里存储什么取决于查询什么。稀疏向量需要按下标做交集查询所以存非零项列表回收站选址需要回答“某坐标周围有没有垃圾点”所以用集合存坐标。4.2 做题顺序与时间分配CSP认证一共5题考试时间比较紧张。我的建议是前两题必须快、准、稳因为它们决定了你的下限。具体时间分配可以按这个节奏来读题阶段3分钟内迅速锁定数据范围和题目类型判断该用哪个数据结构构思阶段5分钟内在草稿纸上写清楚核心步骤尤其是判断条件编码阶段10到15分钟一口气把代码写完避免边写边想测试阶段5分钟至少过一遍题目样例再自己造两个小用例验证边界。第二题总耗时控制在30分钟左右比较健康。如果超过40分钟还没AC建议先跳到第三题看看别死磕。我自己的习惯是写完代码后一定会手造几个特殊用例。比如稀疏向量我会造一个“完全没有公共下标”的用例输出必须为0回收站选址我会造一个“某点缺少一个正方向”的用例它必须被淘汰而不是得低分。这些特殊用例往往就是AC和WA的分界线。5. 实战中的常见问题速查与修复实录5.1 稀疏向量问题排查现象可能原因修复方式输出一直是0双指针比较下标的逻辑写反或循环条件写错检查是u[i].first v[j].first还是大于方向别反大样例输出负数或异常大C里用int存乘积或累加结果全部改用long long超时对每一对非零项都做遍历比较复杂度变成O(a*b)必须用双指针把复杂度降到O(ab)编译不通过试图开vector长度为n的数组n过大只存非零项列表还有一个很容易被忽略的场景如果a或b为0说明有一个向量是全零向量内积必然是0。双指针写法天然能处理这种情况循环直接不进入输出0完全没问题。5.2 回收站选址问题排查现象可能原因修复方式合格点数量偏少四方向判断写成了“或”导致该淘汰的没淘汰改成只要有一个方向不存在就break并continue分数全部为0对角判断误用了上下左右的方向数组单独定义对角方向数组sx/sy输出行数不对或顺序不对输出顺序不是按分数0到4递增按ans[0]、ans[1]、ans[2]、ans[3]、ans[4]输出运行时超时输入输出没优化C加ios::sync_with_stdio(false)Python用buffer读取集合查询结果异常用两个set分别存x和y再分开判断必须用pair整体存坐标整体查询5.3 考场上容易忽略的IO细节IO问题在CSP认证里是真能要命的。很多同学明明算法写对了最后却因为IO太慢在最后几个大样例上超时非常可惜。C选手养成两个习惯一是所有main函数开头写上ios::sync_with_stdio(false); cin.tie(nullptr);二是换行一律用\n而不是endl。endl每调一次都会强制刷新缓冲区在输出量稍大的题目里会拖慢速度。Python选手更要注意input()逐行读在输入量达到几十万行时会很吃力。直接用sys.stdin.buffer.read().split()一次性读入全部数据再按位置解析速度能快好几倍。上面给的代码就是这个模式考场上直接套用就行。另外一个实用技巧样例通过只是最低标准。我一般会再花两分钟手算一个自造小样例比如回收站选址里构造一个得分分别为0和4的两个点确认输出对应行数正确。这种简单的“人肉单步执行”能拦住大半低级错误。6. 一点真实备考心声这两道题放在一起讲是因为它们在策略上有同一个启示别让极端的数据范围打乱你的编程节奏。维度上亿坐标上天这些数字看着吓人实际上都在逼你换一个存储思路而已。我在备考时把近几场认证的第二题都做了一遍发现高频考点真的就那几个双指针、集合判存、前缀和、二分查找、简单模拟。其中双指针和集合判存出现频率尤其高考场上遇到它们的概率非常大。稀疏向量和回收站选址正好是这两个知识点的入门代表。如果你现在还在为CSP认证发愁我的建议特别简单拿出历次认证的第一题和第二题每道题刷三遍。第一遍限时40分钟自己做第二遍对照题解看有没有更优的存储方案第三遍隔天闭卷默写。这个方法很笨但确实管用。第二题不是考天才的是考熟练度的。下一篇我打算接着拆线性分类器和报数这种“看似简单但坑点密集”的第一、二题组合。把这一档的分数都拿稳了后面的第三题才有从容思考的底气。你在刷这两题时如果遇到别的奇怪问题也可以拿我这份排查表先对一遍基本上能解决八成。