NOIP2024游记

· · 生活·游记

day-1

打板子。

说了一些很唐的发电,试图通过今天多唐来避免明天犯唐。

最后打了AC自动机的板子,肯定不会考,但是有个好寓意。

晚上补番,爽!

胆大党更了两集一口气看完爽。

之后去看《笨女孩》,好唐好唐,好看好看。

睡的疑似有点晚。

正式

做梦来着,梦见NOIP一题不会。

醒来之后发现还没考,太棒了,还有机会。

去考场,听歌,一直保持在精神恍惚状态。

不记得怎么进考场得了。

解压包密码输错了两遍,01写反了。

看大样例,猜了题目顺序。

T1->T1 T4->T2 T2->T3 T3->T4

先看了一遍四个题。

A 好像直接贪心就行,但是不是很会写。

B 好抽象,不会。

C 好抽象,不会。

D 我去这不板子,我是不是读错题了。

写A,写了一半删了,感觉细节多还杂,认为自已没考虑清楚。

去写D,发现果然读错题了,k 在每次询问中是不一样的。

写 A,还是想不清楚,拼命喝咖啡。

过了40多分钟,受不了了,就开写。

写完调了一下直接过样例了,交了。

开始思考 B,看数据范围,盲猜是某种矩阵快速幂优化DP。

DP 推半天没推出来,怀疑自己想错了,想了想其他做法。

想容斥,发现每段之间是独立的,我去这不傻题,写写写,直接过了所有大样例。

用时大概十分钟,感觉严格简单于A。

写完去上厕所,回来之后把 D 的暴力写了,想搞特殊性质A,但是C还一分没有,于是去看C。

C 感觉非常抽象,决定先想办法转化一下题意。

发现一个点的答案只和度数有关,有点不敢相信,但是先写了。

感觉肯定是假的,但是决定写完再看看哪假,反正很好写。

写完过了样例一,样例二过不去,发现会算重。

思考了若干避免算重的方式,但都是错的。

思考思考,发现可以尝试转化。 每个合法方案唯一对应出一条链接两个叶子的路径,可以尝试对路径计数,然后乘上某个权值。 很有前途啊!! 于是先写了 $O(n^2)$,反正还剩两个多小时,不慌。 写完发现样例都过了,爽,说明转化是对的。 于是想怎么优化,很经典的优化:考虑在两个叶子 $lca$ 处合并答案。 但是细节很多,没着急开始写,想了挺久。 后来开始写,写完一直调调调,过了小样例后测大样例,发现没清空,清空完直接过了。 剩40分钟,不敢写D了,开始对拍。 拍出错了,发现需要特判 $n=2$。 写完貌似没什么问题了。 最后一分钟发现D 数组开小了,直接在网站上改的,希望不要出锅。 估分:100+100+100+32 出考场后发现Segtree会 D 不会 C,评价为没放防 AK 题。 下午继续看《笨女孩》好唐好好笑。 可惜太短了,一下午都没过完就完结了。 于是去补上辈子没看完的少女终末旅行。 爽了。