AGC
A Range Flip Find Route
设 $dp(i,j)$ 表示使得从 $(1,1)$ 能走到 $(i,j)$ 所需的最少操作数目.
$dp(i,j)$ 可以由 $dp(i-1,j),dp(i,j-1)$ 转移来.
若 $(i,j)$ 初始是 . ,则不需要额外花费.
若上个位置和 $(i,j)$ 初始都是 # ,就不需要额外的花费,可以将覆盖上个位置的矩形拓展,不会影响接下来的路径.
若上个位置初始是 . ,但 $(i,j)$ 初始是 # ,就需要操作一次将它变为 . .
B 123 Triangle
为了方便,假定所有 $a_i$ 从 $0$ 开始标号,可以先将所有 $a_i$ 减去 $1$ ,因为 $n>1$ ,所以不会影响答案.
先考虑判断答案是否为 $1$ ,可以把 $2$ 也看作 $0$ ,做差取绝对值改为两者异或,若最后剩下 $1$ ,说明原答案也是 $1$ .
异或的性质就比较好了,有结合律和交换律,根据帕斯卡三角可知, $a_i$ 对最后剩下的数产生贡献的次数为 $\binom {n-1} i$ .
用 Lucas 定理判断哪些 $a_i$ 对最后剩下的数对贡献次数为奇数,即可判断答案是否为 $1$ .
当答案不为 $1$ 时,我们还要区分答案是 $0$ 还是 $2$ .
注意到若初始数列中有至少一个 $1$ ,答案就不可能为 $2$ .
因为若全部都是 $1$ ,操作一次后会变成全部为 $0$ ,否则某个 $1$ 会与 $0$ 或 $2$ 相邻,操作一次后至少还有一个 $1$ .
当初始数列中没有 $1$ 时,判掉全部是 $0$ 的情况,其余情况可以将所有数 $/2$ ,变成只有 $0,1$ ,算出答案后 $\times 2$ 即可.
C Giant Graph
观察一个点对答案的贡献形式,不难发现我们应该贪心拿编号之和 $i+j+k$ 最大的点.
即按照 $i+j+k$ 从大到小枚举三元组,若它能被加入独立集,就贪心将其加入,时间复杂度是 $O((n+m)^3)$ 的.
考虑转化模型,假定在三张图上各有一个棋子,A 与 B 轮流操作,每一步选一个棋子,把它沿边移动到编号更大的点上.
若某人操作时,不能做出任何移动,就输了.
不难发现三元组 $(i,j,k)$ 在独立集中,当且仅当三个棋子分别在 $(i,j,k)$ 时,先手必败.
即 $SG(X,i)\oplus SG(Y,j)\oplus SG(Z,k)=0$ ,把 $SG$ 值预处理出来,枚举 $SG(X,i),SG(Y,j)$ 即可统计答案.
$SG$ 值的上界是 $O(\sqrt m)$ 的,于是时间复杂度为 $O(n+m)$ .