[1525] Cow Xor

问题描述
农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在0..2^21 - 1的范围内。

帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。

如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。
输入
第1行:一个单独的整数N。
第2到N + 1行:N个0..2^21 - 1之间的整数，代表每头奶牛的被赋予的数。第j行描述了社会等级j - 1的奶牛。
输出
第 1 行: 3个空格隔开的整数，分别为：最大的异或值，序列的起始位置、终止位置
样例输入
```
5

1

0

5

4

2
```
样例输出
```
6 4 5
```
提示

最大异或值为6，从第4个开始喂，到第5个结束。

4 异或 2 = 6

(100) 异或 (010) = (110)

来源
```
USACO (NOCOW)
```

大概思路就是利用异或和的性质

维护一个前缀，找两个前缀异或值最大的就行了。

比如 sum[5]^sum[2] 的值就是 a[3]^a[4]^a[5]的值

可是为什么我在这里提交就能过https://ac.2333.moe/Problem/view.xhtml?id=1525

而在这里提交 http://42.247.7.121/zh/Problem/Details/1873 死活过不了第二组数据....

/* ***********************************************

Author        :guanjun

Created Time  :2016/10/6 12:31:51

File Name     :nk1873.cpp

************************************************ */

//#include <bits/stdc++.h>

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <cmath>

#include <algorithm>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 100010

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

bool cmp(int a,int b){

    return a>b;

}

int sum[maxn];

struct node{

    int next[];

    int v;

    void init(){

        v=;

        memset(next,-,sizeof next);

    }

};

node L[maxn*];

int tot=;

int Max,be,ge;

char s[];

void add(char s[],int len,int num){

    int now=;

    for(int i=;i<len;i++){

        int t=s[i]-'';

         int next=L[now].next[t];

         if(next==-){

             next=++tot;

             L[next].init();

             L[now].next[t]=next;

         }

         now=next;

         L[now].v=num;

    }

    L[now].v=num;

}

void query(char s[],int len,int num){

    int now=;

    int ans=;

    for(int i=;i<len;i++){

        int t=s[i]-'';

        int next=L[now].next[-t];

        if(next==-||L[now].v==){

            next=L[now].next[t];

        }

        else{

            ans+=pow(2.0,-i-);

        }

        now=next;

    }

    //cout<<"ans "<<ans<<endl;

    if(ans>Max){

        Max=ans;

        be=L[now].v+;

        ge=num;

    }

}

void cha(int x,char *s){

    for(int i=;i<=;i++){

        s[i]=x%+'';

        x/=;

    }

    s[]='\0';

}

int main()

{

   //#ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

   //#endif

    //freopen("out.txt","w",stdout);

    int n,x;

    while(cin>>n){

        L[].init();

        sum[]=;

        for(int i=;i<=n;i++){

            scanf("%d",&x);

            sum[i]=sum[i-]^x;

        }

        Max=sum[];

        cha(sum[],s);

        reverse(s,s+);

        add(s,,);

        for(int i=;i<=n;i++){

            cha(sum[i],s);

            reverse(s,s+);

            query(s,,i);

            add(s,,i);

        }

        printf("%d %d %d\n",Max,be,ge);

    }

    return ;

}

巴特西

[1525] Cow Xor

最新文章

热门文章