昨天晚上给参与校内赛的同学在钉钉上录制的直播视频,我基本上把这些题目都谈到了,因为我后面确实时间和精力有限,在这里我就简单说一下主要的要点:
https://www.bilibili.com/video/BV1kT4y1A7Ms?t=747
K1-Known-Well Palindrome Date - Easy Version
题目不难,但细节比较多,也难倒了部分本校同学:
首先注意题面中说的数字片段(a series of identification number periods)意味着这道题的数据每段数据的量不是固定的,而且空格也未必是固定的;
因此这里面会出现总长度不足8位的串,加上空格共同构成回文串的串等特殊情况;
其次就是关于日期的合法性,月份和日期为0不是有效日期,注意不同月份的天数不同;
然后就是大家都在比赛中问到的闰年的问题,实质上无需判断,但是你们既然问了,我们也只能回答要考虑这种情况,这里要务必注意:回文串限制了很多信息,哪怕是最特殊的92200229这种情况,也一定是成立的,因为年份20结尾必定被4整除而不会被100整除;
这部分日期判断错了本题是一定不会通过的,因为后台故意有一组数据就是从00000000到99999999的数据。
K2-Known-Well Palindrome Date - Hard Version
只要大家在上一题的基础上想到回文串会限制很多信息,而本题的进一步限制是只考虑2000-2099年的情况,那也就意味着只考虑20XXXX02的情况,实际需要讨论的总共12种情况,就是月份从1月到12月,即使你是分别去DP求前缀和,也是非常容易的。
L-Link Game of Prime Factors
这个题目当初设计的时候就是想做为本场压轴题之一,取材是今年最强大脑7的一个新出的小游戏叫做数字连连看,详细规则可以看这个https://www.iqiyi.com/v_19rzcxmvgs.html,虽然我确实是尽力把规则在题面里说清楚了,但可能太长了有人不愿意看;
题目的难点在于这个游戏的无解情况可以有很多种类型,我不敢说我的标程能确保全部讨论清楚,但是测试数据一定是没问题的,因为数据全部是我根据游戏遇到过的一些状况自己编的,没有刻意的随机造数据;
- 题目由于出现单独的质因子,导致本身自身无解;
- 题目出现无法与之匹配的质因子的高次幂(样例2情况),例如25,49,121,32,64,128这种数字,要判断是否可以消除;
以上两种情况均可以通过预处理解决,我的做法是对每种质因子构造一个优先队列,每次选两个次数最大的数字消除,消除结果再放回队列中,如果不能完全消除就是无解; - 题目出现连连看自带的无解情况,包括但不限于交叉田字格自身无解(样例3情况),环形封闭无解情况,但是其本质均是一对质因子对的交叉;
以上情况我的做法是直接对这个无解区域(包括周围的一圈元素)中的每个元素做判断,根据连连看规则消除,如果其中任意一个质因子能够被外部其他元素消除,即为有解;当整个区域均无法继续操作,即为无解;
考虑好上述无解情况,其他情况均为有解。
M-Magic Cube Battle
本题是2013年长沙区域赛改编过来的,就单纯改了一下问法,也是我为了控制整个比赛难度临时添上来的题目,注意每次转动魔方会有12个格子的相对位置发生改变,不要对错号即可,题目整体思路很简单,但是代码量大。