「LOJ#10051」「一本通 2.3 例 3」Nikitosh 和异或（Trie

题目描述

原题来自：CODECHEF September Challenge 2015 REBXOR

1≤r1<l2≤r2≤N，x⨁yx\bigoplus yx⨁y 表示 xxx 和 yyy 的按位异或。

输入格式

输出格式

输出一行包含给定表达式可能的最大值。

样例

数据范围与提示

5,0≤Ai≤109。

题解

首先记录异或前缀和$s[i]=a[1]⊕a[2]⊕a[3] ...⊕a[i]$。

设$l[i]$为以$i$结尾的区间中，异或值的最大值。

因为异或有 $x⊕x=0$ 的性质，所以区间 $[l,r]$ 的异或值

$=a[l]⊕a[l+1]⊕...⊕a[r]$

$=(a[1]⊕a[2]⊕a[3]...⊕a[l-1])⊕(a[1]⊕a[2]⊕a[3] ...⊕a[r])$

$=s[l-1]⊕s[r]$，

所以求$l[i]$，转化为找$j<i$，使得$s[j]⊕s[i]$最大。

转化为「LOJ#10050」「一本通 2.3 例 2」The XOR Largest Pair（Trie

以相似的方法可以求出$r[i]$（以$i$开头的区间中，异或值的最大值）。

在实际操作的过程中可以$l[i]=max(l[i-1],find(x))$，这样$ans=max(l[i]+r[i+1])$就行了。

书上的操作是直接$l[i]=find(x)$然后$ans=max(l[i]+r[i+1])$，感觉不能理解qwq

 编号     题目     状态     分数     总时间     内存     代码 / 答案文件     提交者     提交时间

 #     #. 「一本通 2.3 例 」Nikitosh 和异或    Accepted           ms      KiB     C++ / 1.2 K     qwerta     -- ::

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 int s[];

 int l[];

 int r[];

 struct emm{

     int nxt[];

 }a[];

 int cnt=;

 int b[];

 void add(int x)

 {

     int j=-;

     memset(b,,sizeof(b));

     while(x)

     {

         b[++j]=x&;

         x>>=;

     }

     int k=;

     for(int j=;j>=;--j)

     {

         if(!a[k].nxt[b[j]])

           a[k].nxt[b[j]]=++cnt;

         k=a[k].nxt[b[j]];

     }

     return;

 }

 int find(int x)

 {

     int now=,k=;

     for(int j=;j>=;--j)

     {

         if(a[k].nxt[-b[j]])

         {

             now+=(<<j);

             k=a[k].nxt[-b[j]];

         }

         else k=a[k].nxt[b[j]];

     }

     return now;

 }

 int main()

 {

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

     int n;

     scanf("%d",&n);

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

       scanf("%d",&s[i]);

     int x=;

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

     {

         x^=s[i];//这里的x为前缀和

         add(x);

         l[i]=max(l[i-],find(x));

     }

     //重做一次找r[i]

     memset(a,,cnt+);

     x=,cnt=;

     for(int i=n;i;--i)

     {

         x^=s[i];

         add(x);

         r[i]=max(r[i+],find(x));

     }

     int ans=;

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

     ans=max(ans,l[i]+r[i+]);

     cout<<ans;

     return ;

 }

巴特西

「LOJ#10051」「一本通 2.3 例 3」Nikitosh 和异或（Trie

题目描述

输入格式

输出格式

样例

数据范围与提示

题解

最新文章

热门文章