给你两个整数 n
和 m
,求集合的 mex
。n,m<=1e9
。
考点:二进制+模拟。
本人打的 数位 dp
。反正打着很恶心的模拟。
看了标算后豁然开朗:n^x=k <=> n^k<=m
。所以我们只需要检查第一个 n^k>m
的数即可。因为要 k
最小,所以从高到低枚举,取 n^k>=m+1
。
n>=m+1
,那么 k
取 0
都能满足 ,直接 break;
0
满足 n[i]>=p[i]
n[i]=0,p[i]=1
,此时最高位只能填 1
n[i]=1,p[i]=0
,根据上述条件直接 break;
看来还是缺乏思考。
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define ll long long #define PII pair<ll,int> #define All(a) a.begin(),a.end() using namespace std; ll n,m; int main() { ll T; cin>>T; while(T--) { cin>>n>>m; ll res = 0; m++; for(int i = 30; i >= 0 && n < m; i --) { ll t1 = (n>>i) & 1, t2 = (m>>i) & 1; if(t1 == t2) continue; if(t2) res += 1<<i, n |= 1<<i; } cout<<res<<endl; } }