2020 腾讯程序设计竞赛(二)

作者: | 更新日期:

我废了。

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

一、背景

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

比赛时间依旧非常不好,依旧是比赛前五分钟准备好环境,结果第一题被卡住了,恰好有人喊着开会,我就溜了。

赛后看了下题目,中间两道题我都可以做出来。
第一题题目有问题,不一定能做出来。 最后一题我做不出来。

总的来说,我废了,一道题也没做出来。

一、IPV6转换

题意:给一个缩写的IPV6,求缩写前的IPV6。
IPV6:IPV6 是由 128 位地址组成,每 16 位一组,分为 8 组,组之间是有一个冒号分割。 另外每组使用 16 进制表示。
缩写:去除前导零,连续多组 0 可以合并为一对冒号 :: 表示,但是只能合并一次。
特例:对于起始连续的前导 0 可以缩写为 ::1
样例:2c0f:9981:::: 也是一种缩写。

分析:

根据题意,可以推断出输入数据分几类。

-)无缩写。
-)中间缩写,例如 1::2
-)前缀缩写,例如::1:2
-)后缀缩写,例如1:2::
-)全缩写,例如::

如果你按照这五类来编写代码的话,看你怎么实现了。

如果运气好,就会一下就过了,如果运气不好,那就被卡到怀疑人生。

据说输入的样例有这样的:

前缀是 :1:2 和 后缀 1:2:

如果像我这样,找规律根据长度来计算答案的话,就会被卡主。
而使用前后缀的方法来做这道题的话,就几乎不会被卡主了吧。

二、糖果

题意:Alice 和 Bob 买了一些糖果,开始了博弈游戏。

-)Alice 和 Bob 轮流拿取糖果。
-)轮到 Alice 时,每次她必须拿走恰好一颗糖果。
-)轮到 Bob 时,每次他必须拿走至少两颗口味相同的糖果。
-)轮到 Alice 时,若没有剩余糖果可以拿取,则判 Alice 输。
-)轮到 Bob 时,若不存在两颗口味相同的糖果,则判 Bob 输。

输入告诉你谁先走,问最终的胜利者。

分析:对于博弈题,一般是找规律。

所以我们按糖果个数分情况来讨论。

-)某个口味糖果至少一个。

对于那些单口味糖果, Bob 永远无法拿走。
而 Alice 可以最后那单口味糖果。
所以 Alice 必胜。

-)某个口味糖果至少三个。

假设 Alice 先走,只能选一个口味糖果取走一个。此时 Bob 把那个口味剩下的糖果都拿走。这样策略坚持到最后,此时 Bob 胜。
假设 Bob 先走,随便选一个口味糖果全部拿走,则变成 Alice 先走了。所以还是 Bob 必胜。
所以 Bob 必胜。

-)某个口味糖果至少二个。

如果 Alice 先走,赶紧拿走一个,就会变成情况一了,此时 Alice 必胜。
如果 Bob 先走,如果那些两个糖果口味只有一个,Bob 拿走后就变成 情况二了,Bob 必胜。
否则 Bob 不管怎么操作,下一步 Alice 拿走一个,就变成情况一,Alice 必胜。

就这样,三种情况都梳理出来后,我们就可以得到答案了。

三、幸运字符串

题意:如果一个字符串还有子串 TPC,则称为幸运字符串。
如果不存在幸运字符串时,可以通过多次翻转子串来构造出幸运字符串,求最小翻转次数。

例如:TACP 翻转 ACP 后可以得到 TPCA,就包含幸运字符串。

思路:暴力枚举所有情况即可。

大概存在下面几种情况。

-)TPC
-)TPxxC
-)TxxPC
-)TxPxC
-)TxxCP
-)TxCxP
-)…

情况很多,但是可以一一枚举出来,然后就可以做出这道题了。

四、最长上升子序列

题意:对于一个序列,可以找到一个最长上升的子序列。
那如果给二元序列,序列的值是[max,min],求构造一个上升子序列,使得序列的值在二元对之内,并且子序列的长度最大。

这道题完全没思路,放弃。

五、最后

这次比赛的题其实非常不好。

第一题不告诉完整题意,需要去猜测输入的数据是啥。如果按照题目描述,将会被卡主。
第二题博弈题,还算不错,不过算是找规律题了。
第三题枚举题。
第四题不会做。

不喜欢这次比赛,除了博弈题有点质量,其他的考查不出什么来了。

《完》

-EOF-

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

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

点击查看评论

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

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

tiankonguse +
穿越