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

作者: | 更新日期:

讨厌 Mac 笔记本。

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

零、背景

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

这次时间很充足,比赛前十五分钟就吃完饭上楼了。

可是这次我忘记带 wondows 笔记本了,公司之后一个 Mac Pro 笔记本,还没鼠标,我不会玩。

这个比赛电脑也为后面的比赛买下了伏笔。

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

一、劳动七号

题意:劳动七号是人气 MMORPG《最终幻想 14》中 24 人团队任务“封闭圣塔黎铎拉纳大灯塔”的第三个 boss。
在打这个 boss 的时候,需要按照劳动七号的指令,进入或远离场上四个代表 1,2,3 和 4 的圆形区域调整自己的体力,以躲避接下来的攻击。

劳动七号会使用以下四种指令中的一种:

  • 算术 - 3 的倍数(Divide by Three):需要调整自己的体力为 3 的倍数;
  • 算术 - 4 的倍数(Divide by Four):需要调整自己的体力为 4 的倍数;
  • 算术 - 5 的倍数(Divide by Five):需要调整自己的体力为 5 的倍数;
  • 算术 - 质数(Indivisible):需要调整自己的体力为质数。

若玩家初始的体力值为 h,当他进入代表 c 的圆形区域后,他的体力值会被调整为 (h+c)。
PS:这里 c 就是上面的 1,2,3,4 四个区域,也就是体力值可以加 1~4。
如果没有进入任何圆形区域,那么体力值不变。

问根据指令,应该依次进入哪个区域?

要求:每次做出选择后,需要使自己的体力值最小。
解释:什么是体力值最小呢?比如现在体力值是 2,选择区域 1 可以使得体力值变成 3 的倍数,选择区域 4 也可以使得体力值变成 3 的倍数,我们需要选择小的那个。

输入体力值:1~9。

思路:对于倍数,直接运算,对于素数,枚举即可。

对于倍数,取模看还差几个,就加几即可。

对于素数,对应关系如下

1 + 1 = 2  
2 + 0 = 2  
3 + 0 = 2  
4 + 1 = 5  
5 + 0 = 5  
6 + 1 = 7  
7 + 0 = 7  
8 + 3 = 11  
9 + 2 = 11  

二、并非斐波那契

题意:给一个二进制字符串 s1s2s3...sn,现在需要重新排列这个二进制,使得s[i] + s[i+1] != s[i+2]
如果存在多组答案,返回任意一个,如果不存在,返回Impossible

思路:状态机或者找规律。

根据不等式,画出一元状态机,就可以发现一个规律。

我们可以发现,如果出现0,必须连续出现两个,然后可以出现任意个1。

那我们使用插板法,每两个 0 插入一个 1 即可。

另外,根据不等式,还可以画出一个二元组的状态机。

枚举起点,也可以判断出所有可能的情况,我就是使用这个状态机枚举过的。

三、循环质数

题意:给一个数字,如果不断循环右移得到的数字都是素数,则称这个数字是循环素数。

我们可以发现,循环素数是一组一组的,而且 N 位数的循环素数肯定是 N 个一组。

另外,N 大于 1 的时候,可以发现所有数字必须是 1、3、7、9四个数字,其他数字当做位数时肯定不是素数。

要求:给一个数字字符串,找出最大的循环素数子串。

思路:没啥想法,先把1亿以内的循环素数打印出来看看有啥规律。

结果打印出来后,发现到第 6 位之后,就找不到了。

于是大胆猜测循环素数只有这么几个,从大到小判断是不是子串即可。

四、最小序列生成树

题意:一棵树从根节点触发,可以求出一个最小生成序列。
现在给一个图,找到一个生成树,使得这个生成树的最小生成序列最大。

思路:题意一开始看不懂,看懂的时候没啥思路,不会做。

五、最后

这次比赛据说第三题比较坑,据说存在很大的循环素数。

官方给出的答案是使用大素数测试来判断 20 位内的正数是不是答案。
因为数据是随机生成的,大于 20 位的答案概率非常小,可以忽略。

这句话说白了就是,存在很大的循环素数,但是数据中没有。
所以我也不需要大素数测试了,直接子串查找水过去了。

思考题:最后一题你有思路吗?

《完》

-EOF-

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

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

点击查看评论

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

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

tiankonguse +
穿越