2024-11-22

似乎成功了。整个机房都去了。

2024-11-??

发现 NOI 官网写的要自选操作系统，但报名的时候没选。问了一圈只有 ZHY 妈妈给他选了 Linux，其他全是未知。

以前考试复习 Linux 怎么用，现在要复习 Win 怎么用了。

2024-11-28 (DAY -2)

NOIP 前最后一次模拟赛。

T3 MLE，T2 写太久导致 T4 没时间写暴力。

当做给 NOIP 涨 rp 的。

2024-11-29 (DAY -1)

明天考试，早上到机房按惯例开打板子赛。

ZHY 说赛前打得板子赛时大概率用不到，于是得出结论：赛前要多打板子，这样赛时就不会考这些了（大雾

开了一个数据结构题，一起想了一会儿，想了个大概的思路。希望明天不要大数据结构。

下午坐大巴去，上车不久就开块了。发现了 ZEN 的垃圾行模式，可以将自己打的伤害给自己，非常好玩。ifffer 荣批，不会玩。

住上次省选的酒店，和 XiaY 住一个房间。吃饭前复习了 Win 的拍子怎么写。

晚上 8:30 被 FSB 叫去开例会，开不开一样，罚站 $1$ h。

回去打了一下块，后来懒得动了，用电视放熊出没和喜羊羊，10:15 睡觉，设了第二天 6:30 的大香蕉闹钟。

2024-11-30 (DAY 0)

被大香蕉闹钟弄醒了。床上颓了 $10$ min，吃完饭大巴去杭师大。

又走了一遍不知道已经走了几遍的去考场的路，也不知道以后还可以走几遍。

到得很早，别的学校大多都还没来。WLZX 来的时候面了 XHGua,CZY 一些老乡。

在考场门口站了一会，ZHY 提议说先一个人进去看，是 Linux 就咳嗽一下，是 Win 就擤一下鼻涕。但没人想先进去。

后来还是一起进去了，发现是 Linux，非常高兴。周围看了一圈，能看到好多认识的。

位置靠墙，好评，直接在赛前配好了 sublime 且没被发现。

8:23 发样例，看到了一只 $12$ 个大样例的题。没发现大模拟。对题意没有头猪。

8:28 发题面，开 T1 看着像贪或 dp。

8:30，NOIP，启动！（监考都没报考试开始，边上的人都开始敲代码才发现的

不是为啥啊，我细节都还没想好你们咋全都开始敲了啊？觉得可能在敲头，就没管，继续想。

不是为啥啊， $1$ min 都过去了头应该敲完了啊，咋键盘声音还是这么响？？？难道 T1 这么唐直接贪心就行啦？

细节也不想了，直接开写，写了几段有复制粘贴了几段就没了。测样例，小样例没过。

心慌，觉得贪心假掉了。直接手模样例，但是发现非常正确。debug， $1$ min 后发现一只 bug，改掉过了小样例，大样例一遍过。

觉得 T1 贪很可能假，打算后面有时间回来写拍。

$15$ min 开 T2，神秘计数，手模一下发现确定的单点划分出来的东西互不影响，直接化简到确定头尾的区间问题。

计数直接一手真难则反。诶不是，直接做完了？敲代码，一遍过小样例，第二个大样例寄了。好在挂的是小点，发现竟然有相同的对子！去重之后直接过，此时 $30$ min。

按 CSP 传统走着去了厕所，顺便平复下心情。毕竟提前开香槟容易击飞。

开 T3，依然困难计数题。看完题面感觉不可做。一看特殊性质，前面的三挡 $k\le 1,k\le 2,k\le 8$ ，鉴定为容斥。

但我咋不会做 $k=1$ 啊？？？觉得很难想，直接开 T4，LXL 风格的数据结构。

一眼暴力部分分给到了 $32$ ，相比平时模拟赛 $10$ 分暴力还是非常良心的。

没犹豫直接打暴力， $20$ min 肝完一遍过样例。

继续特殊性质链，转为序列上问题。开始考虑二分答案，正确性显然，时间过不去。换成整体二分，时间变成 $\log^2$ ，能过 $10^5$ 但过不了 $5\times 10^5$ 。

不知道整体二分在不在 NOIP 考纲内，但感觉有更精细的做法。于是没打整体二分开始想单 $\log$ 。没想出来做法，又去上厕所，觉得还是先想 T3 为妙。

发现决策是正确的。T3 想到对每个节点的儿子进行某种顺序连边，其中只有起点固定为离靠近关键边的那条边，于是 $k=1$ 的答案就是 $\prod (du_u-1)!$ ！很漂亮啊，跟关键边是那条都无关，推式子的压力小了好多。

花 $3$ min 写完，感谢出题人给 $12$ 组大样例，测了一发，过了 $k=1$ 的点，皆大喜欢。

既然要容斥那 $k=2$ 的点显然不能逾越。开始想同时满足两个关键边作为根的计数。先推完了一条边能为根的充要条件，然后构造同时满足两条边的。

中间构造假了一次，导致差点以为没有同时满足两个关键边的树，浪费了 $20$ min。突然发现小样例二样例解释里就有这种情况，直接画样例并猜测样例的情况就是充要。发现显然是正确的。

稍微算了下方案数，又是好看的一个式子 $\prod (du_u-1-[\text{u is between two critical edges}])! = \prod (du_u-1)! \times \prod (du_u-1)^{-1}\cdot[\text{u is between two critical edges}]$ ！判断在两关键边之间用了 LCA，运气巨好直接从 T4 的暴力搬过来用。快速打完，过了 $k=2$ 的大样例。