程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> CSU 1216 異或最大值

CSU 1216 異或最大值

編輯:關於C++

【題意】

給定序列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 --> 可以把前綴與後綴互相轉化,常見應用在可持久數據結構的查詢

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved