big 题解【异或】【字典树】【构造】

作者: wjyyy 分类: 与或异或,二进制,字典树,数据结构,构造,解题报告 发布时间: 2018-10-17 19:29

点击量:26

 

    最重要的部分是理解题目中给的式子。

题目描述

你需要在\([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\)分。

输入输出样例

输入样例#1:

2 3
1 2 3
输出样例#1:

1
2

说明

样例解释:

\(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\)。

题解:

    这个题看上去比较难,而且式子很麻烦。实际上这个式子是在将\(x\)左移一位,如果原来最高位是\(1\),那么移动后的最低位补为\(1\)。

    这样这个题的过程就是,你给出一个数\(x\),你的对手在这个数异或\(\bigoplus\limits_{i=1}^{k}a_i\)的异或和后,将所得结果左移一位得到\(x’\),接着将\(x’\)异或\(\bigoplus\limits_{i=k+1}^{m}a_i\)。而可以发现,前面两个操作可以等价于\(x\)先左移一位再依次异或\(a_i\times 2\ (1\le i\le k)\)(左移一位),\(k+1\)以后的就直接异或原数。这样我们有\(m+1\)个\(k\),而异或是有结合律的,因此可以把每种状态后面所有的\(a_i\)都看作是一个数\(b_i\)。比如当\(k=3\)时,\(b_i=2a_1\bigoplus 2a_2\bigoplus 2a_3\bigoplus a_4\bigoplus \dots \bigoplus a_m\)。

    此时题目转化为,求\(x\)使得\(\min\limits_{i=0}^m x\bigoplus b_i\)最大。此时认为,如果对于任意\(i\in[0,m]\),都有\(b_i\)的第\(k\)位相等,那么就一定可以构造出\(x\)使它与任意\(b_i\)异或在这一位上都为\(1\),即当\(b_i\)的第\(k\)位均为\(0\)时,让\(x\)的第\(k\)位为\(1\)即可,反之亦可。如果\(b_i\)的第\(k\)位既有\(0\)又有\(1\),说明这一位会被对手抢走。

    又因为我们要找出最大的异或答案,那么我们找出尽可能高的这种二进制位。既然我们可以利用\(a_i\)的前缀后缀和求出上面任何一个\(b_i\),然后把它插入字典树中。然后dfs这棵字典树,如果一个节点拥有两个儿子,就对应上面说明这里无论选\(0\)还是\(1\),对手都会让你变成\(0\),同时dfs两个儿子,继续统计;如果只有一个儿子,“你”就可以选择另一个儿子代表的数字,为答案做出\(n-dep\)的贡献,这里的\(dep\)是字典树节点的深度。最终统计答案就和一般的计数一样就可以了。

    又是一个异或计数的好题公式误导人类啊……

Code:

#include<cstdio>
#include<cstring>
struct node
{
    node *ls,*rs;
    node()
    {
        ls=NULL;
        rs=NULL;
    }
}*root=new node();
void Insert(node *rt,int x,int d)
{
    if(d==-1)
        return;
    if((x>>d)&1)
    {
        if(!rt->rs)
            rt->rs=new node();
        Insert(rt->rs,x,d-1);
    }
    else
    {
        if(!rt->ls)
            rt->ls=new node();
        Insert(rt->ls,x,d-1);
    }
}
int a[100100];
int sum[100100],mus[100100];
int mx=0,cnt=0,now=0;
void dfs(node *rt,int d)
{
    if(d==-1)
    {
        if(now==mx)
            ++cnt;
        if(now>mx)
        {
            mx=now;
            cnt=1;
        }
        return;
    }
    if(rt->ls&&rt->rs)
    {
        dfs(rt->ls,d-1);
        dfs(rt->rs,d-1);
    }
    else
    {
        now|=(1<<d);
        rt->ls?dfs(rt->ls,d-1):dfs(rt->rs,d-1);
        now^=(1<<d);
    }

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)
        sum[i]=sum[i-1]^(((1<<n)-1)&(a[i]<<1)|(a[i]>>(n-1)));//前缀异或和 表示前面都左移
    for(int i=m;i>=0;--i)
        mus[i]=mus[i+1]^a[i+1];//直接后缀异或和
    for(int i=0;i<=m;++i)
        Insert(root,sum[i]^mus[i],n-1);
    dfs(root,n-1);
    printf("%d\n%d\n",mx,cnt);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */