题解：P9841 [ICPC 2021 Nanjing R] Puzzle in Inazuma

· · 题解

比较厉害的题。题目给的操作太过于神秘，考虑用已有的操作构造出更加简单的操作。

初始的操作形如：

选四个点 a,b,c,d 和一个值 x，把 \newcommand{\lra}{\leftrightarrow} a\lra b,a\lra c,a\lra d 的权重增加 x，把 \newcommand{\lra}{\leftrightarrow} b\lra c,b\lra d,c\lra d 的权重减小 x。（后面将其简记为 \text{Op4}(a,b,c,d)）

这个操作看起来比较难受，考虑用这个操作搞出一些更简单的操作。

扩展到五个点的情况，用 \text{Op4} 操作搞一些更人类的操作。一个构造方案是：

选五个点 a,b,c,d,e 和一个值 x，并依次执行下面的操作：

  • \text{Op4}(c,a,d,e,x)
  • \text{Op4}(e,a,b,d,x)
  • \text{Op4}(c,a,b,d,-x)
  • \text{Op4}(e,a,b,c,-x)

然后考虑执行这四次操作会发生什么。

最终 \newcommand{\lra}{\leftrightarrow}a\lra b,a\lra c 两条边的边权增加了 x，\newcommand{\lra}{\leftrightarrow}a\lra d,a\lra e 两条边的边权减少了 x。这里把这个操作记作 \text{Op5}(a,b,c,d,e,x)。

看上去还是比较复杂，因此考虑继续利用已有操作来简化操作：

选五个点 a,b,c,d,e 和一个值 x，并依次执行下面的操作：

  • \text{Op5}(a,b,c,d,e,x)
  • \text{Op5}(a,b,d,c,e,x)

容易发现这个操作其实就是让 \newcommand{\lra}{\leftrightarrow}a\lra b 的边权增加 2x，\newcommand{\lra}{\leftrightarrow}a\lra e 的边权减少 2x。记这个操作为 \text{Op}(a,b,c,d,e,x)。

继续扩展到六个点的情况。

选六个点 a,b,c,d,e,f 和一个值 x，并依次执行下面的操作：

  • \text{Op}(a,b,c,d,e,x)
  • \text{Op}(a,d,e,c,f,x)

此时这个操作会让 \newcommand{\lra}{\leftrightarrow}a\lra b 的边权增加 x，\newcommand{\lra}{\leftrightarrow}a\lra f 的边权减少 x。

然后观察到不论执行多少次操作，边权的和都不会变。考虑简化题意，用第一个图减去第二个图，问题就变为从一个带权图出发，执行若干次操作最终使得这个图的所有边权均为 0。因此容易发现若边权的和不为 0，则必然无解。否则必然有解，直接把边权转移过去即可。容易证明该策略满足查询数量的限制。

但是因为这个操作需要用六个点才可以正确执行，所以需要特判 n\in\lbrace4,5\rbrace 的情况。