★ FEATURED ARTICLE 我刷Codeforces的简单思维题断断续续也有几年了最近把以前分散在收藏夹和错题本里的题目重新翻出来整理了一份“简单思维题合集”这才发现它们虽然挂着“简单”两个字但背后反复出现的思维模型其实非常集中。所谓简单思维题就是不依赖高级数据结构和复杂模板能用很短代码写完但需要你从题面里提炼性质的那类题。这篇文章不打算堆砌题解而是想把我在刷这类题时用到的方法论、几道典型的例题以及踩过的坑一起讲清楚。适合刚接触竞技编程、目标是把Rating稳定在1300左右的选手也适合想训练逻辑思维的开发者。1. 为什么我推荐多刷简单思维题1.1 思维题和算法题的区别很多人一上来就盯着动态规划、图论、数据结构刷却卡在Codeforces的A题上。原因很简单算法题是“你知道这个工具就能做”思维题是“你得先发现该用什么工具”。比如最短路知道Dijkstra就能套模板但一道A题不会告诉你“这里是最短路”它只会说“你每次能把一个数加一另一个数减一问能否让数组不下降”。如果你没有把操作抽象成“交换两个数字”的能力就算会一百个算法也白搭。简单思维题恰恰是训练这种抽象能力最便宜的材料。它不需要你先啃完几本算法书只要会用数组、循环、基本数学就能开始练。而且这类题在比赛中往往就是前两题能不能快速拿下直接决定了整场比赛的心态。我见过很多选手难题思路不少但前两题磨磨蹭蹭等开始做C题时时间已经不够了。反过来像“相邻交换”“奇偶性判断”这类题如果平时练得多比赛时几乎是秒出结论。1.2 三个实实在在的好处第一个好处是读题能力变强。Codeforces的题面很少把结论直接讲出来经常用一堆操作和条件包装。刷思维题刷多了你会养成一个习惯读完题先问自己“操作的本质是什么”“什么量是不变的”“有没有多余的条件”而不是急着写for循环。这个习惯比会某个算法更重要。第二个好处是证明能力变强。简单题要求的证明通常不长但很经典比如奇偶性分析、反证法、构造法。这些证明思路以后遇到难题一样用得上。我之前有一段时间只刷数量不复盘后来发现同样的套路换了一层皮又不会了。问题就出在没搞懂“为什么”只记住了“怎么做”。简单思维题正是补这个短板的最好工具。第三个好处更现实稳定拿分。Codeforces的计分规则里前两题的AC速度直接影响Rating。你如果能稳定地在10分钟内解决一道800分的思维题在15分钟内解决一道1200分的思维题那你的比赛下限会非常高。很多上分攻略都会强调“先把A、B题练成肌肉记忆”说的就是这件事。1.3 简单题不等于无脑题有人可能会觉得刷简单题是不是太菜了我的看法完全相反。简单题的“简单”是说实现简单但思考过程一点都不简单。你经常需要花很长时间去证明一个看起来显然的结论比如“为什么这样构造一定合法”。而这种证明能力恰恰是很多刷难题的人最缺的。毕竟难题的代码长错了不好查简单题的代码短一旦出错基本就是思考过程的问题。所以我建议哪怕你已经能稳定做出1600分的题每隔一段时间回来刷几道简单思维题也会发现新的收获。以前可能需要半小时才想通的性质现在一眼就能看穿这种对比本身就是思维成长的反馈。2. 四个常用思维模型2.1 样例先行猜结论再用暴力验证我处理一道陌生思维题的流程通常是先不急着证明直接手算样例和特殊情况。特别是那种“每次操作满足某某条件问能否达到目标”的题先写一个暴力DFS或BFS把n比较小时的所有答案打出来观察规律。比如n1到10的答案分别是true、false、true……你往往一眼就能看出周期或奇偶性规律然后顺着规律去找证明方向。这不是投机取巧因为Codeforces题目的数据范围通常很小暴力程序运行起来毫无压力。用暴力验证猜想的正确性相当于给思路上了第一层保险。我自己有一次遇到一道题操作是把一个位置上的数减一同时给两个邻居加一。当时以为需要图论建模差点放弃。后来写了个暴力跑了一下发现只要总和满足某个模3的条件就有解。顺着这个条件去证明才发现确实存在一个模3的不变量。如果没有打表我大概率还在错误方向上越走越远。2.2 找不变量看操作中什么东西没变很多简单思维题的本质是无论你怎么操作某个量始终不变然后题目要你判断目标状态能否到达你只需要检查这个不变量是否匹配。最经典的就是奇偶性。比如两个数每次可以同时加一问能否变成相等差值始终不变所以初始差值必须为零。更隐蔽的例子是操作会翻转某些状态而翻转总次数决定了某些奇偶性质。你找到不变量以后题目就压缩成一条if语句。早期我总是不重视这个工具觉得“不变量”听起来很抽象。后来刷多了才发现所谓思维题绝大多数都是在考你能不能找到那个不管怎么变都不会变的量。找不变量有个人门方法先写出状态变化前后的表达式再把每个表达式做差或者取模看哪些项被消掉了。比如两个数同时加一差值不变把数组中相邻两个数翻转1的个数变化量可能是-2、0、2所以1的个数奇偶性不变。这些都是在做差的过程中自然浮现的。2.3 构造法先明确下界再证明可达有一类题问“是否存在某种排列/方案”简单难度下通常可以用构造法解决。构造的核心是先找个足够强的候选方案然后证明它满足所有条件。最常见的是极端法把所有元素按某种顺序排序取最大的和最小的配对或者从边界开始处理或者把多余的量统一加到最大元素上。构造题为什么难因为你需要同时满足多个限制很容易顾此失彼。但简单题的限制往往只有一两个你只要抓住“最少需要多少”和“最多能做到什么程度”就能得到答案。比如后面要讲的“k个不同正整数表示n”那道题关键就是先求最小和剩余部分全部加到最大的数上这样既不破坏“不同”这个条件又能覆盖所有更大的值。2.4 把长题面压成一句话这是我个人最常用的技巧。读题时在草稿纸上写几个词输入是什么操作是什么要判断什么。然后尝试用一句话描述问题的本质。很多时候一句话写出来解法就浮出来了。比如“其实就是问数组能否通过相邻交换变成非递减序列”和“其实就是问奇数和偶数的个数差是否满足条件”两种描述给人的感觉完全不同。压缩题面的过程就是在剔除干扰信息。Codeforces的简单题特别喜欢加入“花里胡哨”的故事背景但剥掉背景以后核心往往就是一行公式。我甚至会在笔记本上专门记录“一句话翻译题面”复盘时直接看那些翻译比看原题高效得多。3. 四道典型简单思维题拆解3.1 连续正整数之和2的幂判断题目描述给定一个正整数n判断n能否表示成至少两个连续正整数的和。比如9 4 5可以8就不行。这道题刚看到时很多人会去枚举首项和长度或者做前缀和。但最简单的结论是n可以表示成连续正整数之和当且仅当n不是2的幂。为什么设连续整数有k项首项为a那么和是n k(2a k - 1) / 2如果k是奇数那么2a k - 1是偶数可以构造如果k是偶数那么2a k - 1是奇数。关键在于k或者(2ak-1)中总有一个是n的奇因子。n是2的幂时没有任何奇因子所以不可能。反过来n有大于1的奇因子时一定能找到合适的k和a。实际做题时我一般先列出n2、3、4、5、6、7、8……的结果发现只有2、4、8不行马上猜出“2的幂”。然后用上面的公式证明。代码只有几行#include bits/stdc.h using namespace std; bool canRepresent(long long n) { return (n (n - 1)) ! 0; // 不是2的幂 }这道题的坑在于题目可能要求“至少两个连续正整数”所以n1也要单独处理另外n可能很大要用long long。拿这个公式去解释样例你会发现所有数字都能对上。3.2 k个不同正整数下界即答案题目描述给定正整数n和k判断能否把n表示成k个互不相同的正整数的和。这个题第一反应是搜索但n和k都可能很大搜索完全不行。我们需要一个必要条件和一个构造方案。k个互不相同的正整数最小的和一定是1 2 ... k k(k1)/2。所以如果n小于这个最小和答案一定是NO。那如果n大于等于最小和是不是一定有解答案是YES因为我们可以把多余的部分全部加到最大的那个数上。比如k3最小和是1236如果n10我们可以取1、2、7也就是把多出来的4加到最后一项上。这样仍然互不相同仍然k项正好等于10。所以结论就是若 n k(k1)/2输出NO否则输出YES。代码同样很短#include bits/stdc.h using namespace std; bool canSplit(long long n, long long k) { long long mn k * (k 1) / 2; return n mn; }这道题教会我一个很重要的思维先求“最小消耗量”再看剩余的“资源”能不能找到一个安全的地方去。类似的问题还有“能否用k个奇数的和表示n”本质也是先看最小值和奇偶性只不过那道题多了一个奇偶条件。3.3 栈与相邻消除顺序思维题目描述给定一个字符串不断删除相邻且相同的两个字符问能否把整个字符串删空。比如“abba”可以先删中间的bb剩下“aa”再删掉所以可以清空“abc”就不能。这种题最直接的模拟就是用一个栈。从左到右扫描每个字符如果栈顶和当前字符相同就弹出栈顶相当于消除这一对否则把当前字符入栈。扫描结束后如果栈为空就说明可以全部删空。#include bits/stdc.h using namespace std; bool canErase(string s) { stackchar st; for (char c : s) { if (!st.empty() st.top() c) { st.pop(); } else { st.push(c); } } return st.empty(); }为什么这个顺序扫描一定正确因为如果一个相邻对最终会被消除那么它们之间不能隔着一个没被消除的字符。栈天然维护了“当前还没配对的字符序列”每次配对都发生在栈顶和当前字符之间这是唯一的消除顺序。这种“顺序匹配”的思维在括号匹配、单调栈问题里会反复出现。简单题里它就是赤裸裸的栈模拟但如果你理解了栈顶为什么是唯一的候选对象以后遇到更复杂的“删除k个相邻相同字符”“判断能否通过消除变成某个目标串”你就不需要重新学习了。3.4 异或找单一位运算的威力题目描述给定一个数组只有一个数出现奇数次其余所有数都出现偶数次找出这个出现奇数次的数。如果没学过异或第一反应可能是哈希表统计次数时间和空间都是O(n)也不算差。但Codeforces的简单思维题经常想要一个更干净的做法把所有数全部异或起来结果就是答案。原理只有一句话a xor a 00 xor x x。出现偶数次的数异或后全部变成0那个出现奇数次的数会留在结果里。#include bits/stdc.h using namespace std; int findOdd(vectorint a) { int x 0; for (int v : a) x ^ v; return x; }这道题看起来很“偏”但实际上它是位运算思维的入门必修课。很多人一上来就排斥位运算觉得只在竞赛里用得上。但这类思维恰恰训练你关注“性质”而不是“过程”我们不需要知道每个数字怎么配对只要知道异或运算具有交换律、结合律以及自己和自己的异或为0就能直接得到答案。刷题时我还学到一个小技巧如果题意里出现“只有一个某某”“其余都是成对”八成可以往异或方向想。类似的还有“找唯一出现两次的数”“判断两个集合是否相同”等变体。简单思维题的价值就在这里给你一个小工具然后让你在不同场景里反复认出它。4. 刷题节奏与复盘方法4.1 怎么选题不浪费时间很多人打开Codeforces题库就不知道该点什么。我的建议是根据Rating区间选800到1200的题就是通常说的“简单思维题”从这里面随机抽二三十道按顺序做就行。不需要刻意挑题型因为Codeforces的出题风格本身就很杂乱序刷反而能训练你适应不同包装的能力。但要注意别陷入“只做简单题”的舒适区。我会给自己定一条规则如果一道题在30分钟内完全没有思路直接看题解然后记录卡点如果一道题15分钟内想到了结论但不会证明就继续多想10分钟直到能说服自己。简单题是为了培养思路不是为了死磕。4.2 五问复盘法每次刷完一道简单思维题我会在错题本上回答五个问题我卡在哪一步是没想到结论还是想到结论但不会证明关键结论是从哪个样例或者哪个性质里冒出来的这道题能用哪个通用模型归类比如“不变量”“构造下界”“顺序匹配”。我的代码实现里有没有踩到数据范围、边界条件之类的坑如果把这个题改个条件结论会怎么变这五个问题看起来繁琐但只需要三五分钟。效果非常明显刷题不再是一个个孤立的点而是不断往已有框架里塞新例子。时间长了看到新题就能自动匹配“这题大概在考哪个模型”。4.3 一个完整复盘示例用上面的“连续正整数之和”举例子。我的复盘记录大概是卡点没想到2的幂一直想枚举长度。样例启示列了前几个n的结果发现2、4、8不行全是2的幂。模型归类数论下界 奇因子分析。实现坑点n1时按公式判断不是2的幂会误判为YES但题目要求至少两个数所以要单独特判。变形思考如果允许负数连续整数结论会不会变会变因为可以从负数开始几乎所有整数都能表示。这样一道题就算之后遇到它的变体我也有底气。复盘的意义不是记住这一道题而是把“看到连续和想奇因子”这条线索沉淀进思维模型里。5. 我踩过的坑和排查技巧5.1 数据范围永远是第一线索简单思维题的代码虽然短但坑经常藏在数据范围里。最典型的是int溢出。比如k(k1)/2如果k是1e9乘积直接爆int。我踩过的坑是在“k个不同正整数”那道题里k不算大但n是1e18我把k写成int结果乘法溢出后成了负数输出全反。从那以后见到乘法第一时间先估一下数量级再决定用long long还是更小心。另一个常见的边界问题是“空数组、空串、长度为1、全是同一个元素”这些极端输入。栈消除那道题如果字符串长度为1栈自然是空不了的但如果条件改成“可以任意选择相邻相同字符删除”那“aa”一开始就能删掉。类似边界一定要提前想清楚不要等WA了再怀疑人生。5.2 贪心之前先证明简单思维题里太多贪心解法了从左往右扫一遍、每次取最大、遇到就删……但贪心是WA高发区。我总结出一个规律如果你能说出“为什么当前这一步不会让后面变差”的理由那这个贪心才是可信的如果你只是觉得“好像这样比较优”那大概率会错。比如数组相邻翻转那类题从左往右扫描成立的原因是当前位只可能被当前操作影响而后面操作不会再触碰它。这叫作“决策唯一”所以可以从前往后确定。如果没有这个“唯一性”直接贪心就是撞运气。我建议在代码里顺手加assert尤其在自己的贪心结论上用断言验证中间状态至少在样例上跑不崩。5.3 用对拍和断言提高正确率很多简单题不是代码难写而是结论难证。写出一个猜测后我通常会写一个小暴力函数再写一个优化版本的函数然后枚举n比较两个结果。这一步叫对拍。Codeforces虽然可以提交但每次提交都要等待而且只能看到部分样例自己在本地跑几十组随机数据能提前杀掉大部分边界问题。断言也是好帮手。比如在“栈消除”后我可以断言最终栈内相邻字符一定不相等。再比如在连续正整数判断里我可以枚举到1000暴力判断与位运算结果是否一致。对拍和断言不会泄露到提交版本里只是帮我提升信心。如果你目前刷题流程里还没有这一步强烈建议补上尤其是做简单思维题的时候因为代码短跑对拍成本极低。6. 写在最后的个人体会6.1 题感是怎么来的经常有人问我为什么别人看题一眼就有思路我却要半天我的体会是所谓题感其实是在大量“预期与结果”的匹配中形成的。你见过的“连续和”和“2的幂”联系越多以后看到类似数字形状就越敏感你把长题面翻译成一句话的次数越多下次剥包装的速度就越快。我给自己的最低要求是每一道简单思维题不仅要做出AC还要能在不看题解的情况下用三句话向别人讲清楚“结论是什么、为什么、边界在哪”。如果讲不清楚说明我还没真正理解。6.2 简单思维题的扩展应用别小看这些简单模型。相邻交换的思维会继续出现在排序类难题里栈的匹配思想会延伸到括号序列、单调栈、最长有效括号异或运算更是在很多中等难度题里充当核心子问题。换句话说简单思维题不是终点而是建立自信和熟练度的起点。我目前还会在每周末专门抽出一个小时随机刷十道800到1200的题不追求速度只追求每道题都能复述出它的思维模型。这已经成了我的热身方式。如果你刚起步我也建议从这份“简单思维题合集”的思路开始不求贪多每天三五道坚持一个月你会明显感受到自己看题时脑子的转速变化。
阅读完成 · 觉得有帮助？
