AGC 017 题解

比赛

A dp 一下就好了

B

枚举减了多少次，算出这个 n - 1 项数列末项的最小值和最大值，显然这个范围内任何一个数都是可达的

check b 是否在范围内就好了

*C

设 f[i] 表示按 ai 排序的某个前缀 i 个球，是否合法

显然 f[i + num[j]] 在 i + num[j] = j 的时候也是合法的

到这里就不会了，，，

题解巧妙的转化成了线段覆盖，i 号球的是 [i - num[i], i] 这一段，答案就是 [0, n] 间没被覆盖的线段数

为什么？首先所有线段被覆盖次数之和为 n，那么没被覆盖的线段需要从 重复覆盖的线段 移过去，正确性显然。

*D

竟然是经典套路。。学习一波

Hackenbush删边游戏，sg[x] = XOR( sg[son] + 1 )，好像归纳法可证

这玩意还有一些奇奇怪怪的扩展，比如无向连通图上玩游戏。。。

这就需要用环搞事情了（不会

*E

大概想到要转化成图上问题了，但暴力建边 n^2 + 哈密顿路径显然不可做。。。

考虑欧拉路径，h 只有 200，我们将左边贴地高度 k 的形状 和右边离地高度 k 的形状 标号 k，左边离地高度 k 的形状 和右边贴地高度 k 的形状 标号 -k，那么每个积木就成了连接两个形状的有向边

问题就转化成了：能否找到若干条 s -> t 的路径，包含所有边且 s > 0, t < 0

这需要满足条件：

  • x > 0, in[x] <= out[x]
  • x < 0, in[x] >= out[x]
  • 在每个（弱）连通分量中，必须有一个点 x, in[x] != out[x]

正确性还是比较显然的，证明考虑不断拿环就好了。

upd: 别忘了连双向边（可以从 t 搜回 s）

*F

咕咕