题意:

在[0,2n)区间内任取一个数X,依次异或m个本区间内的数,并在某次异或之前或之后做一次f操作,即将当前的X循环左移(在n位的范围内)。求选择哪个数可以使在不同时候异或的答案的最小值最大。

分析:

首先,题目可以转化为:X异或这m个数中的前k个和循环右移1位后的(m-k)个数后的最小值最大。根据k的取值不同,我们可以得到(m+1)个不同的这样的异或方案。根据异或的交换律和结合律,这(m+1)个方案就相当于那m个数异或后的数与X异或。即$X\oplus A\oplus B\oplus C=X\oplus(A\oplus B\oplus C)$,所以我们将题目转化为:求{X与(m+1)个数中的某一个异或后结果的最小值}max

很自然地想到:策略1:如果X的某一位无论异或(m+1)个数中的哪一个,那一位都不变,我们就尽量让这一位异或之后为1。
我们继续分析:策略2:如果X的某一位异或不同的数,结果都不同,那么这时我们就需要使后续位异或结果尽量大(即尽量多遇到策略一)。
因此,这种只跟后续状态有关的问题,我们应该用DP解决,而0和1的状态分布又神似二叉树,所以我们可以尝试在trie树上DP

把那(m+1)个数放进trie树,较高位更靠近根节点,那么对于每一个X,我们都可以从trie数中找到一条路径使路径代表的值与X的异或值最小。比如X的最高位为1,而trie树的根节点有0和1两个子节点,那么我们的路径肯定会走向1这个子节点,从而获得更小的异或值。

那么如何求最小值的最大值呢?二分似乎是行不通的。结合开始分析时我们想到的两个策略,我们发现:

如果trie树的某个节点只有左子节点或右子节点,对应着策略1;两个节点都有的对应着策略2。在DP时我们就可以结合这两个策略,更新trie树每个节点对应应该选什么数字可以使往下的异或值最大。


#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>

#define MX 3000004
#define ls tre[node].s[0]
#define rs tre[node].s[1]

using namespace std;

typedef struct trrr
{
    int fa,s[2],x,ans,num,dep;
}trie;

trie tre[MX];
int n,m,a[MX],b[MX];
int fl[MX],fr[MX];
int nn;

int f(int x)
{
    return ((x<<1)%(1<<n)+(x<<1)/(1<<n));
}

void input()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
}

void insrt(int node,int len,int x,int fa)
{
    tre[node].fa=fa,tre[node].dep=len;
    if(len==-1)return;
    int nxp=!!(x&(1<<len));
    if(tre[node].s[0]&&nxp==0)tre[tre[node].s[0]].x=nxp,insrt(tre[node].s[0],len-1,x,node);
    else if(tre[node].s[1]&&nxp==1)tre[tre[node].s[1]].x=nxp,insrt(tre[node].s[1],len-1,x,node);
    else
    {
        tre[node].s[nxp]=++nn;
        tre[tre[node].s[nxp]].x=nxp;
        insrt(tre[node].s[nxp],len-1,x,node);
    }
}

void build()
{
    for(int i=1;i<=m;i++)fl[i]=fl[i-1]^a[i];
    for(int i=m;i>=1;i--)fr[i]=fr[i+1]^a[i];
    for(int i=0;i<=m;i++)b[i]=f(fl[i])^fr[i+1];
    for(int i=0;i<=m;i++)insrt(0,n-1,b[i],0);
}

void dfs(int node)
{
    if(ls)dfs(ls);
    if(rs)dfs(rs);
    if(tre[node].s[0]==0&&tre[node].s[1]==0)
    {
        tre[node].ans=0;
        tre[node].num=1;
    }
    else if(tre[node].s[0]==0&&tre[node].s[1])
    {
        tre[node].ans=tre[rs].ans|(1<<tre[node].dep);
        tre[node].num=tre[rs].num;
    }
    else if(tre[node].s[0]&&tre[node].s[1]==0)
    {
        tre[node].ans=tre[ls].ans|(1<<tre[node].dep);
        tre[node].num=tre[ls].num;
    }
    else
    {
        tre[node].ans=max(tre[tre[node].s[0]].ans,tre[tre[node].s[1]].ans);
        if(tre[ls].ans<tre[rs].ans)tre[node].num=tre[rs].num;
        else if(tre[ls].ans>tre[rs].ans)tre[node].num=tre[ls].num;
        else tre[node].num=tre[ls].num+tre[rs].num;
    }
}

int main()
{
    freopen("big.in","r",stdin);
    freopen("big.out","w",stdout);
    input();
    build();
    dfs(0);
    cout<<(tre[0].ans)<<endl<<(tre[0].num)<<endl;
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *