Day -20（2021 / 10 / 31，周天）

2021 福建省 NOIP 编程水平测试。由于是 NOIP2021 选拔赛，听说不爆零就可以过，所以就没有做太多准备。

一共 3 小时，从 9 : 00 考到 12 : 00。

打开 problem.pdf 一看，好家伙，标题是「福建省 NOI2011 省队选拔赛（第一天）」。
FJOI 先生，世间所有的相遇都是久别重逢。

先开了 A 题，很快就有了一个 \(\mathcal{O}(n^3k + n^3m)\) 的做法。
摁了一下计算器，发现 \(3000 \times 80^3 = 1.536 \times 10^9\)，都 15 亿了肯定过不了。

很快就观察到，因为求的是最短路，经过的点的个数不会超过 \(n\) 个，故切换赛车的次数也不会超过 \(n\) 次。
于是就可以优化到 \(\mathcal{O}(n^4 + n^3m)\)。

接下来开了 B 题，第一眼的想法是：我超！是 Pólya 定理吗？我不会啊怎么办。
过了好一会才看到 " 计算对于有相同宝石排列的项圈 " 这句话，果然是 FJOI。

然后就写了一个复杂度为 \(\mathcal{O}(T \cdot n)\) 的线性递推。辣鸡 FJOI，连测试数据组数都不给。

我：您好。我想问一下这场比赛的第二题，它所说的 " 有多组测试数据项 "，具体有多少组呢？

负责人：在正常范围内。

我：我知道在正常范围内，具体是在什么范围内呢。

负责人：我们也不知道具体是在什么范围内，但是是在正常范围内，就是你们平常做题时的正常范围。

我：好吧，谢谢您。
内心独白：这也不给、那也不给，你怎么不去 * 呢？

负责人：不客气。

算了，应该可以过吧。

接下来开了 C 题。我真是太逆天了，看错了两个题面的意思：

• 我以为每个被占领的节点可以向周围的任意多个节点扩展，但实际上只能向周围的至多一个节点扩展。
• 我以为子任务 1 的起点必须为 \(a\) 点，但实际上可以为 \(1\) 到 \(n\) 中的任何点。

考场上的我天真地认为，既然 A, B 都这么送分了，C 肯定也在送分。于是就打了一个求最长链的模板。

我超，这就 AK 了？这是不是人均 AK 啊？于是开开心心扫雷去了，这一扫就是两个小时，扫到 12 : 00 出考场。

出考场一问，才发现 C 题爆零，我真逆天。
后面仔细想了想，发现 C 题也不难，子任务 1 就是一个简单的换根 dp；子任务 2 就是一个简单的倍增。