2020 TPC 腾讯程序设计竞赛(六)

作者: | 更新日期:

题很好,最后发现除了移到模拟题,其他全是贪心题。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

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

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

比赛的时候,脑子卡壳了,加上代码敲的慢,每道题都做了几十分钟才做出来。
不过还好,这次比较细心,每次都是一次通过,有幸做出三道题,进入前百名。

不过也有可惜的地方,手速再快几分钟,就可以进入前 50 名。 。

意外发现,上次进入前百名获得了京东卡 50 元, 这次又进前百名,又可以得到京东卡 50 元,爽歪歪。

一、A Binary String Flipping

题意:给一个 01 字符串,我们可以选择一个区间,将所有数字反转(0变成1,1变成0),使得 0 与 1 的个数差最小。

思路:脑子卡壳了,这道题搞了四十分钟。

我们不妨假设 1 比较多,且 1 比 0 多 K个。
如果 0 比较多的时候,对整个字符串预处理反转一下。
这个时候,如果可以找到一个区间,1 比 0 多 K/2 个,那对其反转,就可以使得 0 与 1 的个数差最小了。

怎么找到一个区间,使得 1 比 0 多 K/2 个呢?
我第一时间想到的是最大区间和的思想,即使用动态规划来做这道题。
具体来说从左到右扫描区间,如果遇到 0 的个数多余 1 的,区间就重置。 由于总区间 1 的个数比较多,肯定可以找到最优答案。

当然,赛后看题解发现自己想复杂了。
既然 1 比 0 多 K 个, 那从最左边为起点,在所有的前缀中,1 比 0 多的前缀里,肯定会出现多 [1, K] 个。
也就是肯定存在某个前缀,1 比 0 多 K/2 个。
所以最简单的方法是枚举前缀即可。

二、Recruitment Plan

题意:招聘了,有 n 个候选人,会招 m 个人,其中一个是 SP。
告诉你每个候选人的招聘代价、入职后创造的价值、SP额外招聘代价、SP额外创造的价值。
问怎么选才能使得 m 个人创造的价值最大,在此基础上招聘代价应该尽量小。

思路:数据范围很小,直接暴力 dfs 即可。

当然,这道题也可以贪心做,即先排序,求前 m 个或者 M-1 个人的和,再枚举 SP 调整和即可。

三、Divisible Sequence

题目:给一个数组,如果任意子数组内都存在一个数,可以被子数组中其他数字整除,则称这个数组是可除数组。

思路:我第一时间想到的是单调栈来贪心。

可以看相邻两个数字,因为任意区间都是可除数组,所以相邻的两个数字肯定也是可除的。

相邻数字 a, b 分三种情况:

1、前面的数字大,即是 a=k * b, b
此时 b 的所有后缀中,选择的数字如果是 b 的因子,那肯定也是 a 的因子。
如果 b 是选择的数字,那 a 也可以整除 b。
所以所有包含 a,b的子数组中,只需要判断 b 即可,a 可以直接删除的。

2、两个数字相等
这个与前面的情况类似,删除保留一个即可。

3、后面的数字大,即是a, b=k * a
此时如果 某个数字是 b 的因子,我们无法判断与 a 的关系,所以需要保存下来。

这样,我们就保存了一个递增的栈,一层循环即可解决问题。

当然,如果没想到贪心,能想到被整除的数字是子数组中的最小数字。
就可以得出最小数字是子数组的 GCD 这个结论。
然后就可以使用分治来解决这个问题。

可以证明,gcd(l, r) = gcd(gcd(l, m), gcd(m+1, r)))
即可以拆分出两个子问题,通过并查集合并或者分治合并子问题,复杂度 n log(n)

四、Persistent String

题意:给一个字符串和三个操作。

1、在指定位置后插入一个新的字符串。
2、对于指定的子字符串,在指定位置插入若干次。
3、查询指定位置的字符。

思路:一看操作数只有几千个,我第一时间想到的就是预先输入所有数据,然后倒退计算出每个询问的位置应该映射到哪个字符上。

不过考虑到时间不多了,又发现最后一题是贪心大水题,就跳过这道题了。
后来发现,还是自己太年轻,只想到第一层。
没去想,这么多大牛,很多都是很快做出前四道题的,第五题却迟迟没做出来。
如果多想一层,假设是这么简单的贪心题,我能想到,那些大牛肯定也想到了。
但是那些大牛没做出来,说明这样贪心肯定是错的。

以后做题做事还是要多想,就像《三体》里章北海的父亲说的,“那”之前要多想。

回到这道题,既然可以预处理倒推计算,那就是一道大的模拟题了。

不过这里面也用到了不少小技巧,下面讲解一下。

小技巧1:输入了很多字符串,只告诉总长度,每个都是变长的。 这时候可以使用二维数组的指针指向一维数组的偏移量即可。

小技巧2:由于是倒推计算,循环完了可能某些查询的答案在原字符串上,还需要再判断一次。此时可以把原字符串也当做一个插入操作。

小技巧3:对于单字符串输入,很多人会遇到空白问题。这里可以使用字符串输出,字符串长度为 1 。

至于具体的模拟代码,就没啥好说的,按照题意逆着倒退即可。

就是那些偏移量,可能很多人会再也偏移不出来了吧。

五、A + B Problem

题意:给一个 01 字符串,以及需要拆分的两个子序列长度。
问怎样拆分,才会使两个子序列对应的二进制数字的和最大。

思路:第四题的时候啰嗦了几句,说自己想的太简单,放弃第四题来做贪心第五题了。

当然,当时肯定是没做出来啦。

错误的贪心方法:遍历 01 字符串。

1、如果遇到 1,则赋值给剩余 位数较多的子序列。
2、如果遇到 0,则赋值给剩余位数较少的子序列。

这样的目的是为了使 1 尽量靠前。
但是,这样的贪心做法是没法通过的。

比如对于 10111 , 这个特殊数据,按照上面的贪心。就会拆分为 111 和 01 序列,结果是 1000。
但是如果拆分为 10 和 111 序列,答案会更优,是 1001。

之所以会这样,是由于两个子序列的高位很接近的时候,尝试给较短序列高位赋值为1,可以在更高的位数触发进位。

那什么情况会这样呢?
较短的子序列赋值 为 1 后,尝试把剩余 1 都赋值给较长的子序列,0 都赋值给较短的子序列,直到和 1 对齐触发进位。
如果可以触发进位,则这种情况会更优,否则,与上面的贪心策略保持一样。

这种特殊的情况需要向后去探测,裸写的话肯定会超时。
所以需要读数据进行预处理,在一个位置遇到 1 之后,我们能够快速找到性遍历到哪个位置才能凑齐 K 个1。

这个通过计算 1 的前缀和,然后二分查找即可实现。 当然,直接做一个 1 个数 到 下标的索引,连二分查找都不用了。

找到最优答案后,就是大整数加法运算了,这也是题目的来源。

六、最后

这次比赛的题依旧不错。

第一题:贪心或动态规划。
第二题:贪心或dfs暴力。
第三题:贪心或者线段树或者分治。
第四题:逆向模拟或者可持久化平衡树。
第五题:贪心。

好吧,这次比赛是贪心专场。

思考题:第四题能使用 RMQ 或者 ST表 来做吗?

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越