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.为什么这样不会使得同时途两个颜色?