自动搬运

查看原文

来自洛谷，原作者为

	zibenlun 我是可爱zibenlun

搬运于2025-08-24 22:49:55，当前版本为作者最后更新于2023-08-28 20:06:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

骗分还得是模拟退火

思路

了解了模拟退火算法后，本题几乎成为了一道板子题，但是还有一些细节需要去解决一下。

模拟退火算法本来是用来求最值的，所以对于本题来说其中退火的环节确实有点多余，所以我们为了本人更好地偷懒解法的正确性，我们要舍去多余的退火。

舍去了退火之后会发现，如何解决是否交换的问题呢？其实只需要全部交换就可以了，因为异或这种运算没什么太大的规律。

之后是我们总体的思路，首先预处理一下要用的 $lg$ 数组，然后对于每一个 $n$ 准备好的原数组和它的前 $m$ 个异或和，还有要比较的数。之后跑模拟退火直到出结果或者无解就好了。

更多的代码细节还是直接看代码吧。

Code

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s;
}
inline void write(long long x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int flag=0,lg[1000005];
int a[1000005],n,m,t,pos=1,sum;
void SA(){
	for(int i=1;i<=10000;i++){
		int l=rand()%m+1,r=m+rand()%(n-m)+1;
		sum^=a[l];
		sum^=a[r];
		swap(a[l],a[r]);
		if(sum==pos){
			flag=1;
			return ;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin>>t;
	for(int i=1;i<=1000000;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	while(t--){
		cin>>n>>m;
		if(n==m){
			for(int i=1;i<=n;i++) a[i]=i;
			flag=sum=0;
			for(int i=1;i<=m;i++) sum^=i;
			pos=1;
			for(int i=1;i<=lg[n];i++) pos*=2;
			pos--;
			if(sum==pos) {
				for(int i=1;i<=n;i++) cout<<i<<" ";
				cout<<"\n";
				continue;
			}
			else {
				cout<<"-1\n";
				continue;
			}
		}
		for(int i=1;i<=n;i++) a[i]=i;
		flag=sum=0;
		for(int i=1;i<=m;i++) sum^=i;
		pos=1;
		for(int i=1;i<=lg[n];i++) pos*=2;
		pos--;
		for(int i=1;i<=90;i++){
			SA();
			if(flag){
				for(int j=1;j<=m;j++){
					cout<<a[j]<<" ";
				}
				cout<<"\n";
				break;
			}
		}
		if(!flag){
			cout<<"-1\n";
		}			
	}
	return 0;
}

温馨提示

本代码不一定可以一遍过，如果答案错误的话，多提交几遍就可以了。