题解：CF1163E Magical Permutation

很少在 duel 的时候遇到惊艳我的 2400 了。正好把我不熟的整合了一下。

首先假设我们 $S$ 可以自己定，如果要满足 $0\sim 2^x-1$ 的， $|S|$ 最小是多少？

|S| 最小是

x

。考虑

S=\{0,1,2,\cdots ,2^{x-1}\}

。然后我们

0,1,3,2,\cdots

构造序列。容易证明

|S|

不可能更小。

一点要注意的是，

0,1,3,2,\cdots

是格雷码。

给定 $S$ ，怎么判断一个 $x$ 合不合法？

其实也就是

S

中的集合能不能表示所有

0\sim 2^x-1

，并且不重不漏。

一个显然的条件是

S

中有用的数插入线性基中，线性基大小

=x

。

然后发现这个是冲要条件：

首先，所有 $0\sim 2^x-1$ 可以用线性基中若干个数 $\oplus$ 得到。
其次，根据线性基的定义：没有两个子集异或相等，所以 $0\sim 2^x-1$ 的数都可以以唯一方式表示出来。定义这个数的编号为：一个二进制串，每一位表示选不选这个线性基中的数。
因为有 $2^x$ 个数，而线性基最多能表示 $2^x$ 个数，所以数和编号是双射关系。
因为是不重不漏的 $000,001,010,011,\cdots$ ，所以可以构成一个格雷码。

那么构造也简单了：可以直接暴力搜索，一定有答案。

CPP

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 4e5+5;

int n,a[N],b[20],c[20],cnt,mx;

void ins(ll x){
	ll y=x;
	for (int i=19; i>=0; i--){
		if (x>>i&1){
			if (!b[i]){
				b[i]=x;
				c[i]=y;
				cnt++;
				return;
			}
			else{
				x^=b[i];
			}
		} 
	} 
}

int vis[N];

void dfs(int u){
	cout<<u<<" ";
	vis[u]=1;
	for (int i=0; i<mx; i++){
		if (!vis[c[i]^u]){
			dfs(c[i]^u);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>a[i];
	}
	for (int i=19; i>=0; i--){
		cnt=0;
		for (int j=0; j<20; j++) b[j]=c[j]=0;
		for (int j=1; j<=n; j++){
			if (a[j]<=(1<<i)-1){
				ins(a[j]);
			}
		}
		if (cnt==i){
			mx=i;
			cout<<i<<"\n";
			dfs(0);
			return 0;
		}
	}
	return 0;
}

题解：CF1163E Magical Permutation

文章操作

相关推荐

评论

题解：CF1163E Magical Permutation