OI

「省选联考 2021」矩阵游戏

OI

首先可以发现，若不考虑 \(a_{i} \leqslant 10^{6}\) 的限制，那么构造一组合法解是容易的。

同时可以发现，如果对一行或一列进行 \(+1, -1, +1, -1, \cdots \) 操作，那么得到的 \(a_{i}\) 还是合法的。

Read more

「省选联考 2021」图函数

OI

首先考虑分析 \(f(u, G)\)，可以观察出一些性质 ：

  • 会产生贡献的 \(v\) 必须满足 \(v \lt u.\)
  • \(v\) 与 \(u\) 会产生贡献当且仅当 \(u\) 和 \(v\) 可以仅通过大于 \(v\) 的点互达。

有两个显然的性质 ：

Read more

「省选联考 2021」卡牌游戏

OI
可以证明，若进行了操作 \(a_{i} \to b_{i}\)，那么 \(\forall j \lt i\)，操作 \(a_{j} \to b_{j}\) 都进行了。因为如果存在 \(j \lt i\)，\(a_{i} \to b_{i}\) 执行了，但 \(a_{j} \to b_{j}\) 没执行，那么 \(a_{i} \to b_{i}\) 执行就没有意义，因为 \(a_{j}\) 还是会作为最小值。
Read more