开考
题目难度应该是升序的,开 T1 发现看着不简单,就有点突突。
T2 看起来比较简单,想到了双指针,但是方向不对,搞了 20min 出不来就回去看 T1。
开写
T1 想出来就很好写了,想到两个点就可以组成一条边从而确定一个正方形(当然没有对角线),直接 \(\mathcal{O}(n^2)\) 暴力枚举判断就可以了,用到一点点割补法和勾股,小学内容。
再返回看 T2,觉得排序后应该是结论题,但是好像不是,也没怎么找到单调性,先过,观察一下部分分,但是好像不知道怎么暴力,感觉要挂。
去搞 T3,刚开始想出了 \(\mathcal{O}(n\log^2n+n^2\log n)\) 的解法,尝试去枚举(预处理)所有质因数,认为有希望,但是(吸取了上次教训)又重新过了一遍架构,发现锅了,贪心不可行,果断放弃去看 T4(赛后证明当时放弃是对的,不然只会在错误的路上一去不复返),当时琢磨着这么大的范围怎么也不可能是状压,不过赛后戏剧性的事情又发生了。
开 T4,其实对自己当时已经没什么希望了,但是还是想垂死挣扎一下,事实证明看到字符串只去想 kmp、哈希、trie 甚至 AC 自动机是不对的,看着像字符串甚至可能是数论,比如这题。
头脑风暴之后发现可能是乱搞的组合数?只用倒着看就从删数变成了加数。
题目里给出的模数 \(1000000007\) 是个大质数,于是我想到了...费马小定理。
其实想到费马小定理的时候我感觉已经完蛋了,但是还是去糊一下,竟然胡出来了!样例也过,说实话,当时真的开心极了,虽然只写出来两道,但是这道题胡出来真的特别骄傲,感觉这道题比较有难度,写完之后对自己的思维也有很大提升,一会记录一下那道题。
最后中间那两道也没写出来。
出分
180pts,感觉是 T4 少 20pts,但是老师说好像拿满了?那就是 T1 挂了?个人不太相信,因为仔细检查过不可能炸,等下午。
知识纰漏
T1 其实不需要单独说什么,但是觉得有的题真的只是一句话的事,想到了就切,想不到就没。
T2 第二题确实是双指针,但是与原来的单调性不同,这次的单调性可以说是很不明显,而且发现其实有的时候双指针并不是正解,他可能只是解题的一个小步骤,可以说很多题都是用不同算法拼出来的,所以很多算法可能就是一句话的事。
T3 真的是状压...其实这次也提供了另一种思路,解决一道题的方法:想出正解和改变题目。这个“改变题目”当然不是去单杀出题人,而是通过一系列操作达到转化题意或者发掘潜在的数据范围的目的。比如这道题,看似 \(n\le1000\) 不能状压,其实只要考虑到 \(n\) 大于 \(\sqrt{n}\) 的质因子至多有一个就好了,数据范围就 \(n->\sqrt{n}\le31\),又注意到 \(31\) 一下的质数只有 \(11\) 个,这样就可以状压了,对于大于 \(\sqrt{n}\) 的质数,分组背包即可(这道题就糅合了两个东西)。
T4 写出来是真的开心,发现有的题真的跨度大,这次用到了数学知识,而且很细节,处理方法很巧妙,继续努力。
策略得失
首先还是要先切一道题,这样不管是实际上还是心理上状态就会好很多。(这种比赛基本都要切 T1)
其次难度不代表顺序,可能不同人擅长的题型不同,个人比较擅长数学,所以反而做出了最难的 T4,所以,顺序很重要,但不是那么重要,重要是因为它通常可以隐含着难度,但是考试时应该根据个人情况理性分析。
T4 大概用了一张纸,可以说 OI 的草稿纸用量毫不逊色于其他竞赛,而且不要吝啬自己的手,多推推可能就出来了。
出题解和小题分
T1 数据点锅了,实际得分 200pts。原因是快读 T 了,但是问老师之后说考场上可以放心写。
T2 比较诡,完全能听懂,但是思路是真的迷,以后要培养的就是这种能力,也要成为能想出奇异方法的谜语人。
T3 状压没活说。
T4 就不说了。