NOIP 2023

SegTree · 2023-11-17 19:48:37 · 个人记录

11.17

打板。

11.18

初步看题。T1 看上去是高妙的串串题，T2 看上去也不会，但是爆搜、TFU、U+ 好像会，T3 发现自己可能会 \mathcal{O}(nm)，T4 好像会 n\le 10^3 和特殊性质 B。如果这样是 70+60+35+44=209。

顺序开题。发现 A 直接一个字典树就做完了。写完小样例过了大样例没过，assert 发现有一个串长度不等于 m，剩下的串调试发现是空的。觉得自己数组开小了，调调调不过。9:30 发现直接复制大样例会不全，然后直接把大样例过掉了。

B 看上去比较可做，决定把 C 和 D 的暴力先打完。

开了 C，发现可以 nm 随便搞一搞，有手就行，直接 dp_{i,j} 表示序列 a 对应到第 i 个序列 b 对应到第 j 个就行，可以 35。

开了 D，只会 \mathcal{O}(nk) 的 dp，就写了。大样例没过，发现滚动数组忘记清空了调了很久，因此把暴力打完已经 11：45。

回去看 B 发现好做，简直有手就行，直接搞出来每个的值或者能否用别的变量表达出来，然后直接染色就行。大样例 3 寄了，发现赋值操作覆盖上一次操作的情况没判，调完就过了。

看 D 想了想优化，不是很会，只剩下二十多分钟，没啥思路，检查一下会不会挂分。

发现 A 的 Trie 空间会寄，100\to 90。

估分 90+100+35+44=269。

出场发现人均切 A，但我写了 Trie，-10。

B 好像也人均切了。CD 不知道。

远低于大众分。

UPD：没挂。

怎么有【】签到题上来明知空间开不下冲 90 写字典树呢。