P9034 「KDOI-04」Again Counting Set
第三条限制非常强，如果 \(\min \neq 0\)，那么其它所有数都必须为 \(1\)，也就是集合中的数全是 \(1\)，这样，\(\min+\max+\operatorname{mex}=2\)，因此集合大小必须为 \(2\)。
否则，\(\min=0\)，那么在第四个限制的式子中 \(\min\) 不贡献。考虑 \(\max\) 和集合中的 \(\max\) 会消掉一个，但是 \(\max\) 可能有多个，不好考虑，因此可以钦定 \(\operatorname{mex}<\max\) 和 \(\operatorname{mex}>\max\) 算，先看小于的，\(\operatorname{mex}=i\) 说明 \(0 \sim i-1\) 都出现过，和至少为 \(\frac{i(i-1)}{2}\)，因此 \(\frac{i(i-1)}{2} \le i\)，解得 \(i \le 3\)，那么就只需要分类讨论即可，必须有一个大于 \(i\) 的 \(\max\)，其他的就应该是 \(0\)。大于的也类似，\(\operatorname{mex}=i\) 可以直接推出 \(\max=i-1\)，那么也是分讨一下即可。
P9992 [Ynoi Easy Round 2024] TEST_130
对于一个合法的点 \(x\)，她的贡献大致是 \(dep_w+d-dep_x+1\)，这个可以扫描线轻松求出。
写一下，有 \(dfn\) 限制，\(dep\) 限制，按照 \(dfn\) 扫描线方便，那么 \(dep\) 就是前缀限制，因为子树内不会有 \(dep\) 小于根的点，用 BIT。
有的时候会有问题，对于子树内最大深度 \(< dep_w+d\) 的会多算，会多算 \(dep_w+d-Mxdep_x\)，然后如果 \(Mxdep_x<dep_w+d\) 那自然 \(dep_x \le dep_w+d\)，所以继续扫描线即可。卡常/tuu
[ABC244F] Shortest Good Path
考虑走一条边只会改变终点节点的奇偶性，设 \(f_{S,j}\) 表示当前状态为 \(S\)，走的终点是 \(j\) 的最短路，转移是枚举 \(j\) 的临边 \(y\)，走到 \(f_{S \oplus 2^y,y}\)。转移可能是有环的，这是边权为 \(1\) 的最短路，使用 bfs 即可。
[ABC244G] Construct Good Path
考虑树怎么做，首先可以按照 dfs 序放点，然后这样一个点经过的次数不对可以向他父亲走一步再走下来。这样逐次向上调整，最后只会留下根，注意到我们可以随便定终点，如果根走的次数不对可以在前一步停止，因为路径的最后一步一定是根。
对于图的情况，随便取出一个生成树做即可，大约是 \(3n\) 的。
P9871 [NOIP2023] 天天爱打卡
设 \(f_i\) 表示第 \(i\) 天不跑步的最大收益，有
记最后那个数是 \(w_j\)，扫描加入 \(r_k=i\) 的 \(k\)，影响一段区间。
一个简单的事实：跑步是为了拿奖，也就是说不拿奖肯定不会跑步，因此每次转移的 \((j,i)\) 必然是包含了至少一个区间。
假设知道要包含哪些区间，那么 \((j,i)\) 是要尽量短的。因此可能的 \(j,i\) 会是 \(l_k-1\) 或 \(r_k+1\) 之类的。
还有一种是，由于 \(k\) 的限制，无论如何都包含不了一个区间的，但是我要转移啊，\(f_i=\max f_j-(i-j-1)d\)。
两个问题：1.为什么这样不会使得同时途两个颜色？