big

题目描述

你需要在\([0,2^n)\)中选一个整数\(x\)，接着把\(x\)依次异或\(m\)个整数\(a_1\sim a_m\)。

在你选出\(x\)后，你的对手需要选择恰好一个时刻（刚选完数时、异或一些数后或是最后），将\(x\)变为\((\lfloor\frac {2x}{2^n}\rfloor+2x)\pmod {2^n}\)。

你想使\(x\)最后尽量大，而你的对手会使\(x\)最后尽量小。

你需要求出\(x\)最后的最大值，以及得到最大值的初值数量。

输入格式

第一行两个整数\(n,m\)。第二行\(m\)个整数\(a_1\sim a_m\)。

输出格式

第一行输出一个整数，表示\(x\)最后的最大值。

第二行输出一个整数，表示得到最大值的初值数量。

第一个数正确得\(6\)分，两个数都正确再得\(4\)分。

说明

\(x=0\)时得到\(0\)，\(x=1\)时得到\(1\)，\(x=2\)时得到\(1\)，\(x=3\)时得到\(0\)。

数据范围

对于\(20\%\)的数据，\(n\le 10,m\le 100\)。

对于\(40\%\)的数据，\(n\le 10, m\le 1000\)。

对于另外\(20\%\)的数据，\(n\le 30,m\le 10\)。

对于\(100\%\)的数据\(n\le 30,m\le 100000,\ 0\le a_i<2^n\)。

挺不错的题目。

考虑操作的特殊性，发现操作把序列左移了一位，并且超出的高位在低位进行了补全。

每一位只是位置换了，而值没换，而异或又是按位的，所以在第\(i\)次操作后左移等价于在第一次操作前进行左移，然后把前\(i\)次操作都左移。

这样的话，操作集合实质上只有\(m+1\)种了

我们可以把操作放到字典树上走。

注意\(A\)和\(B\)的目的。

Code:

#include <cstdio>

#define ll long long

const int N=1e5+10;

int n,m;

ll a[N];

ll change(ll s)

{

    return ((s<<1)/(1ll<<n)+(s<<1))%(1ll<<n);

}

int ch[N*30][2],tot;

void build(ll s)

{

    int now=0;

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

    {

        int t=s>>i-1&1;

        if(!ch[now][t]) ch[now][t]=++tot;

        now=ch[now][t];

    }

}

ll ans=0;int cnt;

void dfs(int now,int dep,ll sum)

{

    if(dep==n)

    {

        if(sum>ans) ans=sum,cnt=1;

        else if(sum==ans) ++cnt;

        return;

    }

    if(ch[now][0]&&ch[now][1])

    {

        dfs(ch[now][0],dep+1,sum);

        dfs(ch[now][1],dep+1,sum);

    }

    else if(ch[now][0])

        dfs(ch[now][0],dep+1,sum|(1ll<<n-dep-1));

    else if(ch[now][1])

        dfs(ch[now][1],dep+1,sum|(1ll<<n-dep-1));

}

int main()

{

    scanf("%d%d",&n,&m);

    ll lf=0,rf=0;

    for(int i=1;i<=m;i++)

        scanf("%lld",a+i),rf^=a[i];

    for(int i=0;i<=m;i++)

    {

        lf^=change(a[i]);

        rf^=a[i];

        build(lf^rf);

    }

    dfs(0,0,0);

    printf("%lld\n%d\n",ans,cnt);

    return 0;

}

2018.10.17

巴特西

big 解题报告

big

题目描述

输入格式

输出格式

说明

数据范围

最新文章

热门文章