【补题】CF
昨晚 CF 掉大分了。。。补一波以前比赛的题
CF702 (Div.3)
CF701
E. Move and Swap
确实比 F 难。
考虑 DP。首先蓝点与红点一定在同一层，且由于蓝点可以走到下一层任一点，因此只需要记录红点位置即可刻画出当前状态，设 \(f[u]\) 为红点在 \(u\) 时的最大值，转移时考虑是否交换：
- 不交换：红点直接从父亲走下来，蓝点走到当前层权值最大/最小的点
- 交换：蓝点变到 \(u\)，红点在这层任选，即为 \(f[fa[v]]+|a[u]-a[v]|\)，拆开绝对值得到 \(\max(\max\{f[fa[v]]-a[v]\}+a[u],\max\{f[fa[v]]+a[v]\}-a[u])\)
- 从限制多/状态少的入手
- \(|a-b|=\max(a-b,b-a)\)
F. Copy or Prefix Sum
哈希表被卡
CF700
E. Continuous City
Acfboy
显然要从二进制入手，但思考&实现细节都很多。也许可以先忽略点编号随便连边，然后拓扑排序？
- 通过连一条 \(l-1\) 的边可以把值域平移到 \([1,r-l+1]\)
- 先解决 \(r=2^{k}\) 的情况在尝试以此为基础扩展