NOJ2026:Keroro侵略地球(01字典树)

传送门

题意

略

分析

将n个数插入字典树中，m次查询，取最大值，复杂度\(O(mlogn)\)

trick

1.注意题目给的空间，开40刚刚够（62852K）

2.作为01字典树的模板保存了

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

//#pragma comment(linker, "/STACK:102400000,102400000")

//inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

const int maxn = 1e5+10;//集合中的数字个数

int ch[40*maxn][2];//节点的边信息

//int num[40*maxn];//记录节点的使用次数，删除时要用

ll val[40*maxn];//节点存储的值

int cnt;//树中节点的个数

inline void init()

{

    cnt=1;mem(ch[0],0);//清空树

}

void insert(ll x)//在字典树中插入x，和一般字典树操作相同，将x化成二进制插入到字典树

{

    int cur=0;

    for(int i=40;i>=0;--i)

    {

        int idx=(x>>i)&1;

        if(!ch[cur][idx])

        {

            mem(ch[cnt],0);

            ch[cur][idx]=cnt;

            //num[cnt]=0;

            val[cnt++]=0;

        }

        //printf("ch[%d][%d]=%d\n",cur,idx,ch[cur][idx]);

        cur=ch[cur][idx];

        //num[cur]++;

    }

    val[cur]=x;//最后节点插入val

}

void update(ll x,int c)

{

    int cur=0;

    for(int i=40;i>=0;--i)

    {

        int idx=(x>>i)&1;

        cur=ch[cur][idx];

        //num[cur]+=c;

    }

}

ll query(ll x)//在字典树（数集)中查找和x异或是最大值的元素y，返回y

{

    int cur=0;

    for(int i=40;i>=0;--i)

    {

        int idx=(x>>i)&1;

        if(ch[cur][idx^1]) cur=ch[cur][idx^1];else cur=ch[cur][idx];

    }

    return val[cur]^x;

}

/*

ll query(ll x)//在字典树（数集)中查找和x异或是最大值的元素y，返回异或的最大值

//带删除操作的查询

{

    int cur=0;

    for(int i=32;i>=0;--i)

    {

        int idx=(x>>i)&1;

        if(ch[cur][idx^1]&&num[ch[cur][idx^1]]) cur=ch[cur][idx^1];else cur=ch[cur][idx];

    }

    return val[cur]^x;

}

*/

int main()

{

    int n,m;

    ll x;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        init();

        ll ans=0;

        F(i,1,n)

        {

            scanf("%I64d",&x);

            insert(x);

        }

        //printf("Case #%d:\n",k);

        F(i,1,m)

        {

            scanf("%I64d",&x);

            ans=max(ans,query(x));

        }

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

NOJ2026:Keroro侵略地球(01字典树)

传送门

题意

分析

trick

代码

最新文章

热门文章