题解 P4098 【[HEOI2013]ALO 】

· · 个人记录

由于这题数据可能过水，所以就暴力过了，正解好像是可持久化trie？

暴力就假定a[i]是第二大的，从i向左扫，记录一下能异或出来的最大值，同时记着有没有比它更大的数，有一次就记下来，有两次就跳出，向右边做一个一样的操作。

出来后看一下如果找到过比a[i]大的数就可以尝试更新答案，如果没有说明a[i]是最大的不能用。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>
#include<set>

#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memcpy((a),(b),sizeof((b)))
#define D double

using namespace std;

const int N=50005;

int n,a[N],ans;

IL int read() {
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
    return x*f;
}
IL void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

signed main()
{
    n=read();
    Rf(i,1,n) a[i]=read();
    Rf(i,1,n) {
        R int s=0,fl=0;//s记录一次统计的最大值，fl表示有没有比a[i]大的
        Tf(j,i-1,1) {//向左扫
            if(a[j]>a[i]) {
                if(!fl) fl=1;//第一次出现比a[i]大的
                else break;//第二次出现比a[i]大的
            }
            s=max(s,a[i]^a[j]);
        }
        if(fl) ans=max(s,ans);//如果有比a[i]大的才能更新答案
        s=0,fl=0;
        Rf(j,i+1,n) {//向右扫，同上
            if(a[j]>a[i]) {
                if(!fl) fl=1;
                else break;
            }
            s=max(s,a[i]^a[j]);
        }
        if(fl) ans=max(s,ans);
    }
    write(ans);

    return 0;
}