2020 腾讯程序设计竞赛（四）

零、背景

周三晚上参加了腾讯举办的2020 TPC 程序设计竞赛第四场比赛。

这次时间很充足，比赛前半个小时就吃完饭上楼了，期间还刷了一会微博。

这次带了自己的 windows 电脑，比赛比较顺利，做了三道题。

结果到第四道题时，怎么看构造不出测试数据来，最后发现看错题了，群里反复沟通后才看懂了题意，悲剧。

下面看看这次做的几道题吧。

一、彩票

题目：给一个矩阵，计算出每行之和 Ri、每列之和 Ci、对角线之和 P、反对角线之和 A，前面所有的和再次求和就是彩票的奖金。

现在有一个机会交换矩阵的两个位置的值，问怎么交换才能使奖金最大。

思路：可以发现矩阵的点分三类：

A：中心节点求和四次
B：对角线点求和三次
C：其他点求和两次

相同分类内的点交换没有意义，不同分类之间的点交换后可能提高奖金。

具体来说就是：

1、B 分类里的最小值 与 C 分类里的最大值交换
2、A 分类里的最小值 与 C 分类里的最大值交换
3、A 分类里的最小值 与 B 分类里的最大值交换

最后取最大值即可。

二、几乎有序的序列

题目：对于长度为 n 的序列，前 n/2 元素里的最大值 小于等于 后 n/2 元素里的最小值，则该序列称为几乎有序。

现在给一个序列，可以挑选两个位置，代价是下标之差。
求使序列变为几乎有序的最小代价。

思路：对于几乎有序序列，前后两部分看做两个集合。
则后半部集合的任何元素都不小于前半部集合的任何元素。

所以我们可以先将序列排序，排序后的前后集合和排序前的集合去除重复数据。

可以发现，求交集后，剩下的哪些就是需要交换的元素。

由于最优值是下标之差，所以对于前半部集合，需要尽可能的交换较大的下标，对于后半部集合，尽可能交换较小的下标。

PS：当然，排序后计算出中位数会更简单。
不过当遇到与中位数相等的值时，下标需要处理好。

三、数字分组

题目：给 n 个正整数，求将数字分成两个集合，使得两个集合元素之和相差最小。
注意实现：所有数字之和为 sum，则 sum < 2n-2。
数据范围：n = 2*10^5

思路：第一眼一看，典型的带记录路径的 0/1 背包问题。

具体来说背包大小是 sum/2，重量和价值都是整数的值，求价值最大。
但是一分析复杂度，O(nm)，在 Acm 中会超时，这次比赛是按 Acm，那肯定会超时了。

不过我想试一试，也就两层循环，水过去了就爽了。
结果在倒数第二组样例的时候被卡主了。

此时在看题意，可以大胆猜测 sum < 2n-2 肯定是突破口。

n个数字，值至少是1，和有不超过 2n-2，那显然存在两个1，其他的都是2。
如果存在更大的数字，则存在更多的1。

所以我们可以直接贪心做这道题。
即直接从大到小选择可以放入背包的数字，最终肯定可以把背包放满的。

证明也很简单，这里就不证明了。

四、反二叉搜索树

题意如下图

我比赛的时候看错题了，看成三个条件都需要满足，样例构造不出来答案。

后来讨论的时候，有人说任意一个节点满足就可以了，我又误以为左右节点代表左子树里面的任意一个节点。
此时样例还是不出答案来。

再后来反复读题，发现原来是三个条件只要满足一个就行了。
这样左右节点确实是亲儿子了，但是没啥思路。

后来又一想，只要三个节点的值不同，肯定可以构造出一个满足条件的局部树来。
那不存在答案的情况就是相同的节点太多了。

再往后想不动了，大家可以自己思考一下。

五、最后

四场比赛终于做完了，我只有最后一场比赛进入前 50 名了，前面三次惨不忍睹，综合排名应该是百名只外了。

想起了大学的一段时期，大概也是这个时候，比赛会超常发挥。
那段时光不管是省赛，还是东北四省赛，都意气风发。
可是过了那段时间，我就变成了一个普通人。

思考题：一年中一个人的比赛状态都与什么有关？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code