NOI2023 游记

swiftc · 2023-07-31 23:10:42 · 生活·游记

比赛之外的事情不太想写，大概写一下赛时的心路历程。

因为最近在旅游，写的有点晚，有些细节可能不准确。

Day 1

看到三道题的题意后就直接开始写 T1 了，当时还疑惑 NOI 为什么会有不考察任何东西的题（或者说过于平凡的套路？）。

发现 T1 除了题面没有较小样例，如果一遍没过的活可能很麻烦。

大概写了 4k，中间调主要是调了一个用离散化前的值的错误。

在 1h 左右过了样例。

T2 看起来很难，首先发现了要求是只能在原树上插节点，之后从 n=1 开始想，发现限制在于一个节点子树内编号比这个节点小 k 的节点必须在同一个子树内。

于是可以 dp 每次决策最小的子树填哪些点，是 m^3，但看起来容易优化到 m^2。

想了一下发现 k \neq 0 类似 dp 是假的。

于是先去看 T3，想了一会发现 A 性质是区间覆盖，但没想到怎么低于 n^3 dp，之后发现了原问题要求是没有横叉边，于是有一个 44 分的容斥。

这时候大概还剩 2 小时，写了 T2 的 dp 并换了一下枚举顺序优化到 m^2。

然后写了 T3 的容斥。

推了一下 T2 m=0,1,2 的情况或者可以说就是随便想一下然后看样例过没过。

从 m=2 发现 T2 n \neq 1 就是往树上每一条边和每一个点插入若干节点集合，这些好像跟原树没关系。

于是是个背包？但这时去写了 T3 的 10 分暴力^{[1]}，在最后一分钟调出了 T2 n \neq 1,k=0,m\le100 的部分分。

Day 2

看到 T1 感觉是道需要过的题，所有边从根出发是容易的但没什么启发性，之后想到了两个子树合并，发现需要每个点到子树内所有点的最短路，好像是容易递推 + dij 的？那好像就没什么问题了。

T2 被字符串震惊了一下，一开始在思考直接后缀排序的问题在哪，发现是两个串前面完全相同，这样就是回文串。

于是可以直接后缀排序然后枚举所有回文前缀单独判？

NOI 没有 subtask 感觉能很多分^{[2]}。

如果想让期望得分比较高好像要 PAM，但我好长时间没写过了。

一开始认为无论如何询问都要后缀数组上二分于是先写了个二分哈希后缀排序，但跑了 5s，之后注意到可以把前缀后缀一起排序，这样样例就 400 ms 了。

这时候大概剩 2 个小时。

感觉不用 PAM 会超级麻烦于是想了一遍 PAM 是什么，这道题只需要找到所有偶回文串所以会容易一点还想了一段时间为什么 PAM 每次插入只会多一条转移边。

中间断断续续想了一会 T3 但没有进展，但因为是 NOI D2T3 问题应该也不大，发现 w_i=1 直接贪都不对。

最后 30 分钟写了 T3 的 w_i=1 的 dp 和纯暴力^{[3]}，写到了最后 5 分钟左右。

总分 (100)+(5)+100+50+44+100+92+10=501，rk 65。