2023年的ICPC网络赛打完之后我花了不少时间把场上几道简单题重新过了一遍越复盘越觉得这类线上预选赛的“简单题”其实很有讲究。文章里的内容不是官方题解而是我个人在比赛中的选题、写代码和踩坑记录适合刚接触算法竞赛、想了解网络赛题目风格的同学阅读。ICPC网络赛题量大、时间紧三个人盯着一台电脑很多时候比的就是谁能更快把简单题捞起来保住基本盘。网络赛的难度分配往往很典型前十题里至少有四五道是“训练量到位就能做”的题后面则开始上强度。很多人一上来就被中后段的题目吓住看到英文题面长就跳过其实前几题只要读题细心、代码扎实拿分效率非常高。下面我会拆解几道我在场上AC的简单题尽量把思路、代码和容易翻车的地方都讲清楚。1. 2023网络赛的赛制与选题策略1.1 网络赛到底在比什么ICPC网络预选赛是正式区域赛之前最重要的线上筛选赛参赛队伍以学校为单位每队三个人共用一台电脑。比赛时长一般是四到五个小时题目数量通常在十题以上语言以C/C为主Java、Python也能提交但主流解法基本都用C写。和现场赛不同网络赛的评测环境往往是在线评测系统参赛队伍分布在全国各地。这意味着除了算法能力网络状况、电脑环境、队友之间的配合也会直接影响成绩。我见过不少队伍明明实力不差却因为开局前半小时代码模板没准备好或者读题顺序不对白白丢了好几道水题。所以我把网络赛第一步定义为“选题”而不是“做题”。前二十分钟的任务不是死磕一道题而是把所有题目都翻一遍快速判断哪些是简单题、哪些是中等题、哪些是暂时碰不了的难题。简单题的特征通常很明显题面短、数据范围小、没有复杂的数据结构背景看到之后能直接想到暴力、模拟或经典贪心。1.2 我眼中的难度分布以2023年的网络赛为例我个人的体感是题目可以粗分成三档简单题不需要太深数学推导靠基本编程能力就能解决分布在整场比赛的前半段。中等题需要一点算法积累比如前缀和、二分、简单DP、STL应用或者是比较明显的图论题。难题需要很强的综合能力经常是数据结构套数学、动态规划加优化或者需要观察出比较隐蔽的性质。正因为简单题在前几题所以我的策略很固定先把前五六题全部读一遍从最短题面的开始看。很多简单题的英文描述并不长关键词一眼就能认出来比如“count the number of ...”、“minimum number of ...”等等。一旦觉得有思路立刻上机开写之前先和队友说清楚思路避免后面改来改去。这里还要提醒一点网络赛的罚时规则和ICPC现场赛一致提交错误会有罚时。所以“简单题”也不意味着可以闭着眼交很多时候多想想边界条件比抢那几分钟更重要。2. 从签到题看基础功底字符串处理的隐形坑2.1 题目大意与样例解读先聊一道典型的签到题这类题基本属于“会写循环就能过”的级别。题目大意如下给定一个只包含小写字母的字符串请你把所有出现次数为奇数的字母按字母表顺序输出如果不存在这样的字母输出-1。字符串长度不超过10^5多组输入读到文件结束为止。题目本身不难用一个长度为26的整型数组记录每个字母出现的次数遍历完字符串之后从小到大检查哪些字母的出现次数是奇数输出对应字符即可。但签到题最容易在“读入”上翻车。比赛的时候我第一反应是用cin直接读字符串因为这道题没有空格字符流cin s完全可以。但如果题目里说“可能包含空格”就必须用getline(cin, s)。这个细节看起来很小却真的会让不少队伍白白吃一发罚时。还有第二个要注意的点多组输入时每一组之间可能有空行。有的选手在读完字符串后没有处理换行符导致下一次getline读到一个空串程序输出-1看起来好像没问题实际上后续所有输出都错位了。这种问题在本地跑样例时很难发现因为样例通常没有多余空行但在评测数据里很容易出现。2.2 代码实现与复杂度分析这道题的参考代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; while (cin s) { // 题目保证没有空格时可以直接用 cin int cnt[26] {0}; for (char c : s) { cnt[c - a]; } bool flag false; for (int i 0; i 26; i) { if (cnt[i] % 2) { cout char(a i); flag true; } } if (!flag) cout -1; cout \n; } return 0; }时间复杂度是O(n)空间复杂度是O(1)因为数组大小固定为26。这个复杂度对于10^5的字符串长度来说是轻轻松松的。我写这段代码时特别注意了“奇数字母可能有多个”这一点。题意要求把所有奇数次的字母都输出不是只输出一个。检查完cnt数组之后累积输出最后如果都没有奇数才输出-1。这种细节虽然简单但恰恰是区分“AC”和“WA”的地方。2.3 这类签到题的复习价值很多人觉得签到题太水赛后就不看了。但实际上字符串处理是ICPC赛场上最高频的基础考点之一签到题里也经常暗藏输入输出陷阱。我当时赛后重新整理这道题时特意把getline、cin.ignore()、多组输入里空行过滤的三种写法都过了一遍。网络赛不像平时刷题可以反复提交交一次错就是20分钟罚时所以这种基础功平时一定要练到不需要思考就能稳写的水平。3. 前缀和与哈希的经典组合子数组和恰好等于k3.1 为什么第一眼会想到双指针第二道想讲的题是“给定一个长度为n的整数数组a问有多少个连续子数组的和恰好等于k”。这道题在网络赛里出现的概率太高了基本是前缀和专题的看门题。题目数据范围一般是n 2e5数组元素a[i]的绝对值可能很大k也可能很大。很多初学者第一反应是“数组有正有负或者全为正数”如果全为正数确实可以用双指针滑动窗口在线性时间内解决因为随着窗口右端移动窗口和是单调递增的左端就可以跟着往右收。所以如果题目特别说明a[i] 0双指针是最简单、最不容易写错的方案。但2023年的网络赛这道题并没有保证数组元素非负。也就是说数组里可能同时有正数和负数。这种情况下双指针的单调性就没了窗口和会随着右端扩展忽大忽小左端不能确定往哪个方向移动才能接近k所以必须换思路。3.2 从暴力到前缀和加哈希暴力做法是枚举所有子数组的左右端点然后计算区间和。从[l, r]的累加最坏情况是O(n^3)或O(n^2)在n2e5的数据范围下想都不要想。优化方向很自然先预处理前缀和数组pre[i]表示数组前 i 个元素的和。那么区间[l, r]的和就是pre[r] - pre[l-1]。问题转化为有多少对(i, j)满足i j且pre[j] - pre[i] k。移项一下就是pre[i] pre[j] - k在上面这个式子里j是当前枚举到的位置i是之前出现过的位置。我们不需要真的枚举i只需要知道在遍历到j之前有多少个前缀和的值等于pre[j] - k。用哈希表C里的unordered_map来记录每个前缀和出现的次数就能在线性时间内统计出来。这里有一个特别经典的坑如果k 0我们在遍历到某个位置时先查询pre[j] - k等于pre[j]自己此时哈希表里已经存了pre[j]的话就会把当前这个前缀本身也算进去导致答案偏大。正确的做法是“先查旧值再更新当前值”。也就是说对于每个前缀和我们先统计在它之前有没有出现过满足条件的前缀和然后再把当前前缀和加入哈希表。3.3 参考代码与边界细节#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin n k; vectorlong long pre(n 1, 0); unordered_maplong long, long long cnt; cnt[0] 1; // 前缀和为0的情况表示从第1个元素到当前位置的区间 long long ans 0; for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; auto it cnt.find(pre[i] - k); if (it ! cnt.end()) { ans it-second; } cnt[pre[i]]; } cout ans \n; return 0; }这个实现的复杂度是O(n)的期望时间空间也是O(n)。关于cnt[0] 1这一点很多人不理解。举个最简单的例子如果k 3数组是[1, 2]遍历到第2个数时pre[2] 3那么查pre[2] - k 0如果一开始没有cnt[0] 1就会漏掉“整个数组就是一个合法子数组”这种情况。所以初始值cnt[0] 1是必须的。另外由于数组元素绝对值和长度都可能很大前缀和要用long long不要用int。我见过不少队伍在这里爆int交上去WA又查不出原因。比赛时间紧张这种低级错误很容易让人心态崩。4. 区间选点贪心为什么按右端点排序是对的4.1 题目与经典变种第三道题是经典的区间选点问题题目描述一般长这样数轴上有n个区间第i个区间是[l_i, r_i]。现在需要在数轴上放置若干个点要求每个区间内至少包含一个点。请问最少需要放置多少个点这道题在ICPC网络赛里经常作为前几题的难度出现背后是贪心算法里非常经典的“区间问题”。它还有一个大家更熟悉的变种活动安排问题选择最多的互不重叠的区间。两个问题都靠排序解决但排序的依据不同。我当年第一次做这类题时直觉是把区间按左端点排序然后尝试合并区间。结果发现按左端点排序很容易遇到一种反例第一个区间特别长从左到右覆盖了后面很多区间但它的右端点已经很靠右了。如果我们在它的右端点上放一个点确实覆盖了它自己但后面那些左端点靠右、右端点更靠左的区间就可能会漏掉。正确的贪心策略是把区间按右端点从小到大排序然后维护一个当前已经放置的“最后一个点”的位置。遍历区间时如果当前区间的左端点大于这个点的位置说明这个区间没有被覆盖需要在这个区间的右端点处新放一个点。否则当前区间已经被之前的点覆盖不需要新增点。4.2 贪心正确性的直观证明为什么按右端点排序是对的因为对于当前未覆盖的最小区间右端点最小的区间我们要想覆盖它点的位置只能放在它的左端点到右端点之间。为了让这个点能尽可能多地覆盖后面的区间放在它的右端点是最优的。因为后面所有区间的右端点都不小于它如果某个区间的左端点小于等于当前区间的右端点那么把点放在当前区间右端点就能同时覆盖它如果把点放在更左边反而可能漏掉某些区间。这种证明思路叫“贪心交换论证”贪心选的第一个点和最优解的第一个点相比贪心点不劣于最优解点通过不断替换可以证明贪心解就是最优解。场上不需要写得这么严谨但至少要用反例说服自己不能想当然。4.3 实现细节与常见错误#include bits/stdc.h using namespace std; struct Interval { int l, r; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorInterval seg(n); for (int i 0; i n; i) { cin seg[i].l seg[i].r; } sort(seg.begin(), seg.end(), [](const Interval a, const Interval b) { return a.r b.r; }); int ans 0; int last INT_MIN; for (const auto s : seg) { if (s.l last) { ans; last s.r; } } cout ans \n; return 0; }这个实现里有几个地方需要注意。首先是排序的 comparator一定要用右端点升序如果写成a.r b.r整道题就废了。其次last的初始值应该是一个很小的数比如INT_MIN这样第一个区间一定会进入分支。如果初始值设成0而区间左端点可以是负数就会漏算。还有一个非常容易踩的细节当区间右端点相同时排序结果不影响答案因为不管哪个在前只要左端点大于last就新增点而last更新为同一个右端点结果一样。但如果题目要求输出方案可能还要按照左端点做第二关键字不过这里只要求数量不需要。区间选点问题的本质是“用最少的点覆盖所有区间”它和网络赛里另一类“最多不相交区间”问题经常一起出现。我建议把这两个问题放在一起复习这样贪心思路会更清晰。5. 二维网格连通块DFS/BFS写法与栈溢出风险5.1 题目特点不是难题但容易卡环境第四道想说的是网格图连通块题。这类题通常长这样给定一个n行m列的网格每个格子要么是空地.要么是石头#。上下左右相邻的空地属于同一个连通块请问网格中有多少个独立的空地连通块这种题在算法竞赛里属于“水题”级别因为直接DFS或BFS就能做。但网络赛里这道题的正确率并没有想象中高原因主要有两个一是很多人DFS递归写得不注意在网格较大时爆栈二是方向数组写错导致上下左右漏掉某个方向。我们需要对每个未访问过的空地格子进行搜索把和它相连的所有空地点打上标记。搜索方法可以是深度优先搜索DFS也可以是广度优先搜索BFS。用DFS实现非常短void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; if (grid[x][y] ! .) return; grid[x][y] #; // 直接标记为已访问省掉vis数组 for (int d 0; d 4; d) { dfs(x dx[d], y dy[d]); } }这里有个很实用的小技巧直接用grid[x][y] #来标记已访问不需要额外开一个vis数组。因为搜索完之后题目只要求计数并不需要保留原始网格。这种做法能省一点内存也让代码更简洁。5.2 用BFS替代DFS务必掌握但是在比赛环境下我其实更推荐用BFS写这道题。原因很简单C的递归函数默认栈空间有限当网格规模到1000x1000并且全是空地时DFS递归深度会非常大可能导致栈溢出。虽然很多在线评测系统会调大栈空间但网络赛的评测环境不好说我们不能赌。BFS用队列来模拟没有递归深度问题。参考写法如下#include bits/stdc.h using namespace std; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { vectorstring grid(n); for (int i 0; i n; i) cin grid[i]; int ans 0; queuepairint, int q; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] .) { ans; grid[i][j] #; q.push({i, j}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] ! .) continue; grid[nx][ny] #; q.push({nx, ny}); } } } } } cout ans \n; } return 0; }这个代码的复杂度是O(n*m)每个格子最多入队一次。对于网格题这个复杂度是必须做到的。5.3 多组数据与输入读取的坑这道题描述里写着“多组输入”所以我在外层套了一个while (cin n m)。有些人会在这里写成死循环原因是没有判断读取是否成功有些人则会忽略n0, m0作为结束标志的情况导致全场卡在一道简单题上。如果题目明确说“输入以0 0结束”那循环条件就要写while (cin n m (n || m))。网络赛里这种细节经常变最好每次读题时都确认一下。另外不要忘记queue清空的问题。如果每一次搜索都用同一个全局队列下一组数据开始时可能残留上一次搜索的节点。最省心的办法是在每次外层搜索时都定义一个新的局部队列像我上面写的那样。局部变量会自动析构不会出现残留问题。6. 网络赛现场经验先拿稳简单分比什么都重要6.1 读题顺序的实战技巧我在2023网络赛中的实际顺序是“先看题面最短的再看数据范围最小的”而不是从头到尾顺序读。因为出题人在摆放题目顺序时不一定是按难度严格递增的偶尔会有简单题被放在靠后的位置。如果一直从第1题往后做可能会在一道难题上卡很久结果后面那道白给题没时间做。更好的办法是第一轮扫描时把所有题目的标题和题面第一段快速看一遍在草稿纸上记录哪些题看起来可以暴力哪些题像是前缀和、贪心、BFS。然后把题目分成“马上能做”、“需要想想”、“先放放”三类。优先把马上能做的题AC掉再花时间想需要想想的题。这种策略的核心是避免把时间浪费在错误的方向上。很多时候一道看起来很难的题其实有一个很简单的性质但需要跳出来才能发现。如果一开始就钻进牛角尖反而忽略了其他简单题。6.2 常用模板与开局准备网络赛开始前我会把下面这些模板代码提前敲好放在编辑器里备用快读快写或者至少ios::sync_with_stdio(false); cin.tie(nullptr);常用头文件#include bits/stdc.h快速幂最大公约数、最小公倍数二分查找的库函数用法数组/容器的排序sort自定义比较器这些模板不需要多复杂但能省下开局阶段的大量时间。比如gcd在C17里可以用std::gcd但很多比赛环境的编译器版本较低还是自己写一个更稳妥。C的bits/stdc.h是GCC编译器的扩展头大部分评测系统都支持但如果遇到不支持的编译器就需要改成传统的头文件列表。网络赛之前最好确认一下评测环境用的编译器版本。另外一定不要低估ios::sync_with_stdio(false)的作用。当输入规模较大时没有这一行cin的速度可能比标准C的scanf慢很多。网络赛数据量一大就可能导致超时而这不是算法的问题。简单题里数据范围往往是10^5以上所以开局一定要写好这一行。6.3 网络赛特有的心态管理如果说现场赛比的是实力和运气那网络赛还要比心态。因为网络赛的评测反馈不像现场赛那么即时有时候提交之后要等很久才能看到结果。这时如果发现自己WA了很容易着急甚至开始盲目修改代码。我的经验是提交之前先和队友互相检查一遍重点看数据范围、类型有没有用对、数组有没有开够。如果一道题在自己队伍中都没人能讲清楚思路那就先不要提交继续想清楚。因为一次罚时的代价很大尤其是简单题多WA几发可能会让整支队伍的名次掉出一大截。网络赛的另一个特点是一个队伍只有一台电脑。三个人抢键盘的效率非常低。所以开局的两小时以内最好分工明确两个人负责读题想思路另一个人负责写代码。写代码的人不要边写边想先把思路写在纸上再上机。这样可以最大限度减少“上机后发现方向错了”的浪费。6.4 赛后复盘的真正价值很多队伍打完网络赛就散了这其实很可惜。在我看来网络赛最大的价值不是那张成绩单而是赛后复盘。尤其像我这次整理的几道简单题虽然每道题单独看都不难但把它们放在一起就能看出网络赛简单题的出题偏好字符串处理、前缀和/哈希、贪心、网格搜索。这些都是最基础但最常用的算法。复盘时我会问自己三个问题这道题有没有更简单的做法我的代码有没有可能更快我在哪个环节浪费了最多时间第三个问题往往最扎心因为答案通常都是“读题不够仔细”或“边界条件没想清楚”。2023ICPC网络赛已经过去但这类线上预选赛每年都会以类似的形式出现。简单题永远是网络赛的基本盘把前几题拿稳了后面的中等题才有余力去攻。希望这篇复盘能帮到正在准备ICPC的同学也希望你们在比赛中少踩我踩过的那些坑。