【算法日记 08】一行代码秒杀！当“程序模拟”变成“数学脑筋急转弯”

【算法日记 08】一行代码秒杀当“程序模拟”变成“数学脑筋急转弯” 场景引入今天在刷题时遇到了一个极其“唬人”的题目题目大意给定一组正整数问其中有几个数可以被分解为**“连续递增的整数序列”**之和三个极其关键的条件序列长度至少为 3。相邻元素之差必须为 1。可以包括正整数、负整数或 0⚠️ 极度危险的暗示面对这道题很多人的第一直觉包括我最开始是写循环去暴力枚举是不是3*j 3是不是用等差数列求和公式去倒推方程如果你这么想恭喜你你已经完美掉进了出题人为你精心挖好的连环大坑里 暴力解法的死胡同如果我们顺着常规思路去凑数字比如凑5找两个数2 3 5不行题目要求长度≥3\ge 3≥3。找五个数-1 0 1 2 3 5可以但我们要用程序把所有可能的组合都跑一遍吗如果给的数据极大一定会 TLE超时。其实这道题的破局点就藏在那个看似不起眼的条件里“可以包括负数”。✨ 满级降维打击正负抵消大法既然题目允许用负数那我们为什么不耍点“流氓”直接用负数把前面的数字全抵消掉呢假设我们要凑出数字A以A 5为例我们可以极其暴力地构造这样一个序列[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]看出规律了吗求和完美从-4到4的数字两两相加全变成了0完美抵消最后这串长长的序列总和绝对等于5长度达标这个序列从-(A-1)一直连续到A它的总长度永远是2A2A2A。对于5来说长度是 10远远满足了题目中“长度≥3\ge 3≥3”的要求 终极规律推导根据上面的“作弊”公式对于任意一个正整数AAA我们都能构造出一个长度为2A2A2A且和为AAA的序列。题目唯一的要求是长度必须≥3\ge 3≥3。即2A≥32A \ge 32A≥3。因为AAA是正整数所以得出唯一结论只要A≥2A \ge 2A≥2它就绝对能被分解那A1A 1A1呢如果凑 1根据公式长度是 2 ([0, 1])不达标。在数学上连续 3 个及以上的整数之和为 1 也是绝对无解的。 光速 AC 代码连数组都不用开推导到这里这道题的底牌已经被我们看穿了。我们根本不需要什么复杂的循环甚至连数组vector都不需要开只需要一边读入数据一边数一数“有几个数字是≥2\ge 2≥2的”即可。时间复杂度O(N)O(N)O(N)空间复杂度O(1)O(1)O(1)绝对的降维打击#includeiostreamusingnamespacestd;intmain(){// 读写极速引擎ios::sync_with_stdio(false);cin.tie(0);intn;// 养成好习惯严谨读入防越界if(!(cinn))return0;intcount0;for(inti0;in;i){inta;cina;// 边读边处理极致省空间// 终极降维打击只要数字大于等于 2就绝对能分解if(a2){count;}}coutcount\n;// 极速换行return0;} 总结在算法竞赛中当你发现一道题按照正常思路写起来无比复杂、边界条件多到让人抓狂时不妨停下敲键盘的手去重新读一遍题干里的“特殊条件”。很多时候打败程序的不是更强的算法而是极其优美的数学逻辑。这道题的“正负抵消大法”就是最好的证明