以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 C/C++编程思想 』  (http://bbs.xml.org.cn/list.asp?boardid=61)
----  USACO COWXOR  (http://bbs.xml.org.cn/dispbbs.asp?boardid=61&rootid=&id=72390)

--  作者：卷积内核
--  发布时间：2/27/2009 2:32:00 PM

--  USACO COWXOR
之前一直看不懂网上的解答，而且找了半天没找到什么好懂的解法。。

昨天上网的时候看到有人说自己用trie把这题过掉了

于是上网学习trie这个东西

trie是字典树，每个结点有26个孩子，分别对应26个字母。
根到叶对应一个单词，节点上可以记录数据，搜索字符串的复杂度位O(n)，n是字符串长度

照着网上的样例code写了编，发现蛮简单的

然后回过头看这题

有一行数字，取中间连续子串，求出所有字串异或值中的最大值


首先，a[i]记录从1到i的异或值，则从 i 到 j 的异或值位a[j] xor a[i-1];枚举的话是O(n^2)的算法，100000的数据绝对不行。

问题的关键在对于每个a[j]，要于找到i使i到j的异或值最大。

异或最大，感性上认识就是，有差别的位数靠近高位，且越多越好。再看看这个字典树， 如果把26个字母改成0和1的孩子，这样可以形成一个21层的二叉树。从最高位找起，如果有和当前所在的位数相异的位数，就选那条路。 不行，再妥协选相同的位数。

要让这样的做法可行，要插入一个结点选一次（不能选自己之后的结点），且选完课才能把自己插进树里（不能选自己）

至于题目中的重复处理方法，只要在插入节点的时候遇到需要插入的结点已经有数据的情况就用覆盖数据就行了

--  作者：卷积内核
--  发布时间：2/27/2009 2:32:00 PM

--  
/*
PROG: cowxor
LANG: C++
*/
#include<stdio.h>
#define FOR(i,s,e) for(int i=s;i<e;i++)
#define SIZE 700000
#define BIT_AT(x,n) (((x) & (1<<n))>>n)
int a[100001],n;
struct Trie
{
int idx,value;
int sub[2];
}node[SIZE];
int root;
int node_alloc()
{
static int t=0;
node[t].idx=node[t].value=-1;
node[t].sub[0]=node[t].sub[1]=-1;
return t++;
}
void insert(int idx,int value)
{
if(root==-1) root=node_alloc();
int t,location=root;
for(int i=20;i>=0;i--)
{
t=BIT_AT(value,i);
if(node[location].sub[t]==-1)
node[location].sub[t]= node_alloc();
location=node[location].sub[t];
}
node[location].idx=idx;
node[location].value=value;
}
int find_max(int idx,int value)
{
int t,location=root;
for(int i=20;i>=0 && location!=-1 ;i--)
{
t= BIT_AT(value,i);
if(node[location].sub[(t+1)%2]!=-1)
location= node[location].sub[(t+1)%2];
else
location= node[location].sub[t];
}
return location;
}
int main()
{
freopen("cowxor.in","r",stdin);
freopen("cowxor.out","w",stdout);
a[0]=0;
root=-1;
insert(0,0);
scanf("%d",&n);
int t,max_i,max_j,max=-1;
FOR(i,1,n+1)
{
scanf("%d",&t);
a[i]=a[i-1]^t;
t=find_max(i,a[i]);
if(t!=-1 && (a[i]^node[t].value)>max)
{
max=(a[i]^node[t].value);
max_i=node[t].idx+1;
//printf("%d\n",t);
max_j=i;
}
insert(i,a[i]);
}
printf("%d %d %d\n",max,max_i,max_j);
//printf("%d ",node_alloc());
}
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 93.750ms