「AGC035C」 Skolem XOR Tree

「AGC035C」 Skolem XOR Tree

感觉有那么一点点上道了？

首先对于一个 (n)，若 (nequiv 3 pmod 4)，我们很快能够构造出一个合法解如 (n,n-1,n-2,..,1,n+n,n+n-1,n+n-2,...,n+1)。

若 (nequiv 1 pmod 4),我们将 (n,n-1) 拆分出来单独成一条链。

然后如果 (n) 是偶数，可以想到对于这个 (n) 单独处理，则剩下的问题转化为我们上面的问题。

考虑对于这个偶数特殊判断，可以想到两个偶数之间的数的异或和应该等于这个偶数，所以若 (operatorname{lowbit}(n)=n) 则无解，因为中间的数都比 (n) 小，且二进制下这一位均为 (0)，不可能异或出 (n)。

所以根据这一点对于偶数有非常方便的构造方式：(n ightarrow n-operatorname{lowbit}(n) ightarrow operatorname{lowbit}(n) ightarrow n)。

似乎根据这个性质再对 (2) 的次幂特判就已经做完了

然后这个题就做完了。

/*---Author:HenryHuang---*/
/*---Never Settle---*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;cin>>n;
	if((n&-n)==n) cout<<"No
",exit(0);
	cout<<"Yes
";
	int tmp=n-(n%2==0);
	if(tmp%4==1){
		cout<<tmp<<' '<<tmp-1<<'
';
		cout<<tmp-1<<' '<<1<<'
';
		cout<<1<<' '<<tmp+n<<'
';
		cout<<tmp+n<<' '<<tmp+n-1<<'
';
		tmp-=2;
	}
	for(int i=1;i<=tmp;++i) a[i]=tmp-i+1,a[i+tmp]=n+tmp-i+1;
	if(n!=tmp&&n%2==0){
		for(int i=1;i<2*tmp;++i) cout<<a[i]<<' '<<a[i+1]<<'
';
		cout<<n+(n&-n)+1<<' '<<n<<'
';
		cout<<n-(n&-n)<<' '<<n*2<<'
';
	}
	else{
		for(int i=1;i<2*tmp;++i) cout<<a[i]<<' '<<a[i+1]<<'
';
	}
	return 0;
}