自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 22:29:09，当前版本为作者最后更新于2021-04-01 15:45:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

给定一个长为 $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=1$，严格单调递增序列，即 $A_i<A_{i+1}$。（$n\leq200$，保证所有 $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$ 次，刚好足以通过本题。

那么本题思路就讲完了，以下是压行代码：

#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;
}