CF282 E Sausage Maximization[trie树]

给n个数

求异或前缀（从前连续取一些数全作异或）和异或后缀（从后连续取一些数全作异或）异或的最大值

好坑啊，指针好坑啊

第一道trie树

简单说下解法（其实壳还是不深）：

先异或所有数作为初始后缀

然后从前往后的数逐个从后缀出来，进入前缀，

在这个过程中，都把当前前缀变成二进制压入trie，然后当前后缀变成二进制从高位到低位尽量取和它数位不同的值，沿着trie往下走，得到一个最好的数，然后和后缀异或，维护最大值

简直了，指针就是坑

其实还是自己有点坑

说下遇到的坑吧

一开始没有全存64位数（导致可能一个长为30的后缀匹配出来的”最优“前缀长度为6什么的）

然后，我判断每个数位的时候是这样的    num&(1<<i)，，，显然错了，应该是(num>>i)&1

还有，应该是把prefix压入trie，我却把number[i]压入trie

还有就是。。。1<<55是错的，应该是1LL<<55

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
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; i<len; ++i) {
		long long id = str[i]-'0';//这里按需求改
		if(p->next[id] == NULL) {
			q = (Trie *)malloc(sizeof(Trie));
			q->v = 1;    //初始v==1
			for(long long j=0; j<MAX; ++j)
				q->next[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; i<len; ++i) {
		long long id = str[i]-'0';//这里按需求改
		p = p->next[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;i<MAX;i++) {
		if(T->next[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<<ans<<endl;
	//dealTrie(&root,true);
	return 0;
}