526互联

Atcoder Beginner Contest 317(F~G)

发布时间 2023-08-27 19:49:28作者: ydtz

两发罚时：

  1. D long long。
  2. E bfs 不在把元素扔进队列前标记。

F. Nim

考虑 \(a_i\) 很小，\(n\) 很大，于是不妨数位 dp。

设 \(dp_{i,p_1,p_2,p_3,0/1,0/1,0/1}\) 表示对于前 \(i\) 位，\(x_1/x_2/x_3\) 当前取模 \(a_1/a_2/a_3\) 的值为 \(p_1/p_2/p_3\)，且当前 \(x_1/x_2/x_3\) 在前 \(i\) 位中是否严格顶着 \(n\) 的上界。

可以考虑使用记忆化搜索实现。整十数取模 \(a_1/a_2/a_3\) 的值可以通过预处理得到。实现时考虑下 \(n\) 的当前位是 \(1\) 还是 \(0\)，填当前位时只要满足 \(x_1,x_2,x_3\) 的当前位异或和为 \(0\)，且都不超过上界即可。

时间复杂度 \(O(\log a\sum a_i)\)。

G. Rearranging

一副匹配的样子，可惜赛时手速太慢没时间给这题了。

考虑对于每一列单独来看，行和数字构成了匹配关系。不妨考虑将 \(n\) 行作为左侧节点，\(n\) 种数字作为右侧节点，由每一行向该行包含的对应数字连边，边可重。

对于每一列分别作匹配，即作 \(m\) 轮匹配，每次匹配由源点向每一行连一条边权为 \(1\) 的边，由每种数字向每一列连一条边权为 \(1\) 的边。不难发现，每次匹配会消耗左侧所有点的一条出边，以及右侧所有点的一条入边，由于左侧所有点初始出度皆为 \(m\)，右侧所有点初始入度皆为 \(m\)，由 Hall 定理可证明一定可以进行 \(m\) 轮有解的匹配。

每次匹配完毕后 check 一下整张图，填一下当前列的数即可。

图中共有 \(2n\) 个点和 \(nm\) 条边，时间复杂度 \(O(nm\sqrt n m)=O(n^{1.5}m^2)\)。