[新的开始]NOI2023 退役记

· · 个人记录

结局。

2023.7.21

坐 10h 高铁到了成都，在高铁上附近找了家酒店住了下来。

看了一眼，酒店离成都七中挺近的。

2023.7.22

报道，到处乱晃。

以前签名是不喜欢把自己完整的网名写上去的，但是想到可能是最后一趟了，还是写了。

然后写了个 MatrixCascade。

领徽章，我会有心情换吗。

2023.7.23

开幕式还不错。

印象比较深的是街舞和川剧变脸，蛮酷炫。

还有个唱歌《我的未来不是梦》，以我现在的身份去听很有感觉。

下午试机，笔试 100 了，没出什么岔子。

感觉键盘太扁了，按不下去，很难受。

然后新增了个辅助功能，大概就是给你个评测软件但是只能测样例。大概是去年一堆 MLE 的原因吧。

晚上一直在想明天的事。我现在的水平，还是没法 Au 了吧，这一趟感觉大概率还是遗憾吧。真可惜。我会不会连 t1 都不会呢。

没时间去想，听天由命。

九点半就睡觉了。

2023.7.24

t1 只会 40pts。

t2 面对 n=1000,m=20 的数据范围我只会 O(n^m) 的指数级做法。

还没看 t3，我已经接近于崩溃。双手拍打着桌面。

。

下一秒，我坐在床上，四周一片漆黑。

传统艺能了吧，算是，每次赛前都要这样。

打开手机，4:14。

d1t1 只会 40pts 吗，呵。

水平烂，接受每种结局吧。

这回是真的进考场了。

t1 看上去很简单，应该把横竖搞完，最后枚举一下斜的就行了。

t2 看上去像神秘计数，相比之下 t3 好像更可做。

想了一下 t1 实现，一开始想大力扫描线线段树，发现扫描线需要离散化一下，那干脆两个坐标都离散化一下。发现同一类型的可能相交就会很麻烦。那就把相交的合并一下。每次竖的是个单点修改，横的就是减去个区间和。所以最后只剩下扫描线和 BIT。然后斜着的直接拿个 map 记一下交点。跑出来还不错。

怕样例恶心人，写了个 O(nmq) 的暴力拍了一下，直接挂在后台一直拍着得了。

先去看 t3。能作为 dfs 树其实就是没有横叉边。那就有了最低档的指数级做法。然后发现有 36 分 k 很小。那就对每条边处理出可行的根的集合，然后做状压 dp 即可。

然后发现性质 A 很优美，每条边的贡献都是两个区间，那么合并起来就是一个中间的区间，两个两边的区间，但是这样要记 4 个点？显然很劣。

又想了一会，不妨换个角度，把每条边当成个区间，从左往右，相当于插入区间，禁用区间的点。把区间排序一下从左往右扫着 dp 一下，然后拿个线段树优化一下。

现在就有 100+?+52 了，剩下两个半小时决定全去搞 t2。

最低档暴力，直接 prufer 枚举树也就 8^6，每次想着方便就直接 O(n^2) 判了，0.5s 有点阴间，不过先不管，后面再测。

对于 m\le 2，好像可以大力讨论一下。但是想了一下基本上是随便乱放都可以，稍微要判一下 m=2,k=0。推了一点式子。这时候就 35pts 了。

然后还有个 n=1,k=0 的部分分看上去很可做。其实就是在一个点下挂若干棵树，总共挂 m 个点。先算个 f_i 表示 i 个点拼出来的树的个数，然后维护个答案 g_i，但是这玩意只会 O(m^2\ln m)，不过和 T 是独立开来的，所以放外面预处理就好了。

然后就 50pts 了，此时只剩半个小时，回去测了一下最低档暴力的极限数据，发现要 0.59s，然后就改成了 O(n) 的 check，结果还写错了一点东西，删删改改只剩 15 分钟，分数定格了。

最后按照这玩意拓展一下 k=0 的做法，相当于每条边或者在某个点上挂一棵树？看上去很可做？可惜没时间了。不然有机会 70pts。

分数定格为 100+50+52=202，希望别挂分。

出来问了些人的分数，大部分在 200-240，那我应该是寄了。qiuly 比较会整，一开始我听说他 t2 35 我以为 t2 这么难吗，结果和我说 t3 100。人与人的信任。

听说队线 222，唉。听天由命。

查分，没挂。

2023.07.26

后面不写了，100+100+50+52+100+56+30=488。

队线好像是 509。

如果我 d1t2 猜到那 20pts 的找规律呢？

如果我 d2t2 的 bitset 想到了折半呢。

如果我的 d2t3 把可行的状态搜了出来呢。

哪有那么多如果。

这么突然，我的 oi 生涯在一夜之间就结束了。我也将奔赴文化课，奔赴高考。

前些阵子看到各种各样 9 级勾满是遗憾的人，一转眼变成了自己。

我一直坚信，我缺的只是时间和运气。虽然到最后，运气还是没能眷顾自己。

新的开始，感谢陪伴。

只是终究还是意难平。