NOIP2025

• $\text{8:12}$：进入了考场，发现半个机房的人我都认识？
• $\text{8:25}$：开始测试机器。
• $\text{8:30}$：开考，但是我还沉浸在打代码框架里。
• $\text{8:32}$：终于意识到开考了，开始解压文件夹，建子目录。
• $\text{8:48}$：读完了所有题目，感觉 T1 像简单贪心，T2 像 DP + 组合计数，T3 像 bitset，T4 像神秘数据结构。
  自以为可以秒掉 T1，然而……
• $\text{8:53}$：发现 T1 能够买大于等于 $2$ 颗的 $i$ 只有一个 $i=i_0$ 满足 $x_i+y_i$ 最小。因此其他 $i\neq i_0$ 的所有糖果至多买一个 $x_i$。因此贪心买完 $x_{i_0}+y_{i_0}$，剩下的从小到大买 $x_i$ 即可。
• $\text{9:08}$：贪心假了，死活调不出来，开始打 T2 暴力。
• $\text{9:23}$：发现 T2 题意理解错了，重写暴力……
• $\text{9:42}$：写出了 T2 暴力。过程中调了半天的 01 背包。？
• $\text{10:06}$：过掉了 T1 所有大样例。发现可能会存在 $x_i+x_j<x_{i_0}+y_{i_0}$，这种情况答案不变，可以省钱。
  不妨令 $x_1<x_2<\cdots<x_n$。
  因此类似于一种可反悔贪心：
  • 若 $m\geq x_i$，就购进 $x_i$，令 $m\leftarrow m-x_i$，同时记录答案。
  • 否则若 $x_i+x_{i+1}<x_{i_0}+y_{i_0}$，令 $m\leftarrow m+x_{i_0}+y_{i_0}-x_i-x_{i+1}$。
• 之后开始打 T3 暴力。
  看到 $\operatorname{mex}$ 给我激动坏了，因为在 Day -1 才复习了 bitset 维护 $\operatorname{mex}$。
  但是其实是一坨。因为我只知道 $a_x\in[0,\textit{size}_x+1]$，只会写 $\mathcal O\left(n^n\right)$ 的。bitset 和直接开桶统计差别不大。都只能过 $n\leq7$。
• 开始打 T4 暴力。先写了一个 $\mathcal O\left(qn^3\right)$。
  想到 ST 表直接求区间最值，因此可以 $\mathcal O\left(qn^2\right)$。
  对于 $\text B$ 性质，其实可以直接跑过去。因为复杂度可以做到 $\mathcal O(qnR)$。
  T4 最终期望得分 $30\sim35\text{pts}$。如果 CCF 神机再世，也许能让我跑过第 $4$ 个点；本机 $\text{3.9s}$。
• 之后想了好久，不知道如何写 T3 特殊性质。
  最终期望得分 $\text{8pts}$。
• 最后一直在写 T2。
  注意到测试点 $16$ 满足 $m=2n-1$，特判一下 $w_1=w_2=\cdots=w_n=2$ 这种情况是否合法即可。其余情况都可以全买完，都是合法的。最终答案即 $2^n-[\text{$w_1=w_2=\cdots=w_n=2$ 不合法}]$。
  但是没有大样例，不知道假了没有。
  注意到测试点 $17$ 满足 $m=2n-2$，说明答案为：
  $$2^n-[\text{$w_1=w_2=\cdots=w_n=2$ 不合法}]-\sum_{i=1}^n[\text{只有 $w_i=1$ 不合法}]$$