题解 P7362 [eJOI 2020 Day2] XOR Sort
a___
·
·
题解
题目描述
给定一个长为 N 的序列 A_i（A_i\leq2^{20}），你可以进行如下操作：
选定一个位置 i，将 A_i 修改为 A_i \oplus A_{i+1} 或 A_i \oplus A_{i-1}。
你要构造一个长度不超过 4\times10^4 的操作序列把 A_i 变为：
$S=2$，非严格单调递增序列，即 $A_i \le A_{i+1}$。（$n\leq1000$）
______
看见这神奇的数据范围就知道这题显然是二合一。
_____
先来考虑 $S=1,n\leq200$ 的情况。
有一个很谔谔的想法显然就是直接给这个数组排序。
我们知道三次异或可以交换两个数，而排序需要交换逆序对个数次，于是，通过冒泡排序，我们就获得了一个最劣 $\frac 32n(n-1)$ 次交换的做法。然而这个做法只能通过 $n\leq150$ 的数据，并不能通过本题。
我们发现这个 $\frac32$ 很讨厌，如果能优化掉就好了。
考虑换一种排序方式，改为选择排序，即每次选出最大的数，放到最后。
如果我们能在 $2n$ 次操作内将一个数换到一个长度为 $n$ 的数组最后，那么我们就可以完成这道题。
考虑到异或的性质，我们想到这样一个做法：
首先，对于 $\forall A_i$，令 $A_i=A_i\oplus A_{i+1}$；
然后，设最大值的位置为 $p$，对于 $\forall A_i,i\in(p,n]$，从前往后依次使 $A_i=A_i\oplus A_{i-1}$；
最后，对于 $\forall A_i,i\in[1,p-1)$，从后往前依次使 $A_i=A_i\oplus A_{i+1}$。
此时，整个序列变为 $[A_1\oplus A_p,A_2\oplus A_p,\dots,A_{p-1}\oplus A_p,A_{p+1}\oplus A_p,\dots,A_n\oplus A_p,A_p]$。
举个具体的例子，原序列为 $[a,b,c,d,e,f]$，$max=d$。
首先，将序列变为 $[a\oplus b,b\oplus c,c\oplus d,d\oplus e,e\oplus f,f]$；
然后，从第四个位置向后异或，序列变为 $[a\oplus b,b\oplus c,c\oplus d,d\oplus e,d\oplus f,d]$；
最后，从第三个位置向前异或，序列变为 $[a\oplus d,b\oplus d,c\oplus d,d\oplus e,d\oplus f,d]$。
于是这样的 $2n$ 次操作过后我们成功地把 $d$ 换到了最后并消除了其影响。
你可能觉得所有数都被异或了一个 $d$，怎么算是消除了影响；但是考虑下次做那个每个数异或下一个数的变换时，其实会把所有的 $d$ 消掉。
于是我们就有了一个约 $n(n-1)$ 次操作的做法。可以通过本题。
_____
再考虑 $S=2,n\leq1000$ 的情况。
发现限制条件放松了，可以相等了。
我们显然又有一个非常谔谔的想法，就是把所有数都变成一样的 —— $0$。
考虑从高到低枚举每一位，尝试让所有数的这一位都变成 $0$。
具体方法是，设当前枚举到第 $k$ 位，从前往后对于 $\forall i,A_{i,k}=1$，若 $A_{i+1,k}=0$，则令 $A_{i+1}=A_{i+1}\oplus A_i$。然后令 $A_i=A_i\oplus A_{i+1}$。
还是举个具体的例子：
对于 $[1,0]$，先将其变为 $[1,1]$，再将其变为 $[0,1]$；
对于 $[1,1]$，则直接将其变为 $[0,1]$。
发现有一个问题，就是我们无论如何异或，如果 $n$ 个数中有一个数这一位为 $1$，那么最后总会有至少一个数这一位为 $1$。
也就是说，我们不可能把所有数都变成 $0$ 了。
然鹅你会发现，按照刚才那个算法其实已经能够通过本题。因为我们是从高位往低位做的，每次我们把单独一个不得不留下的 $1$ 放到最后，而这个数一定会比前面所有数都大。。。唯一要注意的一点就是不要让已经被搁置在后面的数再参与运算。
这个算法操作次数不超过 $20\times2n$ 次，刚好足以通过本题。
_____
那么本题思路就讲完了，以下是压行代码：
```cpp
#include<bits/stdc++.h>
const int N=1010,M=4e4+10;
int n,s,a[N],cnt,tot,flg;std::pair<int,int>ans[M];
int main()
{
int i,j,k;scanf("%d%d",&n,&s);for(i=1;i<=n;i++)scanf("%d",&a[i]);
if(s==1)
for(k=n-1;~k;k--)
{
for(i=j=1;i<=k+1;i++)(a[i]>a[j])&&(j=i),(i<n)&&(ans[++cnt]=std::make_pair(i,i+1),0);
for(i=j;i<=k;i++)ans[++cnt]=std::make_pair(i+1,i),a[i]=a[i+1];
for(i=j-1;i>1;i--)ans[++cnt]=std::make_pair(i-1,i);
}
else
for(k=19,tot=0;~k;k--)for(i=1,flg=(a[n-tot]>>k)&1;i<n-tot||(tot+=flg,0);i++)
if((a[i]>>k)&1)flg=1,((a[i+1]>>k)&1)||(ans[++cnt]=std::make_pair(i+1,i),a[i+1]^=a[i]),
ans[++cnt]=std::make_pair(i,i+1),a[i]^=a[i+1];
printf("%d\n",cnt);for(i=1;i<=cnt;i++)printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
```