洛谷5324 [BJOI2019]删数
Luogu LOJ 分析 可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。 于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。 代码 // ==================================...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。 于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。 代码 // ==================================...
Luogu LOJ 分析 设 $f_i$ 为从 $i$ 点生命值变为 $0$ 点生命值的期望步数，$p_i$ 为生命值 $\geq i$ 时一回合扣掉 $i$ 点生命值的概率，那么有 直接高斯消元是 $\mathcal{O}(n^3)$ 的，只能获得 70 分。 但是这个矩阵很有性质。我们从上往下消，消到每一行时只会有 $3$ 个位置（包括常数项）有值，也就是只要消三列。最后一行时只会剩下...
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
Luogu LOJ 分析 一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。 不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。 再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。 这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那...
Luogu LOJ 分析 首先注意到学校选择导师和选择派系是等价的。 考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立，可以分开处理。 设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数，$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。最后卷积合并即可。 考虑 $k\neq 0$ 的情况。注意到有限...
Luogu LOJ 分析 先考虑一个贪心。我们把 $d_i$ 从大到小排序，那么每个子树都对应一段区间，我们把儿子按照编号排序，然后把区间依次划分下去即可。 这样子只能通过所有 $d_i$ 互不相同的点，原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。 考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数，那么节点 $u$ 只...
Luogu LOJ 分析 问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大，这里 $1$ 个点也算一条路径。 先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和，转移讨论各种情况把子树合并进来即可。 设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和，通过打表或...
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...