NOIP2024游记

8:00 到考点，在 rdfz。可恶，为什么不是 sdsz。

pdf 解压码还没发，先看看数据：

• assign 中间的数显然代表二元组个数，但剩下不知道了。
• edit 应该和二进制有关（？
• traverse 看不懂（
• query 显然是经典树问题。

先把板子敲好吧。

8:30 考试开始。

先开 T1。感觉很简单但又不是很简单？

考虑以下记连通块后贪心。手搓了一下，能过小样例。先写代码看看。

果然大样例挂了。看看是第几个样例挂了单独测一下：竟然对了？！

ooo 多测没清空。wssb

好了大样例过了果断交！现在是 9:06，开 T2。

T2 第一眼不就是有前后连续关联的为 v^2-v+1，其余为 v^2 吗？大样例不对？

o 原来在某些情况下只能填固定的数，这就减少了方案数量。

再仔细思考以下：2 ? 2（v=2） 的情况有 14 种，可行，有什么规律吗？

注意到第一个确定的数 x 如果限制是 (x,y) 则下一个只能填 y，否则什么都行。那么可以设两个确定的数 中间只有 n-1 个未确定的数的方案数为 f(n)，则

f(n)=vf(n-1)+v(v-1)v^{2n-2}=vf(n-1)+v^{2n}-v^{2n-1}

算一下：当 v=2 时：

• f(1)=3
• f(2)=14

于是代进去不对。哪出错了？别急，吃一个士力架，再看看。

如果 f(3)=60，则大样例对。那为什么 f(3)=36？奥我算错了，wssb*2。

那么 f 没问题，再推一下：

f(n)=v^{2n}-v^n+v^{n-1}

好了出了。现在大概是 10:00。开 T3。

T3 第一眼直接建立边构成的图，然后计算生成树的个数。有点复杂啊，能不能简化一下？

注意到这个图是由一堆完全图构成的节点构成的树。这就好办了。

办到一半发现不对！生成树必须满足 dfs 序，也就是每个完全图只有 n! 种生成树。这倒简化了做法。现在大致能得 \color{orange}24 分吧。

对于多个节点的情况，加一个容斥应该就行了（事后发现应该是错的），时间复杂度 O(n2^k)，应该能得 \color{yellow}48 分吧。

不着急开写，先看 T4：一眼 ST 表处理 lca，时间复杂度 O(q(r-l-k)\log n)=O(qn\log n)。应该能得 \color{orange} 32 分。

先写 T3。这玩意怎么这么难写！好不容易 \color{orange}24 分调出来了，一看已经 11:30 了，果断跑去写 T4。

没想到 T4 写得飞快，12:00 就写完了。顺便思考以下特殊性质 A。

算了想不出来去调 T3。然而到了 12:30 还没调出来。算了。开始写迷惑行为大赏的代码吧。

最终估分 \color{green}100\color{black}+\color{green}100\color{black}+\color{orange}24\color{black}+\color{orange}32\color{black}=\color{yellowgreen}256。

考场问其他人成绩，大体都在 200\sim 300（他们都比我强）。感觉还行。关键是现在已经 13:15 了！得赶紧去 13:30 的听口模拟！

最终听口模拟是 9(1.5+1.5+1.5+1.5+1.5+1.5)+11.5(1.9+1.8+2+2+1.9+1.9)+10+8.7=39.2。还行吧，总算上 39 了。

等着 CCF 出分。