2020 TPC 腾讯程序设计竞赛（五）

零、背景

2020 TPC 腾讯程序设计竞赛第二季开始了。

周二晚上我参加了第二季的第一场比赛。

比赛的时候，我各种失误，每次提交都先 WA 一次，不过好在自己速度快点，有幸做了三道题，进去了前百名。

进去前百名的话，至少一件衣服到手了，只是不能叠加衣服，有点遗憾。

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

一、Future of Tencent

题目：数字大于 0 输出 You are the future of Tencent!，否则输出Good luck and Enjoy TPC!。

思路：签到题。

二、Source of Happiness

题目：每天一个数字，连续三天的数字之和大于 m，则称第三天是 Happy 的。
给 n 天数字，由于一些原因某些天的数字不见了，使用 -1 表示。

对于数字不见的天数，我们可以赋值为任意数字。
问是否可以通过赋值，使得第三天之后每一天都是 happy 的，如果可以，求 n 天数字的最小和。

思路：由于天数只有 3 天，直接贪心即可。

记录最近一次可以随意赋值的位置。
如果最近三天不是 happy 的，则判断是否可以随意赋值，可以了就缺多少就补多少。

三、BFS Sequence

题意：给一棵树的两个 BFS 序列，如果存在树，则输出这颗树每个节点的父节点。
由于有很多答案，输出树高最大的那个树。

根节点入队，每次出队一个节点，之后这个节点的儿子节点入队的顺序随意，形成的序列就是 BFS 序列。

如上图，根节点是 3，第二层三个儿子 1、4、8 入队顺序随意，所以就可以产生三种情况。
第三层里，4有两个儿子，顺序也是随意的。
所以这个树共有 6 中不同的 BFS 序列。

3 4 8 1 5 6 7 2
3 1 8 4 2 7 5 6

思路：一分析，发现通过两个 BFS 序列，可以将序列垂直划分为等长的几块， 每块都是一层，而且在群论中都是闭环的。

所以我们分块后，就可以知道最优答案的树高了。

那每块的父节点该如何划分呢？

再一分析，发现每层的节点的父节点是谁是没影响的。
也就是每层的节点的父节点可以都是上一层的第一个节点。

这样分块后，直接贪心将上一层的第一个节点当做父节点即可。

群论分块的思想也很简单。
第一个序列中选一个元素加入集合1，然后不断的在第二个序列中找选的元素。
第二个序列找元素的过程中，遍历的元素都加入到集合2。
可以证明，两个集合相等的时候，就是找到一个闭环分块的时候。

四、Color Palette

题目：有三种基础颜色ryb和三种中间颜色opg，以及黑色x。
两种颜色可以进行按照顺序进行混合，关系如下：

上图之外的颜色混合的时候，将会保留后面的颜色。
比如o+r=r，x+b=b等等。

可以发现，上面的颜色混合不满足结合律。

现在给一个颜色序列，然后有两个操作。

1）指定区间的颜色设置为 c。
2）查询指定区间从左到右混合后的颜色。

思路：看到区间操作很容易想到线段树。
可是区间操作不满足结合律，线段树的区间合并就无法进行了。

赛后讨论，有人直接找最后若干个暴力计算，有人倒着找连续的颜色然后暴力计算，竟然都水过去了。
而标准答案还是线段树。

对于一个区间，左区间输入的颜色决定了区间最后计算出的颜色。
那能不能枚举所有的输入颜色呢？
颜色只有 7 种，还真可以。

这样区间合并的时候，左区间的输入颜色就是右区间的输出颜色，合并后还是其中枚举情况。

另外，题目中给的颜色混合公式可以发现是 bit 位的或运算，所以我们可以使用 bit 位来管理运算关系。

之后就是线段树的标准操作了。

五、UAV Network Deployment

题意：相当复杂，就不介绍了。

六、最后

这次比赛的题还不错，尤其是线段树那道题，很有意思，只是当时没做出来，可惜了。

思考题：你有线段树模板吗？需要我分析一个模板吗？

《完》

-EOF-

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