Atcoder Beginner Contest 420

A、B、C

过

D

显然直接 BFS，记录一下当前机关情况 \(g\)，每次踩到机关 \(g \oplus 1\)。

E

显然并查集直接维护就行了。

注意写并查集的时候如果两个点的根节点相同一定要特判。

WA 了 \(\infty\) 发。

G

MO。

\(n^2 + n + X = Y^2\)，配方有 \((n + \frac{1}{2})^2 + X - \frac{1}{4} = Y^2\)，移项 \((2n + 1)^2 - 4Y^2 = 1 - 4X^2\)。

平方差公式，\((2n + 1 - 2Y)(2n + 1 + 2Y) = 1 - 4X^2\)，令 \(A = 2n + 1 - 2Y, B = 2n + 1 + 2Y\)，则 \(n = \frac{A+B-2}{4}\)。

注意到 \(1 - 4X^2\) 为奇数，且 \(A\) 与 \(B\) 都是奇数。

因为 \(n\) 是整数，所以 \(A + B \equiv 2 \pmod 4\)，又 \(A, B \equiv 1 \pmod 4\) 或者 \(A, B \equiv 3 \pmod 4\)。

所以当且仅当 \(A \equiv B \pmod 4\) 时合法，直接强行枚举一下 \(1 - 4X^2\) 的因数然后判断即可。

\(\Theta(\sqrt N)\)。

F

正在学习