NOIP2024 游记

· · 生活·游记

Day -？

模拟赛。

t1 用 1.5h，小数学思维题。

t2 打表一眼规律，然后显然优化。

t3 写了个四次方的区间 dp，比三次方的正解跑的快，题解见 this。

t4 赛时不会，怒拿 20pts；赛后发现其实不难，容斥 + 状压就可做了，题解见 this。

Day -？？

vp 了洛谷前些年的 CSP-S/NOIP 模拟赛，得出了一个结论：KDOI 好强%%%！

Day -5：

模拟赛，t1 是一个数学题，二分即可。

t2 是一个优化 dp，没注意到 (p_n, n] 也必须全部相同，直接爆 0。

t3 是一个找性质题，不会。

t4 是人类智慧，智慧贪心和线性规划。

100 + 0 + 0 + 0

Day -4：

t1 是一个性质题，随机随机选点找团即可。

t2 是智慧题，不会。

t3 是一个树上多重背包，使用了 12 个 bitset。

t4 是一个 ds，场上没时间了，只写了 80。

100 + 5 + 100 + 85

Day -3：

t1 是 MX 某场模拟赛原，简单分讨即可。

t2 就上 ddp，场上状态想少了。

t3 是一个 dp 优化，状态都没想到qwq。

t4 是一个分治题，场切了，感觉应该和 t2 换个位置。

100 + 50 + 15 + 100

Day -2：

t1 是一个构造题，ryxy 这样排列即可，将最后一列空着补最后还差的。

t2 是一个纳什均衡？实际上二分即可。

t3 神秘计数题，不会。

t4 貌似是更简单构造，先跑两遍能放 C/D 就放，然后染色即可。

100 + 100 + 30 + 100（哇塞，第一次 rk1）

Day -1：

早上爬山，下午玩音游。

Day 1：

吃了早饭后好想吐。。。

先打快读快输，然后写了下 tarjan；由于数论极少出现，猜想要考，于是打 exgcd，调半天没对，然后发题了。

扫了一眼，好像没有数学题，好耶。

看 t1，没看到相邻，浪费 2min；理清题意后容易想到按照 t_i = 0 进行分段，每个段内可以任意交换；然后按位贪心就做完了。

然后看 t2，看数据范围 10^9 感觉是线段树优化 dp，想 10min 后无果；然后发现直接算连续段，中间空的一段用总方案数减去不合法数即可。

前面两题用时 <= 1h，优势在我。

开 t3，生成树计数并？？？这真可做吗，思考 1h 后放弃。

t4 一看就很 lxl；容易发现 \ge k 是假的，等于 k 即可；然后还需要注意到区间 LCA 深度等价于区间相邻两个点 LCA 深度的最小值；然后直接扫描线，怒写 2h；敲出了一个 3log 的东西，最大的大样例要跑 5s+；但是随机数据只需要 1.6s愿 CCF 全放随机啊。

然后只剩 30min，回 t3；看了性质 A，直接全输出 1；然后开始敲暴力，结束了也没敲出来/ll。

估分是：100 + 100 + 4 + [80, 100] = [284, 304]。

回家路上收到喜报，可以去冬令营。