题目:

 分析:

考虑最暴力的办法:枚举选哪个数,枚举对手在哪个时间变化,然后统计答案。

对于异或这一类问题,考虑区间异或可以抵消重复区间,维护一个前缀异或和:pre[i]表示1~i的异或和,suf[i]表示i~n的异或和。

将对手的式子化简,2*x即将x向左移一位,/( 2^n )为向右移n位,+2*x ,%2^n类似。

模拟一下:12345 -> 123450 -> 123451 -> 23451 

每次枚举对手要变的时间i,最后的值即为:work ( pre[i] ^ x ) ^ suf[i+1]    (work是按照上述式子的转换)

枚举x的复杂度太高,其实可以先将 work(pre[i])^ suf [i+1] 预处理出来,用trie树贪心求x。

为什么是对的?

原式转换成:work( pre[i]  )^ suf[i+1]  ^ work( x )  其实就是将前半部分放入trie树,贪心求后半部分的最大值。

注意:trie储存的是对手可以翻转的值 ,如果对手只有1(或只有0), 那么我们可以选择相反的 ,获得这一位的1 ,否则对手两个都有,对手会选择最优策略 ,我们不会收获 。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define ri register int
int pre[N],go[N*30][3],suf[N],x[N],ans=0,num=0,a[N],n,ndnum=0;
int calc(int y)
{
    return ( y*2/(1<<n) + 2*y ) % (1<<n);
}
void add(int y)
{
    int now=0;
    for(ri i=n-1;i>=0;--i){
        int xx=(y>>i)&1;
        if(!go[now][xx]) go[now][xx]=++ndnum;
        now=go[now][xx];
    }
}
void dfs(int now,int dep,int maxn)
{
    if(dep==0){
        if(maxn==ans) num++;
        else if(maxn>ans) ans=maxn,num=1;
        return ;
    }
    //如果对手只有1 那么我们可以选择相反的 获得这一位的1 
    if(!go[now][0]) dfs(go[now][1],dep-1,maxn^(1<<(dep-1)));//dep-1是因为二进制是从0开始的 而这里dep从1开始 
    else if(!go[now][1]) dfs(go[now][0],dep-1,maxn^(1<<(dep-1)));
    else{//如果对手两个都有 对手会选择最优策略 我们不会收获 
        dfs(go[now][1],dep-1,maxn);
        dfs(go[now][0],dep-1,maxn);
    }
}
int main()
{
    freopen("big.in","r",stdin);
    freopen("big.out","w",stdout);
    int m;
    scanf("%d%d",&n,&m);
    for(ri i=1;i<=m;++i) scanf("%d",&a[i]),pre[i]=pre[i-1]^a[i];
    for(ri i=m;i>=1;--i) suf[i]=suf[i+1]^a[i];
    for(ri i=0;i<=m;++i) x[i]=calc(pre[i])^suf[i+1],add(x[i]);//trie储存的是对手可以翻转的值 
    dfs(0,n,0);
    printf("%d\n%d\n",ans,num);
}
/*
3
2 3
*/
View Code
01-22 14:34