usaco 6.1 Cow XOR(USACO终结，二进制的一些应用)

Farmer John is stuck with another problem while feeding his cows. All of his N (1 ≤ N ≤ 100,000) cows (numbered 1..N) are lined up in front of the barn, sorted by their rank in their social hierarchy. Cow #1 has the highest rank; cow #N has the least rank. Every cow had additionally been assigned a non-unique integer number in the range 0..(2²¹ - 1).

Help FJ choose which cows will be fed first by selecting a sequence of consecutive cows in the line such that the bitwise "xor" between their assigned numbers has the maximum value. If there are several such sequences, choose the sequence for which its last cow has the highest rank. If there still is a tie, choose the shortest sequence.

TIME LIMIT: 0.5 sec

PROGRAM NAME: cowxor

INPUT FORMAT

• Line 1: A single integer N
• Lines 2..N+1: N integers ranging from 0 to 2²¹ - 1, representing the cows' assigned numbers. Line j describes cow of social hierarchy j-1.

SAMPLE INPUT (file cowxor.in)

5
1
0
5
4
2

INPUT DETAILS:

OUTPUT FORMAT

• Line 1: Three space-separated integers, respectively: the maximum requested value, the position where the sequence begins, the position where the sequence ends.

SAMPLE OUTPUT (file cowxor.out)

6 4 5

OUTPUT DETAILS:

题意：给你一个长度为n的数列，求一个连续的子数列，使得这个子数列所有数的异或值最大。。。

分析：首先可以想到的是暴力枚举每个子数列，然后统计答案，这样做肯定超时，所有有一个优化就是，利用异或的性质，假设

bit[i]= x[1]^x[2]^...^x[i]

那么，区间i~j的值就是 bit[i-1]^bit[j]

原题转换成找两个数，使得异或值最大。。。

那么我们可以枚举一个数，然后构造另一个数，使得当前答案最大

怎么构造呢，假设当前bit[i]=001010

那么从高位起，判断以1开头的bit是否存在，存在就该位就为1，不存在则为0

假设存在，就判断以11开头的bit是否存在，同上，存在就继续判断以110开头的。。。

现在就剩一个问题，如何判断i前面的bit的开头是否存在呢，很多题解都是用tire来保存的，其实用什么都一样，由于2进制比较特殊，直接可以用一个bool数组来保存状态是否存在，如 以11开头存在，就直接赋值为1，但是如果出现0000，和0是一样的，这样会出错，所有在11前面加个1，即11->111,00->100

代码：

/*
ID: 15114582
PROG: cowxor
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int bit[111111];
bool s[1<<22];
int i,j,k,tmp,n,ans,p;
void update(int x)
{
    for(int i=1,j=1<<21;i<22;++i,x>>=1,j>>=1)s[x|j]=1;
}
int main()
{
    freopen("cowxor.in","r",stdin);
    freopen("cowxor.out","w",stdout);
    while(~scanf("%d",&n))
    {
        for(bit[0]=0,i=1;i<=n;++i)
            scanf("%d",&bit[i]),bit[i]^=bit[i-1];
        memset(s,0,sizeof(s));
        update(0);
        ans=bit[p=1];
        for(i=1;i<=n;++i)
        {
            for(tmp=0,j=1;j<22;++j)
            {
                k=(bit[i]>>(21-j))&1;
                tmp<<=1;
                if(s[tmp|!k|1<<j])tmp|=!k;
                else tmp|=k;
            }
            tmp^=bit[i];
            if(tmp>ans)ans=tmp,p=i;
            update(bit[i]);
        }
        for(i=p;i>0;--i)
            if((bit[i-1]^bit[p])==ans)break;
        printf("%d %d %dn",ans,i,p);
    }
    return 0;
}

最后

以上就是动人仙人掌为你收集整理的usaco 6.1 Cow XOR(USACO终结，二进制的一些应用)的全部内容，希望文章能够帮你解决usaco 6.1 Cow XOR(USACO终结，二进制的一些应用)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。