2021-10-17高二CSP模拟赛23

发表于 2021-10-20 更新于 2021-10-21

$OI$ 之神啊，请赐予我力量

牛表

可以想到一个非常暴力的做法，直接连边跑 $floyd$ , 复杂度 $O(n^3)$ .

然后有两种优化方法，一个比一个不正经

发现从 $x$ 到 $x^2$ 花费为 $0$ . 然后从 $x$ 向 $x^2$ 连边建图，然后跑 $Tarjan$ 缩点。缩完点之后再套个循环展开跑 $floyd$ ， $95$ 分。

打表发现答案不会特别大，不会超过 $20$ , 所以只需要连接长度小于 $20$ 的边，然后跑 $dij$ 就行了.

考虑 $O(n^3)$ 暴力 $dp$ , 这是很显然的。

然后考虑卡常。

发现每次改为 $0$ 的点原来的值是区间的最大值。因为这样显然是最优的

一些结论：

$f_n$ 为 $2^n-1$ .

$G(x) = 2^{popcount(x)} - 1$

$[((i*c)\&G(i))=i] = [((i*(c-1)\&G(i))=0]$

设 $cnt$ 表示 $c$ 末尾 $0$ 的个数.

$F(x)$ 表示 $c$ 最后一个 $1$ 的位置，那么只需要保证 $F(x) <= cnt$

根据这个就可以计算出答案了。