AGC024E Sequence Growing Hard
AtCoder Luogu 分析 假设当前要插入一个数 $x$,那么只能插入到序列末尾或者一个 $<x$ 的数之前。 我们把操作序列转化为一棵树,每个节点都是一个二元组 $(w, t)$,表示第 $t$ 次操作在其父节点插入的数前插入了 $w$。为了方便我们新建一个点 $(0, 0)$ 作为根,表示插入到序列末尾。 那么这棵树满足:$t$ 是 $[0, n]$ 的排列、$w\in [0...
AtCoder Luogu 分析 假设当前要插入一个数 $x$,那么只能插入到序列末尾或者一个 $<x$ 的数之前。 我们把操作序列转化为一棵树,每个节点都是一个二元组 $(w, t)$,表示第 $t$ 次操作在其父节点插入的数前插入了 $w$。为了方便我们新建一个点 $(0, 0)$ 作为根,表示插入到序列末尾。 那么这棵树满足:$t$ 是 $[0, n]$ 的排列、$w\in [0...
AtCoder Luogu 分析 题目相当于限定只能放在两个圆中间,求放 $2n$ 个车的方案数。 事实上我们可以对每一列求出其能放置车的范围 $[L_i, R_i]$。可以发现,对于所有 $i\in[n, 2n)$,都有 $L_i = 0$。 如果所有 $L_i$ 都为 $0$,这就是一个经典问题:将 $R_i$ 从小到大排序,答案即为 $\prod_{i = 0}^{2n - 1} (R...
先放一点上来,剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP:设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A,最后一个是 A/B 是否可行,转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$,为真的 $j$ 一定是一段区间,因此我们只需要维护这段区间,即可去掉 $j$ ...
Luogu 分析 预处理斯特林数和阶乘,换根 DP 求出后面的东西即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/s...
Luogu LOJ 分析 由 Lucas 定理可以推出,${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。 为了方便,我们倒过来 DP,则要求上一个数是这一个数的子集,直接枚举子集转移即可。 复杂度是 $\mathcal{O}(3^{\log A})$ 的。 代码 //...
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 分析 问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大,这里 $1$ 个点也算一条路径。 先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和,转移讨论各种情况把子树合并进来即可。 设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和,通过打表或...
Luogu LOJ 分析 首先把第 $k$ 大转化掉: 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和,并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...