Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset - dblank

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

传送门: D. Vasiliy's Multiset

思路:我们可以用一个字典树来保存这个集合,+,-操作都很好处理,直接在字典树上删除插入就可以。对于 第三种操作,我们可以在字典树上贪心,因为我们插入到字典树要按照二进制插入,而且位权高的离根节点更近于是我们按照x的二进制,如果该点不为空的话,且可以让bit[i] 异或其为1,我们就进入这个子树,并且获得该点的权值,直到到叶子节点。要注意一点,如果最后的值小于x的话,就直接ans取x的值了,还有树为空的话,也直接ans=x。


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int num[50];
struct node
{
    int data;
    node *nxt[2];
    node()
    {
        data = 0;
        memset(nxt, 0, sizeof(nxt));
    }
};
node * root = new node;
int *change(int x)
{
    for(int i = 0; i<=30; i++)
    {
        num[30 - i] = x & 1;
        x>>=1;
    }
    return num;
}
void insert_tree(int *num, int mark)
{
    node * p = root;
    for(int i = 0; i<=30; i++)
    {
        if(p->nxt[num[i]] == NULL)
        {
            p->nxt[num[i]] = new node;
        }
        p = p->nxt[num[i]];
        p->data += mark;
    }
}
int query(int *num)
{
    int res = 0;
    node *p = root;
    for(int i = 0; i<=30; i++)
    {
        int id = -1, ok = 0;
        for(int j = 0; j<=1; j++)
        {

            if(num[i] ^ j == 1 && p->nxt[j]!=NULL &&p->nxt[j]->data != 0)
            {
                id = j;
            }
            if(p->nxt[j]!=NULL &&p->nxt[j]->data != 0)
                ok = 1;
        }
        if(id !=-1)
            res |= 1<< 30- i;
        else if(id == -1)
            id = num[i];
        if(!ok)
            return -1;
        p = p->nxt[id];
    }
    return res;
}
int main()
{
    int n;
    while(cin>>n)
    {
        char c;
        int x;
        for(int i = 0; i<n; i++)
        {
            scanf(" %c%d", &c, &x);
            if(c == '+')
                insert_tree(change(x), 1);
            if(c == '-')
                insert_tree(change(x), -1);
            if(c == '?')
            {
                int ans = query(change(x));
                if(ans == -1)
                    printf("%d\n", x);
                else printf("%d\n", max(ans, x));
            }
        }
    }
    return 0;

相关文章

发表新评论