【题目意思】:
找出修改后的序列中,没出现的最小正整数。
修改操作是 将x与序列中所有数异或。(每次异或之后替代原序列的值)。
【解题思路】:
题目要求是找出不在序列里的的最小值。而字典树正好是解决异或最值问题的,所以我们将不在序列里的所有数放进字典树里面,进行异或操作,求出其中的最小值。
字典树求最小值 是 从最高位开始,判断每一位(2进制)上的值是否与自身在这一位上的值相等(异或是相等为0,不相等为1),如果相等,则走下去,如果不相等,只能走那一条路。
如何存储异或后的序列:
根据异或的性质。 a⊕b = c => a = b⊕c => b = a ⊕ c ;
所以记录异或后的序列,只要将每次的x异或起来,在与序列异或。
【代码】:
#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <vector> #include <stack> #include <bitset> #include <cstdlib> #include <cmath> #include <set> #define ms(a, b) memset(a,b,sizeof(a)) #define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long #define ull unsigned long long #define rep(i, a, b) for(ll i=a;i<=b;i++) #define lep(i, a, b) for(ll i=a;i>=b;i--) #define endl '\n' #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<ll> #define vpi vector<pii> #define vpl vector<pll> #define mi map<ll,ll> #define all(a) (a).begin(),(a).end() #define gcd __gcd #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define ff first #define ss second #define test4(x, y, z, a) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<" a is "<<a<<endl; #define test3(x, y, z) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<endl; #define test2(x, y) cout<<"x is "<<x<<" y is "<<y<<endl; #define test1(x) cout<<"x is "<<x<<endl; using namespace std; const int N = 3e5 + 10; const int maxx = 0x3f3f3f; const int mod = 1e9 + 7; const int minn = -0x3f3f3f; const int M = 2 * N; ll T, n, m; ll a[N]; ll son[N*32][2],idx,cnt[N*32]; ll vis[N*2 ]; void insert(ll n ){ int p=0; for ( int i=32;i>=0;i--){ int u = (n>>i)&1 ; if ( !son[p][u] ) son[p][u] = ++idx; p = son[p][u]; } cnt[p] = n; } ll query(ll n){ int p = 0; for ( int i=32;i>=0;i--){ int u = (n>>i)&1; if ( son[p][u] ){ p = son[p][u]; }else{ p = son[p][u^1]; } } return n^cnt[p]; } void solve() { cin>>n>>m; rep(i,1,n) {cin>>a[i]; vis[a[i]]=1 ;} rep(i,0,2*N){ if ( !vis[i] ) { insert(i); } } ll h = 0; ll x; rep(i,1,m){ cin>>x; h = h^x; cout<<query(h)<<endl; } } int main() { fast; solve(); return 0; }View Code