CF282 E Sausage Maximization[trie樹]

CF282 E Sausage Maximization[trie樹]

給n個數

求異或前綴（從前連續取一些數全作異或）和異或後綴（從後連續取一些數全作異或）異或的最大值

好坑啊，指針好坑啊

第一道trie樹

簡單說下解法（其實殼還是不深）：

先異或所有數作為初始後綴

然後從前往後的數逐個從後綴出來，進入前綴，

在這個過程中，都把當前前綴變成二進制壓入trie，然後當前後綴變成二進制從高位到低位盡量取和它數位不同的值，沿著trie往下走，得到一個最好的數，然後和後綴異或，維護最大值

簡直了，指針就是坑

其實還是自己有點坑

說下遇到的坑吧

一開始沒有全存64位數（導致可能一個長為30的後綴匹配出來的”最優“前綴長度為6什麼的）

然後，我判斷每個數位的時候是這樣的 num&(1<>i)&1

還有，應該是把prefix壓入trie，我卻把number[i]壓入trie

還有就是。。。1<<55是錯的，應該是1LL<<55

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAX 5
typedef struct Trie   {
	Trie *next[MAX];
	long long v;   //根據需要變化
};
Trie root;
void createTrie(char *str) {
	long long len = strlen(str);
	Trie *p = &root, *q;
	for(long long i=0; inext[id] == NULL) {
			q = (Trie *)malloc(sizeof(Trie));
			q->v = 1;    //初始v==1
			for(long long j=0; jnext[j] = NULL;
			p->next[id] = q;
			p = p->next[id];
		} else {
			p->next[id]->v++;
			p = p->next[id];
		}
	}
	p->v = -1;   //若為結尾，則將v改成-1表示
}
long long findTrie(char *str) {
	long long len = strlen(str);
	Trie *p = &root;
	for(long long i=0; inext[id];
		if(p == NULL)   //若為空集，表示不存以此為前綴的串
			return 0;
		if(p->v == -1)   //字符集中已有串是此串的前綴
			return -1;
	}
	return -1;   //此串是字符集中某串的前綴
}
long long dealTrie(Trie* T,bool isroot) {
	long long i;
	if(T==NULL)
		return 0;
	for(i=0;inext[i]!=NULL)
			dealTrie(T->next[i],false);
	}
	if(!isroot) free(T);
	return 0;
}
const long long NN=111111;
long long f[NN];
#define SAVE 62
void get_bina(long long s,char* to){
	long long que=0;
	for(long long i=SAVE;i>=0;i--){
		to[que++]=((s>>i)&1)+'0';//應該是 (s>>i)&1
	}
	to[que]='\0';
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("/home/rainto96/in.txt","r",stdin);
#endif
	long long n;cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>f[i];
	}
	long long prefix=0,postfix=0,ans=0;
	for(long long i=1;i<=n;i++) postfix^=f[i];//初始後綴
	ans=postfix;//ans初始就是取所有後綴
	for(long long i=1;i<=n;i++){
		postfix^=f[i];
		prefix^=f[i];
		char tmp[99];
		get_bina(prefix,tmp);//把當前前綴變成二進制
		createTrie(tmp);//把當前前綴壓入trie
		get_bina(postfix,tmp);//把當前後綴編程二進制


		Trie* p =&root;
		long long len=strlen(tmp);
		long long get_num=0;
		ans=max(ans,postfix);//不取前綴
		for(long long i=0;i<=SAVE;i++){//逐個取
			long long want = 1 - (tmp[i]-'0');//最優匹配
			if(p->next[want]==NULL){//如果沒有最優匹配的
				if(p->next[1-want]==NULL){//如果都沒有，就是到了結尾
					ans=max(ans,get_num^postfix);
					break;
				}else{//有不優匹配
					p=p->next[1-want];
					get_num=get_num*2+1-want;
				}
			}else{//有最優匹配
				p=p->next[want];
				get_num=get_num*2+want;
			}
		}
		ans=max(ans,get_num^postfix);
	}
	cout<