首页 > 编程学习 > AtCoder Beginner Contest 267

AtCoder Beginner Contest 267

发布时间:2022/9/5 19:16:10

https://atcoder.jp/contests/abc267

全部的 AC 代码:

https://atcoder.jp/contests/abc267/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi

E

题目要求最小化花费,而花费是所有花费的最大值,故考虑二分,记现在二分的值 \(mid\)\(lim\)

因为每次代价都是与删点所连点的边权和,所以尽量去找当前花费 \(\leq lim\) 的,找不到当然就继续去二分更大的值。

因此,我们可以执行一个 \(\tt{bfs}\),每次找花费 \(\leq lim\) 的点进行扩展,并在扩展当前点的同时对其邻点更新花费(也就是减去当前点权),当临点更新后花费 \(\leq lim\) 时入队。

F

由于需要求 \(u\) 点跳 \(k\) 步能够到达的树上的点,故尽可能找到 \(u\) 能够跳到的最远点,因为如果 \(u\) 跳到最远点都不足 \(k\) 步,那么必然无解

什么点可能成为距 \(u\) 的最远点呢?直观的想法是直径的两个端点 \(x, y\)

证明:

不妨设 \(dis(u, x)\geq dis(u, y)\)

假设能够找到点 \(v\) 使得 \(dis(u, v)> dis(u, x)\),那么找到 \(u\) 到达路径 \(x, y\) 上的点 \(u'\)

我们有 \(dis(u', v)>dis(u',x)\),故 \(dis(u', v)+dis(u', y)=dis(v, y)>dis(u', x)+dis(u', y)=dis(x, y)\),与 \(x, y\) 为直径矛盾。

证毕。

下面的做法很简单:

就分别以 \(x, y\) 为根节点,求出 \(u\)\(k\) 级祖先即可。

G

为了方便转移,对所给序列 \(w\) 进行升序排序

容易想到状态表示 \(f[i, j]\) 为前 \(i\) 个元素共有 \(j\) 个位置 \(pos\) 满足 \(w_{pos}<w_{pos+1}\)。(记为顺序位置

考虑 \(f[i, j]\) 如何转移到后面的状态。

对于第 \(i+1\) 个元素 \(w_{i+1}\),可以发现当插入 \(w_{i+1}\) 时(也就是将 \(w_{i+1}\) 挑选 \([1, i+1]\) 一个位置放入),要么会使原来的顺序位置个数不变,要么比原来多 \(1\)

  • 对于不变的情况,有多少种方案呢?

    • 首先,插入位置 \(1\) 肯定不变,有一种。
    • 插入到与 \(w_{i+1}\) 等值的元素(记这样的元素有 \(cnt\) 个)后面,有 \(cnt\) 种。
    • 插入到已经产生的顺序位置 \(pos\) 的后面(也就是插入 \(pos, pos+1\) 之间),有 \(j\) 种。

    因此,\(f[i, j]\)\(f[i+1, j]\) 的贡献为:\(f[i+1, j] += f[i, j]\times(1+cnt+j)\)

  • 比原来多 \(1\) 的情况就是不变情况的补,即有 \(i+1-(1+cnt+j) = i-j-cnt\) 种,

    因此,\(f[i, j]\)\(f[i+1, j]\) 的贡献为:\(f[i+1, j+1] += f[i, j]\times(i-j-cnt)\)

EX

注意到值域很小,所以直接将答案拆奇偶然后进行 NTT 分治来合并背包即可。

记当前区间 \(u\) 取奇数个物品的背包为 \(u_{o}\),偶数个的为 \(u_{e}\),左右子区间分别记为 \(ls, rs\)

分治过程即:

\[u_o = merge(ls_e, rs_o) + merge(ls_o, rs_e) \\ u_e = merge(ls_e, rs_e) + merge(ls_o, rs_o) \]

\(merge\) 用 NTT 卷积即可。

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号