氮氧碘磷 2024 游记

ATZdhjeb · 2024-12-01 22:12:11 · 生活·游记

吸取 CSP 游记的教训，尽量少使用暴戾语言。

省流：\log^2，整体二分，线段树，10^5，7s，输光光。

DAY -1

NOIP 前最后一场模拟赛，题面写得幽默搞笑，4 个题， 3 个两位数数据范围，2 个构造，1 个浮点误差，下发了 0 个 SPJ。

只写了 T1，然后挂了，喜提 0+0+0+0=0。

然后看题解，发现 T4 是史无前例的生物题，你只需要把题面中提到的莫名其妙的限制想象成配血实验，点和点的颜色想象成人的血型，结合一些生物学常识，然后就可以自然地想到 2-SAT 建模了！

实在是跨学科融合之典范，为出题人点赞！

Day 0

上午试图写群星链接，然后写一半就摆掉了。

下午在和 @tybbs 研究语言学。

晚上回家写了点简单数据结构。

Day 1

早起坐车去高新校区，喜提全机房第一个到校门口。

然后在校门口紧急背了点《天岁天岁》歌词，准备考场上写。

进校的时候照例喊了句即将获得全机房唯一二等奖。

进考场，发现键盘和平常用的是一样的，且可以提前打缺省源。遂打完了缺省源并在四道题的源文件后面写了点歌词。

看大样例，query 形如一个树或者图上的 DS 题，traverse 有一车样例，这俩应该是 T3/T4；edit 是个简单的 0/1 串题，应该是签；assign 看上去稍显神秘。

又是提前了 O(1) 分钟发密码，但是听说本机的时间其实是不准的，所以可能没有提前发？不太懂。

果然我猜的题序差不多是对的。光速会了 T1 的一个贪心，写出来发现过不了小样例。哦哦，原来是要反悔，加上。然后还是过不了小样例。哦哦，原来分讨少了。哎不是，这咋要分讨这么多？不管了，写写写，写了差不多半个小时才过大样例。

选择相信样例强度，直接扔了去开 T2。哎不是这咋是计数？不过好在是简单计数，虽然期间编了很多神秘的东西，还想了好久容斥，但是最后还是发现只需要把每一段乘起来就可以了，差不多开考 1h 的时候过了大样例，然后开 T3。

还是计数？？？

喜欢出计数？？？

扔之，开 T4，但是完全没有看出一点性质啊！只会暴力，还是决定回去看 T3。

然后先从 T3 的特殊性质想起，发现菊花变换一下是一张完全图，所求即是完全图上的 DFS 生成树，这是个阶乘的形式。再考察一般的树，发现直接把各种阶乘拼起来就是对的了。这样我就会了 AB 性质和 k=1？

感觉很有前途，考虑 k\neq 1 其实就是把重复的树给容斥掉。最开始觉得 O(nk) 是容易的，但是编了半天小样例都过不了！然后又试图想 O(nk^2)，做到了差不多 11:30，依然没有写出任何有哪怕一丁点正确性的东西！于是直接慌完了，果断跑路去开 T4。

先把 T4 的暴力写了，然后发现链的部分可以容易地做到 \log^2，但是需要整体二分，而我恰好没有写过任何一次整体二分！

但是链的 32 分拼不上我就输完了！于是直接搓了一个感觉上很对的东西出来，然后测大样例

—— 7s。

不是哥们？

assert 了一下分治深度，发现很对啊，调了好久发现瓶颈在用线段树求 RMQ，但是由于我这个时候脑子处于原神启动的状态，完全没想到自己其实是会一种好写的近似 O(n)-O(1) RMQ 的，直接换了个 ST 表上去。但是由于在整体二分下线段树其实远远跑不满，所以 ST 反而跑得更慢，直接达到了 12s。

这个时候想起自己会 O(n)-O(1) RMQ 了，但是没有用了，只有大约 10min 就要结束了。

于是交了线段树的版本。

最后大概是 100 + 100 + 40 + 32 = 272。输。

死因大概是做后面两题的时候大脑高度不清醒。包括但不限于：

• T3 没写 O(n2^k)。

• T4 忘记自己会 O(n)-O(1) RMQ。

• T4 没有意识到相邻点求 LCA 就可以把一般情况转化为链。

出场问了一下别人的分数，好像只有 @NATO 稍微正常点，有 304。然后 @tybbs 写了 T3 的指数级容斥，喜提 290+。然后剩下的人都跟我差不太多？

鉴定为全机房都输完了。

就这样吧，中午跟同学聚了一下餐，然后就回家摆去了。