★ FEATURED ARTICLE 考过 CCF 认证的同学应该都有同感第二题从来不考什么深奥算法但特别擅长把简单模型藏在数据范围里让你一眼觉得“我会做”写出来却总是在某个角落翻车。“回收站选址”就是非常典型的一道坐标模拟题。题目本身不复杂给一堆整数坐标的垃圾点你要找出所有“适合建回收站”的位置并按得分 0 到 4 统计数量。但麻烦在于坐标范围很大动不动就到 10 的 9 次方数组根本开不下逼着你换一种存储思路。这篇文章就把这道题的读题、算法、满分代码、常见坑一次讲透准备考 CCF 或者刷模拟题练手的人都用得上。1. 先把题目读懂考点其实是坐标判重1.1 题面到底在说什么题目会先给你一个 n表示垃圾点个数然后给 n 行坐标。坐标都是整数保证互不相同。现在要选一些位置建回收站规则是这个位置本身必须已经有垃圾它的上下左右四个紧挨着的位置必须也都有垃圾满足上面两点后看它的四个对角位置上有几个垃圾点有几个就得几分。最终要输出五个整数分别是得 0 分、1 分、2 分、3 分、4 分的候选点各有多少个。我用一个表格把这八个方向拆开看后面写代码时不容易混类型方向相对坐标偏移四邻方向上(x, y1)四邻方向下(x, y-1)四邻方向左(x-1, y)四邻方向右(x1, y)对角方向左上(x-1, y1)对角方向右上(x1, y1)对角方向左下(x-1, y-1)对角方向右下(x1, y-1)很多同学第一次做的时候会把“上下左右”和“四个角”混在一个循环里处理结果全乱了。后面我会专门说这个坑。1.2 数据范围给出了什么信号这题最关键的信号就是坐标范围。印象很深刻坐标绝对值可以到 10 的 9 次方级别而 n 本身只有几千。这就意味着你不能开一个二维数组用a[x][y]来标记某个位置有没有垃圾。10 的 9 次方乘 10 的 9 次方连想都不要想内存直接爆炸。聪明一点的同学会想到用哈希表、平衡树这类结构来存坐标。C 里最顺手的做法就是setpairint, int把每个垃圾点的坐标作为一对键值存进去之后查某个坐标是不是垃圾点直接find一下就行。换句话说这道题表面考的是“模拟选址规则”实际考的是“在大坐标范围内快速判断某个点是否存在”。这就是它作为认证第二题的定位让你把数据结构用在模拟题里。1.3 候选点判定的完整流程完整逻辑按这四步走就行读入所有坐标全部插入到集合中保存。遍历每个垃圾点把它当作潜在的回收站位置。检查它上下左右四个邻居是否都在集合里有一个不在直接跳过。四个邻居都满足再数它四个对角位置有几个在集合里得到一个 0 到 4 的分数。用长度为 5 的数组统计每个分数出现的次数最后输出。逻辑本身不绕但“用什么结构存”“怎么查”直接决定了你这题能不能稳过。2. 算法设计集合选型与复杂度分析2.1 暴力 O(n²) 其实也能拿满分第一次看到这题我第一反应是直接 O(n²) 暴力对每个垃圾点遍历所有点检查它的上下左右是否都存在。n 如果只有 1000两层循环也就 100 万次操作在 C 里非常轻松常数再大也跑得动。所以如果你想图省事暴力也大概率能过。伪代码大概是这样for (int i 0; i n; i) { bool flag true; for (int j 0; j n; j) { // 分别判断 (x[i]1,y[i]) 这些邻居是否等于 (x[j],y[j]) } }但这属于“偷懒写法”。万一数据范围不是 1000 而是 10000100000O(n²) 就会逐渐吃力。既然题目明确考坐标判重直接用集合才是正统做法。而且集合代码写起来也不复杂还能顺便锻炼自己对 STL 的熟练度一举两得。2.2 选 set 还是 unordered_setC 里判断坐标是否存在主流有三种选择setpairint, intunordered_setpairint, intmappairint, int, bool我推荐直接用set。理由是set自带比较函数pair默认支持比较不需要你额外写任何东西unordered_set虽然理论查询更快但pair类型默认没有哈希函数需要自己写一个很多人栽在这里map是“键值对”结构这里只需要判断键是否存在不需要存额外值用 map 属于杀鸡用牛刀还多一份代码量。实际跑起来n 只有几千set的 O(log n) 查询完全没压力一百万个操作都不算事。所以别盲目追求unordered_set竞赛里“稳”比“快”更重要。#include set using namespace std; setpairint, int st; st.insert({x, y}); st.find({nx, ny}) ! st.end()这段就是核心用法。查到了说明该邻居有垃圾查不到就说明没有。2.3 坐标类型用 long long 更稳妥理论上坐标范围只有正负 10 的 9 次方int能装下加减 1 也不会溢出。但我个人写这类题时习惯统一用long long。原因很简单题目里给的坐标范围不会让你难堪但你自己写哈希函数、做偏移计算、或者后续把坐标值拿去参与乘法运算时就保不准会不会爆掉int了。与其纠结边界不如一开始就上long long多写几个字母换一晚上的安心觉。3. C 满分代码逐段拆解3.1 可直接提交的完整代码下面这份代码是 C 满分写法直接复制提交即可#include bits/stdc.h using namespace std; const int MAXN 1005; long long x[MAXN], y[MAXN]; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; int ddx[4] {1, 1, -1, -1}; int ddy[4] {1, -1, 1, -1}; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; setpairlong long, long long st; for (int i 0; i n; i) { cin x[i] y[i]; st.insert({x[i], y[i]}); } int ans[5] {0}; for (int i 0; i n; i) { bool ok true; for (int j 0; j 4; j) { long long nx x[i] dx[j]; long long ny y[i] dy[j]; if (st.find({nx, ny}) st.end()) { ok false; break; } } if (!ok) continue; int score 0; for (int j 0; j 4; j) { long long nx x[i] ddx[j]; long long ny y[i] ddy[j]; if (st.find({nx, ny}) ! st.end()) { score; } } ans[score]; } for (int i 0; i 5; i) { cout ans[i] \n; } return 0; }如果你是第一次接触这道题建议不要只复制而是自己重新敲一遍。下面我把每一段为什么这么写讲清楚。3.2 主流程与方向数组设计代码开头定义了两个方向数组int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0};这四个组合分别是(0,1)、(0,-1)、(1,0)、(-1,0)正好对应上、下、右、左四个邻居。顺序无所谓但必须在脑子里明确这个数组只用来检查“上下左右”。对角方向是另一组int ddx[4] {1, 1, -1, -1}; int ddy[4] {1, -1, 1, -1};对应(1,1)、(1,-1)、(-1,1)、(-1,-1)也就是右下、右上、左上、左下。两组数组分开写有两个好处语义清晰读代码的人一眼就知道哪段是“选候选点”哪段是“打分”避免把八个方向混在一起后上下左右里夹着对角导致候选点判定错误。我看到过不少人把八个方向放进同一个数组然后在检查条件里写“如果是邻居就继续如果是对角就加分”逻辑上绕来绕去最后把自己绕晕。分开写是最省脑子的方案。3.3 候选判定与计分细节主循环里第一步是选候选点for (int i 0; i n; i) { bool ok true; for (int j 0; j 4; j) { long long nx x[i] dx[j]; long long ny y[i] dy[j]; if (st.find({nx, ny}) st.end()) { ok false; break; } } if (!ok) continue; ... }这里有一个小细节break只能写在“上下左右判定”的循环里。一旦发现某个邻居不存在这个点就不可能成为回收站后面不用再看了也不用再去数对角。但一旦进入打分阶段就不要提前 break。得分需要统计四个对角里到底有几个存在必须四个方向全部数完。int score 0; for (int j 0; j 4; j) { long long nx x[i] ddx[j]; long long ny y[i] ddy[j]; if (st.find({nx, ny}) ! st.end()) { score; } } ans[score];score必然是 0 到 4 的整数正好作为数组下标。最后ans[0]到ans[4]的顺序输出就是题目要求的结果。3.4 用手工用例验证代码光说逻辑不够实际跑一遍最踏实。先用题目常见的样例数据7 1 2 2 1 0 0 1 1 1 0 2 0 0 1这组数据跑出来结果是0 0 1 0 0只有一个候选点得分 2。你可以在草稿纸上画一下这些点会发现只有中心点(1,1)上下左右都有垃圾而且它的左下、右下两个对角也有垃圾所以得 2 分。和代码输出完全对得上。再测一个满 4 分的构造9 0 0 1 0 2 0 0 1 1 1 2 1 0 2 1 2 2 2这是一个 3×3 的完整方块。中心点(1,1)四个邻居都在四个对角也都在所以得分必然是 4。其他点不是缺上就是缺下都不是候选点。输出应为0 0 0 0 1这两个测试用例足够说明代码逻辑正确。如果你自己改写了代码至少先用这两组数据验证一下再提交。4. 常见问题与满分避坑4.1 方向搞混、数组越界最常见的翻车点是把“上下左右”和“四个对角”混成一个概念。比如有些人判断“上下左右有垃圾”时会把左上、右上也算进去这样候选点的标准就不对了。还有一点坐标是long long但你如果用int存nx, ny在当前数据量下其实不会出事因为坐标加减 1 还在int范围内。可一旦你自己扩展题目给坐标乘以 10 再偏移就说不准了。统一用long long能免掉这类隐性问题。4.2 试图用固定二维数组标记坐标坐标范围那么大如果有人非要用bool a[1000000005][1000000005]来存程序直接崩溃。这不是代码技巧的问题是方向性错误。正确做法是把所有输入的点塞进集合用判断“在不在集合里”替代“数组某个位置是不是 1”。这也是我在第 2 节反复强调的原因。如果你特别怀念数组下标的直观感可以试试把坐标映射到一维哈希表但那个代码量对新手并不友好没必要。4.3 输出顺序写反题目要求输出得分从 0 到 4 的候选点数量也就是ans[0]、ans[1]、ans[2]、ans[3]、ans[4]。有些同学审题不仔细最后倒着输出或者只输出有候选点的分数都会丢分。CCF 评测系统看的是标准输出多一个数、少一个数、顺序不对都是零分。另外输出用空格还是换行其实并不影响这题判分。很多 OJ 是按空白符分割比较数字的你用cout ans[i] \n和cout ans[i] 效果一样。不过为了保险起见我习惯每行一个数字贴近常规格式。4.4 本地调试与提交环境备忘说几个容易忽略的环境问题使用bits/stdc.h在绝大多数评测机上没问题但个别老编译器不认这个万能头文件。遇到这种情况改成#include iostream、#include set等标准头文件即可。本地调试如果用文件重定向比如freopen(in.txt, r, stdin)提交前一定记得注释掉否则评测机会找不到文件直接返 0 分。main函数结尾写上return 0;这是规范动作别图省事省略。这些不是题目本身的知识点却是实打实影响分数的细节。5. 写在最后刷这道题最大的收获不是背会了一个set用法而是建立起一种条件反射看到坐标范围很大的“模拟题”第一反应不是开二维数组而是想“能不能用集合来判重”。这种思路在后来的很多题目里都用得上。如果你打算考 CCF 认证建议把这类题归纳成自己的固定模板读入点、存集合、方向数组、统计输出。多做几道你会发现第二题并没有想象中那么难真正难的往往是第一眼看到大坐标时手忙脚乱的心理。冷静下来先分析数据范围再决定存储结构这题就是稳稳的送分题。
阅读完成 · 觉得有帮助？
