CSU 1216 異或最大值

CSU 1216 異或最大值

【題意】

給定序列q[1..n]，求任意兩數異或的最大值

數據范圍：1<=n<=10^5，q[i]為32位非負整數

【分析】Trie用來從高到低保存0和1，然後爆搜：盡可能湊1，不然湊0

【代碼】

WOC為什麼是多組數據？

#include 
#include 
#include 
using namespace std;

const int K=32;
const int L=3300000;

typedef long long LL;
int n,ret[K+10];
LL x,mi[K+10];
int nxt[L][2],tot;

inline void do_ret(LL i)
{
	for (int j=K;j+1;j--)
		i>=mi[j]?ret[j]=1,i-=mi[j]:ret[j]=0;
}

inline void ins(void)
{
	int now=1;
	for (int i=K;i+1;i--)
	{
		if (!nxt[now][ret[i]]) nxt[now][ret[i]]=++tot;
		now=nxt[now][ret[i]];
	}
}

inline LL max(LL i,LL j)
{
	return i>j?i:j;
}

LL DFS(int nn,int nx,int dep)
{
	LL res=0;
	if (nxt[nn][0]&&nxt[nx][1]) res=max(res,DFS(nxt[nn][0],nxt[nx][1],dep-1)+mi[dep]);
	if (nxt[nn][1]&&nxt[nx][0]) res=max(res,DFS(nxt[nn][1],nxt[nx][0],dep-1)+mi[dep]);
	if (res) return res;
	if (nxt[nn][0]&&nxt[nx][0]) res=max(res,DFS(nxt[nn][0],nxt[nx][0],dep-1));
	if (nxt[nn][1]&&nxt[nx][1]) res=max(res,DFS(nxt[nn][1],nxt[nx][1],dep-1));
	return res;
}

int main(void)
{	
	mi[0]=1;
	for (int i=1;i<=K;i++) mi[i]=mi[i-1]*2;
	
	for (;~scanf("%d",&n);)
	{
		memset(nxt,0,sizeof nxt);
		tot=1;
		
		for (int i=1;i<=n;i++)
		{
			scanf("%lld",&x);
			do_ret(x),ins();
		}
		printf("%lld\n",DFS(1,1,K));
	}
	
	return 0;
}

【小結】

(1) 對於位運算的問題，可以通過對於位的分析，常見維護的數據結構有Trie和線段樹

(2) 異或的性質：[1] i^j=k --> j^k=i 且 i^k=j [2] i^i=0,i^0=i --> 可以把前綴與後綴互相轉化，常見應用在可持久數據結構的查詢