671
Codeforces Round 671 (Div. 2) A. Digit Game
\(R\) 和 \(B\) 在玩一个数字游戏,给一个含有 \(n\) 位的正整数 \(x\) 。俩人轮流操作, \(R\) 先行动。 在每一步中,\(R\) 可以选择 \(x\) 中一个未被标记的奇数位置并标记,\(B\) 可以选择 \(x\) 中一个未被标记的偶数位置并标记。 当最后只剩下一个未被 ......
CF671D Roads in Yusland
1D8 ya。 设 \(f_{u,i}\) 表示覆盖了 \(u\) 子树并且向上覆盖到了深度为 \(i\) 的最小代价。 考虑合并儿子 \(v\): \[f'_{u,i}\gets \min\left(f_{u,i}+\min\limits_{j=1}^nf_{v,j},f_{v,i}+\min\l ......
CF671C Ultimate Weirdness of an Array
区间 max gcd 计数显然没有任何性质,考虑倒序枚举,转化为计算 \(\sum_i\sum_{l,r}[f(l,r)\ge i]\)。 考虑用一个线段树维护这个东西。\(x\) 节点上存最小的满足 \(f(x,r)<i\) 的 \(r\)。那么一次操作只需要全局求和。 我们考虑 \(i+1\to ......