NOIP & CTT 游记

Day -2

今天来打 NOIP，目的是帮学弟学妹拉平均分，用来提高省队人数（？）。

进考场的时候被 LeavingZ 认出来了。

LeavingZ：你不要晚节不保了啊。

开考先通读题意，感觉 T1 是贪心题，T2 是数数题，T4 感觉像是一个一眼数据结构体（如果经过大量的数据结构练习，那么这道题应该不会很难）。

T1 想了一个做法，写出来，过了小样例，测大样例！大样例错了！

发现这个做法假了，果断删掉，换一个做法，写出来，过了小样例，测大样例！大样例又错了！！！

我破防了。果断弃掉 T1，去做 T2。感觉 T2 就用所有方案减掉不合法方案即可。测样例，过了！去做 T3。感觉 T3 题意梦回 NOI2023D1T3，结果读了一下之后发现还是有区别的。分析了一下，找到了一些性质，然后写了写，调了调，过了！

看 T4，经典的一些 lca 寄巧。然后转换一下就变成了三位数点问题，5\times 10^5，感觉 O(n\log^2n) 很能过啊！写写写，调调调，测测测。最大的样例只需要跑 1s，那岂不是随便过。

然后回来看 T1，终于知道怎么做了，而且感觉这次的做法很对。也是在 12:00 左右通过了。

欸，我是不是 AK 了！求求你，让我 AK 一次 NOIP 吧。/kel

官方数据：100+100+100+100=400。赢麻了。

Day -1

在教练的强烈推(yao)荐(qiu)下，做的晚上八点到早上六点的卧铺。虽然上次从背景回来教练也是安排做的这个点的卧铺，但是这一次感觉睡眠质量比上一次差，中途反反复复醒了三四次。

Day 0

也是到北京了，风是真的大，感觉比较冷。

我们到酒店的时候才 7 点多，而报道 9 点才开始，所以我们决定去吃早餐！最后找了一家饺子店，结果发现他们家早餐不卖饺子，所以点了一碗馄饨吃。

吃完之后又坐了一会儿，等到回去就已经 9 点了，然后就签到了。

拿了一个证书，一个名牌和一件衣服，感觉那件衣服刚拿出来的时候味道比较大，比较难过。

下午去报道，在清华的机房进行试机，经典的元旦激光炮。

花了一会儿切掉了三道题，然后睡了一觉。这可能是我唯一在 CTT 上 AK 并且睡觉的机会了。

试机结束后去开幕式，感觉 dzd 穿的这身衣服好帅！

吃饭居然实在负 2 楼，很牛；走楼梯到一楼，楼梯比较昏暗，不适合能看清楼梯，结果前面的人意思被位置物体挡住了去路，所有人被卡在了楼梯里面。

Day 1

寄了，只有大众分。

通读题面，感觉 T2 很可做，用喜欢的数据结构维护一下就可以了。花了 2h+ 才通过。感觉 T3 不是很可做，所以决定弃掉看 T1。

T1 貌似会一个 O(n^3m2^m) 的 DP，只能过 25 分。发现 m>\dfrac{n}{2} 不是很必要，所以可以优化到 O(n^3m2^{\frac{n}{2}})，结果怎么都过不了 n\le 30 的（明明我本地跑 1s 多，为什么 2s 的时限过不了？）（赛后听说本机效率是评测机的 4 倍，这下倒闭了啊）。

最后 25+100+0=125，我完蛋了。

下午被带着逛了一圈清华，然后听了讲题，感觉自己蠢爆了。

这下后两天一点压力都没有了，只需要好好享受了。

Day 2

登顶了？！感谢 le0n。

考试，先通读题面，感觉 T2 和 T3 看起来没有 T1 可做，所以决定先看 T1。

发现 Sub1 感觉随便选一个点都是对的，所以直接提交下发的 sample，成功获得 10 分！

然后通过分析发现度数最大的点到所有点的距离都 \le 2，答案一定 \le 2，所以决定直接尝试寻找度数最大的点。收到 Sub2 的启发，度数最大的点大概率没有入度，所以先随一个点 x，把所有点和 x 问一遍，然后删掉 x 指向的点。然后重复这个过程。

写了之后一交发现直接过了？考场上不知道为什么，所以就不管了。

T2 是神秘计数，所以看 T3。看了样例之后，感觉找到一条极长链，顺着扫一遍倒着扫一遍，dfs 被链儿子的顺序两个要 reverse 一下。感觉很对啊！结果发现对于链延申出去且深度 \ge 2 的叶子来说这个方法是不可行的。直接大胆猜测每一个都要单独加一个，直接大胆提交，欸，怎么过了？

这个时候只过了 2h，有三个小时时间大战 T2，那今天不是赢麻了？

然后缝缝补补写了三个不同的做法，拼了 48 分，感觉比较牛。

从篇幅看得出来今天很开心，希望明天不要翻车。 ## Day 3 在集训队选手内部登顶？再次感谢 le0n。 通读体面，感觉 T1 比较可做。先想到了一个 $O(n^3)$ 的 DP，写完发现假了，破防了，把代码全删了。然后想了想又想到了一个 $O(n^4)$ 的题，只能得 $40$ 分，难过了。 然后看了看 T2，发现 $n$ 很小，感觉是一个带状压的 DP，或者说记搜。想了想，感觉先枚举会被放入的积木集合 $S$，然后可以用记搜枚举放入第一个积木之后，其他的积木的分布，有一个 $O(3^{|S|})$ 的记搜，最终复杂度就是 $O(4^{|S|})$。写了写，交上去，感觉很对啊！ T3 是交互，经典的猜树类问题，感觉先随出来一个独立集，然后就可以整体二分问出和其他点之间的所有边。看起来询问次数是 $O(n\log n)$ 的。写出来，调一调，过了？ 剩下的时间用来大战 T1，感觉自己不太能会 $O(n^3)$ 的做法，所以决定大力卡常。最后可以是把 $n\le 500$ 卡过去了（值得注意的是，但凡开到 $n\le 600$ 我就过不了）。 最后 $85+100+100=285$，感觉比较牛。 ## Day 4 坐动车回去。