NOI2021 同步赛迫真游记（附带部分题解）

· · 个人记录

Day1：

开题发懵。上来拍脸一个数据结构啥意思啊？？？

把每个题题意读了一下，然后开始发呆。想了会儿 T1 感觉是 LCT，但是完全不会啊（而且 LCT 也不知道多久没写过了。

因为台风放假，所以 12 点就去吃饭了，吃完回来开始 T2T3T1 的顺序打暴力。途中根本没想过正解。

之前看 T2 有点感觉，又是逆序对又是奇偶答案之差，n 是 100 的数据范围，每一层答案还是独立的，就直接糊了一个行列式上去，调了半天把性质 A 做了。

然后平平无奇地把 T1T3 暴力敲完，结果 T1 暴力都差点没调出来。T3 暴力还写挂了，树的 k=0 分也挂了。

预计得分：50+75+36=161

自测得分：50+75+16=141

晚上仔细想了一下发现三个题都不难。只是我太菜了而已。

Day2：

先把三题题面看了一下，暂时没什么思路，准备先打暴力。发现自己码力堪忧，花了两个半小时才把 T1T2 暴力打好。

然后去想 T1，这个 k<=15 给的很奇怪，发现 256=16*16，也就是把它分成 16 段，然后就可以暴力枚举相同的那段匹配了。由于初始的串是随机的，所以复杂度直接除一个 2^{16}。然后自己巨大多常数，卡了接近半个小时也没进 2s。

最后还剩半个小时，去把 T3 暴力写了，结果题目看错，暴力都写挂（还好 n=1 的读题分过了。

预计得分：[80,100]+35+12=[127,147]

自测得分：[80,100]+35+8=[123,143]

T1 得看 CCF 机子速度如何了。后来发现可以直接用数组存，比用 vector 快不少。

自测总得分：[264,284]。看上去还是能苟上 Ag 的，然而 D1T1 赛时没过实在是太逊了。

2021-8-9-upd：过了 inf 天，官网终于出分了。。果不其然 D2T1 被卡了 20 分，最后是 264。

题解：

D1T1

D1T2

D1T3

D2T1

D2T2