前晚 CF div3 EFG口糊

2026-01-14 23:03:31

发布于：广东

20阅读

0回复

0点赞

我带错题了吗。为什么我一个早读想出来 EFG 还有一堆人说难的。

E

定义数组 $B$ 满足 $B_i=|A_i-A_{i-1}|$ ，则答案为 $\min_{j=l}^r B_j\ge k$ 的 $l,r$ 数量。

显然可以 set $O(n\log n)$ 求出。

未来十年无人看懂出题人设计意图。

考虑树形 DP。令 $dp[i][j]$ 表示是否可以通过 $3k+j$ 次操作将 $i$ 的子树删完。显然是个背包问题，可以 $O(nk^2)$ 解决，答案就是 $dp[1][0]$ 。

优化 1:压位，可以做到 $O(nk)$ 。

优化 2:在压位的基础上预处理所有更新情况，做到 $O(k2^{2k}+n)$ 。

何意味。这是 div3 最后一题？出题人我真求你了。

注意到 $d$ 单调递增， $\min A_i$ 单调不增，所以 $d-\min{A_i}$ 单调递减，可以线段树二分得出是否存在。显然如果存在答案一定为 $1$ 。

$O(n+q\log n)$ 。

有帮助，赞一个

去预览

0/2000