1 条题解

  • 0
    @ 2025-12-19 21:18:32

    自己想的 01trie 的做法:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e7+10;
    int tr[N][2],trlen,sum[N];set<int>s;
    void ins(int x)
    {
    	int id=0;
    	for(int i=29;i>=0;i--)
    	{
    		if(x&(1<<i))
    		{
    			if(!tr[id][1])tr[id][1]=++trlen;
    			id=tr[id][1];
    		}
    		else
    		{
    			if(!tr[id][0])tr[id][0]=++trlen;
    			id=tr[id][0];
    		}
    		sum[id]++;
    	}
    }
    void del(int x)
    {
    	int id=0;
    	for(int i=29;i>=0;i--)
    	{
    		if(x&(1<<i))
    			id=tr[id][1];
    		else
    			id=tr[id][0];
    		sum[id]--;
    	}
    }
    int get(int x)
    {
    	int id=0,ans=0;
    	for(int i=29;i>=0;i--)
    	{
    		if(x&(1<<i))
    		{
    			if(!sum[tr[id][1]])
    				ans+=(1<<i),id=tr[id][0];
    			else
    				id=tr[id][1];
    		}
    		else
    		{
    			if(!sum[tr[id][0]])
    				ans+=(1<<i),id=tr[id][1];
    			else 
    				id=tr[id][0];
    		}
    	}
    	return ans;
    }
    int main()
    {
    	int q;cin>>q;
    	for(int i=1;i<=q;i++)
    	{
    		int op,x;cin>>op>>x;
    		if(op==0)
    			if(!s.count(x))ins(x),s.insert(x);
    		if(op==1)
    			if(s.count(x))del(x),s.erase(x);
    		if(op==2)
    			cout<<get(x)<<'\n';
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    8139
    时间
    1000ms
    内存
    1024MiB
    难度
    7
    标签
    递交数
    29
    已通过
    9
    上传者