[ARC198C] Error Swap

题目传送门

构造

题意

给定长度为 $ N $ 的两个整数序列 $ A=(A_1,A_2,\dots,A_N) $ 和 $ B=(B_1,B_2,\dots,B_N) $。
你可以执行以下操作最多 $ 31000 $ 次：

• 选择满足 \(1 \le i < j \le N\) 的整数对 \((i,j)\)，并将 \(A_i\) 替换为 \(A_j - 1\)，\(A_j\) 替换为 \(A_i + 1\)。
  

你的目标是使 \(A = B\)。判断目标是否可以实现，如果可以实现，请输出一个满足条件的操作序列。
题解

这种题都是都需要套路地将题目给出的操作组合成一种容易维护的操作。
设题目给定的操作为 \(opt(i,j): (A_i,A_j) \rightarrow (A_j-1,A_i+1)\)。
发现只对 \(2\) 个元素操作只能得出有且仅有的另一种状态，所以我们考虑一种对三元组的操作，经过手玩可以总结出下面几个操作：

• \((A_i,A_j) \rightarrow (A_i-1,A_j+1)\)
  
  
  
  • \(j\) ≠ \(n\)：\(opt(j,j+1) \rightarrow opt(i,j+1) \rightarrow opt(j,j+1) \rightarrow opt(i,j)\)，命名为操作 \(\alpha(i,j)\)。
    
  • \(i\) ≠ \(1\)：\(opt(i-1,i) \rightarrow opt(i-1,j) \rightarrow opt(i-1,i) \rightarrow opt(i,j)\)，命名为操作 \(\beta(i,j)\)。
    
  • \(i=1,j=n\)：\(\alpha(i,j-1)\rightarrow\beta(j-1,j)\)，命名为操作 \(\gamma(i,j)\)。
    
  
  
• \((A_i,A_j) \rightarrow (A_i+1,A_j-1)\)：就是上一种操作的逆向操作。
  

我们有了上面两种操作，就可以随便做这道题目了。

令 \(C_i=A_i-B_i\)，则我们枚举每一个 \(C_i\)，并枚举 \(C_j(i