NOIP2024模拟赛#2 总结

NOIP2024模拟赛#2 总结

老师：比昨天简单不少。
得分：\(30+100+20+10=160\)，rk 5。

赛时

正序开题，A 题很好懂，但是一看数据范围立马寄掉，发现自己只会 \(T\le 10,r-l+1\le 10^5\) 这一档暴力，飞快地写了 \(30\text {pts}\) 跑路。此时大概是 8：30。

B 题题面很长，但是不影响阅读，题面通俗易懂。感觉这个什么 SB 树类似于 cantor 表，都能表示出所有有理数。发现 B 题有两个子问题，且是互逆的。题面读着读着发现有个【提示】，发现出题人过于良心，直接把第一问的解法告诉你了，白送 \(50\text {pts}\)。稍加思考后发现 SB 树是单增的，于是第二问仿照第一问一个一个往下走就能做掉。9：00 左右写完了 B 题，随手造了几组数据发现没问题就扔那了。

心想 A 题只拿 \(30 \text{pts}\) 不太行啊，于是再想了想 A，发现会了一个 \(O(T\log ^2V)\) 的做法，复杂度是正确的，但是细节很多，决定先看 C 和 D。

C 题看上去像一个区间 DP，但是不太会处理，写了个 BFS 暴搜拿了 \(20\text {pts}\)。

D 题大组合计数，感觉正解是 \(O(nm)\) 的 DP，但是心中挂念着 T1，预处理了逆元，写了个 \(20\text{pts}\) 的第一档分。

再次回到 A 题，此时已经是 10：30 了，还有 1.5h。

二分答案很快写好了，但是发现 check 很难处理，没写多少就卡到了一个地方，但是过三四分钟后思路就通了，这样写写想想有五六次，因为我的做法细节实在是太多了。

缝缝补补 A 题在 11：40 时过掉了小样例，但是第一个大样例直接 T 飞，发现是二分边界问题，改过后过了第一个大样例，但是第二个大样例感觉也是进入死循环了，但此时没时间了，将前面写的 \(30\) 分暴力加到代码上就交了。

预估：\(100+100+20+20=240\)。

实际：\(30+100+20+10=160\)，寄完了。

赛后

A 题果然有难度，最高分只有 \(50\)，哎，要是 A 题过了就 rk 1 了。

赛后发现 A 题执行暴力代码的边界写成了 \(T\le 10\)，但其实第二档分也是 \(T\le 10\)，把执行暴力的代码删掉后有了 \(50\) 分。

拿着 A 题代码再次执行第二个大样例，发现不是陷入死循环了，而是足足跑了 \(10\text s\)，我去怎么常数这么大被卡常了。

吃完饭回来对着 A 题卡常了一中午，define int long long 真是害人，最后大样例跑到了 \(2.1\text s\)，但是时限只有 \(1.5\text s\)，还是只有 \(50\) 分，卡不动了。

直接让邱老师把时限改到 \(4\text s\)，总算是跑过去了，最慢的点跑了 \(1900 \text {ms}\)。

下发 std 后惊讶于标程的实现，速度是我的四倍多，逆天了。

讲题时因为目前只有我过掉了 A 题，所以大家让我讲，但当时刚睡醒，思路很不清晰，加上语言组织能力不强，讲的很烂，抱歉各位，有机会写个题解（但我是鸽子。

题解

咕了。