HNCPC2024 游记

_LiWenX_

2024-12-16 17:43:55

Life & Travel

队伍:长沙一中二队,本来应该是叫 LiuFaFaOnO 的,队友分别是:我,tx,还有蛋哥。

省流:打得唐完了,最后总共⑨题。

首先 tx 看到了 E 题,他说是 ez 题就赶紧写了,拿到了首杀。然后看 C 题也过了不少,发现是高精板子,tx 直接开写,结果高精写挂 WA 了???原来 a_i

然后我看了一下感觉 H 很水,写了一个什么单串AC自动机和一个 dp,8min 就写完 A 了。 蛋哥说他估计会 J,但是先上了个厕所。tx 发现 K 很水,是个最短路板子,写完拿了首 A。蛋哥回来之后又马上过了 J。同时我发现 D 可以直接莫反,然后找了一下其他题。 蛋哥过了 J 之后,我和 tx 一起推 D 式子,推完发现还挺简单的,就赶紧写,写完 TLE 了,然后我帮忙卡常,把 vector 换成数组就过了。 此时过去了 1.5h,我们已经 7 题了,看榜发现目前 rk1,优势在我。 然后恶心的部分来了,蛋哥说他得到了一个 A 题的结论:必然存在一种最优方案,使得存在两个点使得与旋转后的 x 轴垂直,我们都感觉很对,然后思考了一下,为了防止掉精度,使用复数乘法来保证运算都是整数。 tx 开始写这个做法,我去思考 F 和 B 题,蛋哥思考 G 题。 tx 写完,发现 WA 了,然后我们三个人一起调试,虚空调试很久,结果什么问题都没有发现,加上这个题不好写暴力,根本对拍不了。 蛋哥还是选择冲刺 G 题,他说他有想法,问我用线性基还是高斯消元做比较好,和他讨论了一下感觉线性基比较无脑但是步数可能会爆,所以最后他选择用高斯消元。 然后我和 tx 一直被 A 个题硬控了一个多小时,依然什么都没调处来,于是我们选择了放弃,转去看 B 题,思考了一下,发现答案大致形如 $\sum\limits_{u\in S}deg_u+1-2\times 连通块数量$ ,使用点减边容斥拆开后,感觉式子还比较能做,大致形如 $\sum\limits_{u\in S} val_u$ ,我试图扫描线维护颜色权值,突然想起学长之前告诉我的树上颜色段均摊的 trick,瞬间恍然大悟,发现直接树剖珂朵莉树,动态维护颜色权值扫描线就做完了,赶紧告诉 tx,tx 也觉得没问题,我们就开写。 写到一半,蛋哥突然说会 G 了,很快就写了出来,此时我们分屏继续调试 A 题。 我突然有个很大胆的想法,我们做法枚举两个点得到向量 $(x,y)$ 然后求法向量旋转,虽然这样看不出问题,但是我直觉感觉这样分类少了,所以我直接把 $(x,y),(x,-y),(-x,y),(-x,-y),(y,x),(y,-x),(-y,x),(-y,-x)$ 八个向量全部扔进去跑旋转,抱着试一试的心态交了一发,过了,我们三个看到 AC 直接笑了出来,还把后面监考看乐了。 也就是在 3h20min 的时候我们来到了 9 题。 然后 tx 继续 B 题,发现 B 题少了很多情况和细节,他就继续调。 我和蛋哥思考 F,设了一个 $f_{i,j,0/1,0/1}$ 表示以 $i$ 为根的子树,有 $j$ 个割点,是否与叶子节点同色,是否向上延伸合并,发现 $5000×5000×4$ 的状态就直接 MLE 了,遂放弃,不知道该怎么做。 然后继续看 tx 调,一直到结束都没有调出来。 出来,发现 rk3,我们学校一队没打好,所以我们成学校第一的队了(然后我们学校四队也比三队高)。 听 using 讲了 F 的做法,发现大概就是这种状态硬做,转移大力分讨即可,空间的话,直接 dsu on tree 优化即可,没有想到这个 dsu。 然后看了一下 B 的题解,它的式子比我想到的更好维护,但是大致思路框架都是一样的树上颜色段均摊加扫描线。 所以感觉⑨题还是有点遗憾的,三个人的配合很好,但是没有把水平全部打出来,希望我们队能在 THUPC 得到更好的表现吧。