[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 \neq n\)：\(opt(j,j+1) \rightarrow opt(i,j+1) \rightarrow opt(j,j+1) \rightarrow opt(i,j)\)，命名为操作 \(\alpha(i,j)\)。
  • \(i \neq 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<j)\) 去跟 \(C_i\) 匹配，能消就消掉。

下面证明总操作次数是小于 \(31000\) 的，对于操作 \(\gamma\) 最多只会进行 \(N\) 次，不考虑，对于操作 \(\alpha,\beta\)，单次操作需要消耗 \(4\) 个次数，最多进行 \(O(\frac N 2 \times \frac N 2) 次\)，最大次数约等于 \(10000\) 次，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;const int N=105;
const int LIMIT=31000; 
int n,m;
int aa[N],a[N],b[N],c[LIMIT<<1],d[LIMIT<<1];// (i, j) -> (j - 1, i + 1)
inline void opt(int i,int j){// cout<<i<<" "<<j<<"\n";c[++m]=i,d[m]=j;swap(a[i],a[j]);a[i]--,a[j]++;
}// (i, j) -> (i - 1, j + 1)
// j != n, cost : 4
inline void change1(int i,int j){opt(j,j+1);opt(i,j+1);opt(j,j+1);opt(i,j);
}
// i != 1, cost : 4
inline void change2(int i,int j){opt(i-1,i);opt(i-1,j);opt(i-1,i);opt(i,j);
}// i = 1, j = n, cost : 8
inline void change3(int i,int j){change1(i,j-1);change2(j-1,j);
}// (i, j) -> (i + 1, j - 1)
// j != n, cost : 4
inline void change4(int i,int j){opt(i,j);opt(j,j+1);opt(i,j+1);opt(j,j+1);
}// i != 1, cost : 4
inline void change5(int i,int j){opt(i,j);opt(i-1,i);opt(i-1,j);opt(i-1,i);
}// i = 1, j = n, cost : 8
inline void change6(int i,int j){change5(j-1,j);change4(i,j-1);
}inline void in1(int i,int j){if(j!=n) change1(i,j);else if(i!=1) change2(i,j);else change3(i,j);
}inline void in2(int i,int j){if(j!=n) change4(i,j);else if(i!=1) change5(i,j);else change6(i,j);
}inline void output(){assert(m<=LIMIT);cout<<"Yes\n";cout<<m<<"\n";for(int i=1;i<=m;i++) cout<<c[i]<<" "<<d[i]<<"\n";
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++) cin>>aa[i];int sum=0;for(int i=1;i<=n;i++) cin>>b[i],a[i]=aa[i]-b[i],sum+=a[i];if(sum){cout<<"No\n";return 0;}if(n==2){if(a[1]==0&&a[2]==0) output();else if(aa[1]+1==b[2]&&aa[2]-1==b[1]){//这里的特判要注意不能用下面的change操作的标准，因为只有两个数不合法。opt(1,2);output();}else cout<<"No\n";return 0;}for(int i=1;i<=n;i++){if(!a[i]) continue;if(a[i]>0){for(int j=i+1;j<=n;j++) while(a[i]>0&&a[j]<0) in1(i,j);}else{for(int j=i+1;j<=n;j++) while(a[i]<0&&a[j]>0) in2(i,j);} }output();return 0;  
}