Codeforces 651C是一道考察核心观察的入门级思维题,背景是给定一个满足“相邻元素差的绝对值严格递增、无重复”的整数队列,要求每次取队列两端差值更大的相邻对删较小数,输出每次删去的元素,初看易尝试暴力模拟找中间所有差值,但实际因唯一严格增差的条件,更大差值只会出现在当前左右端点的相邻对上,只需双指针从两端逐次删除较小的边界元素即可,复杂度线性。
提到全球知名的编程竞赛平台Codeforces,很多入门者都会对“CF”开头的场次编号格外熟悉——其中CF651(即Codeforces Round #345 (Div. 2))更是不少人的“思维启蒙场”,这场2016年举办的Div.2比赛,题目难度梯度友好,尤其是之一道题,用看似简单的设定,藏着一个让新手恍然大悟的思维点。
先聊聊CF651的背景
Codeforces的Div.2场次主要面向竞赛新手,题目从“签到题”到中等难度不等,核心是考察对问题的理解而非复杂的代码技巧,CF651就是这样一场典型的比赛:它没有刁钻的算法,却逼着你跳出“按题目描述硬做”的惯性,先去想“问题到底在问什么”。
最经典的那道题:CF651A Watchmen
让我们从这场比赛的之一道题说起——题目叫《Watchmen》(守望者),大意是:平面上有n个守望者,每个的坐标是(xi, yi),问有多少对守望者,他们的曼哈顿距离等于欧几里得距离?
先简单解释两个距离:
- 曼哈顿距离:|x1 - x2| + |y1 - y2|(像走网格路,只能横平竖直);
- 欧几里得距离:√[(x1 - x2)² + (y1 - y2)²](直线距离)。
如果按“暴力解法”,你可能会想:把所有点对列出来,分别算两种距离再比较——但n如果是1e5,这样O(n²)的计算肯定会超时,这时候,CF651A的妙处就来了:先别急着算,先推推数学公式。
我们把两个距离相等的条件写出来: |x1 - x2| + |y1 - y2| = √[(x1 - x2)² + (y1 - y2)²]
两边同时平方(因为两边都是非负数),左边展开是: (|x1 - x2| + |y1 - y2|)² = (x1 - x2)² + 2·|x1 - x2|·|y1 - y2| + (y1 - y2)²
右边平方后是: (x1 - x2)² + (y1 - y2)²
两边相等的话,中间的交叉项必须为0,也就是: 2·|x1 - x2|·|y1 - y2| = 0
哦!原来如此——要么两个点的x坐标相同,要么y坐标相同!问题瞬间简化了:不用算距离,只要统计“有多少对点x一样”加上“有多少对点y一样”就行。
比如统计所有点的x坐标,假设某个x出现了k次,那对应的点对就是k*(k-1)/2;y坐标同理,最后把两部分加起来,就是答案。
CF651告诉我们的事
这道题只是CF651里的“开胃菜”,却精准击中了编程竞赛的核心:重思维,轻代码,很多时候,你不需要写复杂的循环或数据结构,只要先停下来想“问题的本质是什么”,就能把看似麻烦的事变得简单。
后来很多人回头看CF651,都会说这是一道“更好的入门题”——它不是让你背算法,而是教你“换个角度看问题”:从“计算距离”到“统计坐标重复”,这一步小小的思维跳跃,往往就是解题的关键。
CF651的题目依然在Codeforces上被无数新手刷过,或许再过很多年,大家还会想起这场比赛,想起那道让自己之一次感受到“编程竞赛乐趣”的Watchmen——毕竟,比起写出能跑的代码,想通一个巧妙的思路,才是最让人开心的事。
