「AGC035C」 Skolem XOR Tree

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

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

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

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

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

所以根据这一点对于偶数有非常方便的构造方式：\(n\rightarrow n-\operatorname{lowbit}(n) \rightarrow \operatorname{lowbit}(n)\rightarrow 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\n",exit(0);

	cout<<"Yes\n";

	int tmp=n-(n%2==0);

	if(tmp%4==1){

		cout<<tmp<<' '<<tmp-1<<'\n';

		cout<<tmp-1<<' '<<1<<'\n';

		cout<<1<<' '<<tmp+n<<'\n';

		cout<<tmp+n<<' '<<tmp+n-1<<'\n';

		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]<<'\n';

		cout<<n+(n&-n)+1<<' '<<n<<'\n';

		cout<<n-(n&-n)<<' '<<n*2<<'\n';

	}

	else{

		for(int i=1;i<2*tmp;++i) cout<<a[i]<<' '<<a[i+1]<<'\n';

	}

	return 0;

}

巴特西

「AGC035C」 Skolem XOR Tree

「AGC035C」 Skolem XOR Tree

最新文章

热门文章