「雅礼day3」整数big - trie树+贪心

题目大意

---

题目分析

不难发现题目的变化就是将$x$左移一位，或者左移一位在末尾补$1$。
那么我们将$x$和$1$~$i$所有数异或起来再执行操作与先将$x$执行操作然后对$1$~$i$所有执行完操作的数异或起来没有区别。

根据这个性质，我们可以将所有未确定$x$的方案全部初始化出来。

现在我们的任务是，已有若干个数，要求选出一个数异或其中任意一个数后最大值最小。

这不正好是trie树所解决的问题吗？将所有方案按照二进制建成trie树，考虑遍历trie树，问题转化为选出一条路径使得按位异或的值最大，但是对手会在trie树遍历过程中尽可能阻止你选到最大值。

考虑贪心的思路，当前遍历到trie树的$u$结点，若$u$拥有两个儿子，说明此时选择会有两种方案，无论哪种方案最优，对手都可以强制使你无法选到最优值，因此此刻无法更新答案，若$u$仅有一个儿子，说明此时选择仅有一种方案，一旦选择对手无法阻止该选择，只需选择与该位相反的数即可，更新答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=100005;
int n,m,sum1[maxn],sum2[maxn],ans=0,ans2=0;
struct Trie {
	int root,cnt,ch[maxn*25][2];
	Trie() {
		cnt=0;
		root=++cnt;
	}
	void insert(int x) {
		int now=root;
		for(int i=n-1; i>=0; i--) {
			int v=(x>>i)&1;
			if(!ch[now][v])ch[now][v]=++cnt;
			now=ch[now][v];
		}
	}
	void dfs(int now,int depth,int sum) {
		if(depth<0) {
			if(sum==ans)ans2++;
			else if(sum>ans) {
				ans=sum;
				ans2=1;
			}
			return;
		}
		if(ch[now][0]&&ch[now][1]) {
			dfs(ch[now][0],depth-1,sum);
			dfs(ch[now][1],depth-1,sum);
		} else if(ch[now][0])dfs(ch[now][0],depth-1,sum^(1<<depth));
		else if(ch[now][1])dfs(ch[now][1],depth-1,sum^(1<<depth));
	}
} trie;
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int();
		sum1[i]=sum1[i-1]^x;
		sum2[i]=sum2[i-1]^(((x>>(n-1))+(x<<1))%(1<<n));
	}
	for(int i=0; i<=m; i++)trie.insert(sum2[i]^sum1[m]^sum1[i]);
	trie.dfs(1,n-1,0);
	printf("%d\n%d\n",ans,ans2);
	return 0;
}