CF932F Escape Through Leaf
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费,显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树,转移时直接查询对应位置的最小值,然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费,显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树,转移时直接查询对应位置的最小值,然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
Luogu LOJ 分析 考虑从 $x$ 传递到 $y$ 的代价,显然有 这样子就可以 $\mathcal{O}(m2^m)$ 预处理 $g(x,S)$ 和求 $f_S$,总时间复杂度 $\mathcal{O}(m2^m)$。 然而存 $g$ 需要 736MB 空间,并开不下。 但是可以发现,我们只需要求 $x\in S$ 的 $g(x,S)$,所以我们只需要对每个 $x$ 求 $2^{m...
Codeforces Luogu 分析 设 $dp_{l,r,0/1/2,0/1/2}$ 表示 $[l,r]$ 段,$l$ 没有颜色/红色/蓝色、$r$ 没有颜色/红色/蓝色的方案数。 当 $r-l+1=2$ 时为边界,有 $dp_{l,r,1,0}=dp_{l,r,2,0}=dp_{l,r,0,1}=dp_{l,r,0,2}=1$。 考虑转移。 如果 $l,r$ 是一对匹配的括号,直接从...
Codeforces Luogu 分析 有一个显然的状压 DP:设 $dp_{i,S}$ 表示前 $i$ 个人,$S$ 中的位置被选中时的最大力量值,转移枚举当前这个人当观众还是进某个位置即可。 然而 $p+k\leq n$,所以这个做法不太行。 注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序,当 $i-|S|>k$ 时 $i$ 显然不会被选...
Luogu LOJ 分析 为了方便,将陷阱作为根节点。那么冷静分析一下可以得到一些结论(没有证明) 当老鼠走到一个叶节点时,它将被困住。 当老鼠被困住时,将其它岔路口堵住,然后将到根的路径擦干净是最优的。 设 $f_u$ 表示老鼠进入 $u$ 子树后回到 $u$ 的最小操作次数。显然老鼠会找一个 $f$ 最大的子树进去,所以堵住 $f$ 最大的子树最优,此时老鼠会进入 $f$ 次大的子树...
Luogu LOJ 分析 发现题目中那个 LCS 的限制不好处理,考虑建一个自动机来解决这个问题。 假设我们已经建出了自动机,我们就可以设 $f_{i,j,k}$ 为前 $i$ 个字符,已经转移到自动机的 $j$ 节点,已经匹配到了 NOI 的第 $k$ 位的方案数,然后根据 $k$ 转移即可。 现在考虑如何建这个自动机。考虑求两个串的 LCS 的过程,即设 $g_{i,j}$ 表示第一个串...
Codeforces Luogu 分析 显然对于合法的图,满足不在最短路树上边连接的点在同一层。 设 $f_{i,j}$ 表示前 $i$ 个点,$[i-j+1,i]$ 中的点在同一层时的方案数,$g_{i,j,k}$ 表示这一层有 $i$ 个点,上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。 $f$ 的转移不难得到:枚...
Luogu LOJ 分析 首先可以发现,$i$ 只能被 $\geq i$ 的开关操作掉。从而我们只需要从大到小模拟一遍,如果 $i$ 亮着就操作 $i$ 开关,就可以算出最小需要操作的次数 $c$ 了。这样子就可以拿到 $50$ 分(实际上有 80 分)。 冷静分析一下可以发现,达到目标所需要按的开关组合是唯一确定的。我们把这些开关叫做正确的。 考虑一个 DP。设 $dp_i$ 表示从剩余 ...
LOJ 分析 容易想到容斥,计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$,因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌,所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
Codeforces Luogu 分析 为了方便,把串翻转,条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。 可以发现一个性质,即在一定存在一组最优解使得 $|t_i|=i$,因为某个不满足的串删去多的部分一定不会差。 于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。 然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-...