官方题解

T5 午枫的mex

题目大意

求 $mex\{i\oplus j \mid i\in [1,n],j\in[1,n] \}$ .

解题思路

通过打表，善于观察的同学可能会发现一定规律：$\begin{cases} \begin{aligned} 1,n\leq 2\\ 2^{\lceil\log{n}\rceil},n>2 \end{aligned} \end{cases}$。

证明：对于 $n$ 的最高位 $1$，仅保留这一位 $1$，对于低位可以任取，此时覆盖了 $n$ 最高位为 $1$ 的所有情况；然后 $n$ 的最高位 $1$ 这一位为 $0$，次高位为 $1$，对于低位可以任取，此时覆盖了 $n$ 次高位为 $1$ 的所有情况。依次类推，所以最小的不能被表示的就是 $2^{\lceil\log{n}\rceil}$，$n=1,2$ 特判。

时间复杂度 $O(Tlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n;cin>>n;
    if(n<=2){
        cout<<1<<endl;
        return;
    }

    int now=4;
    while(now<n){
        now<<=1;
    }
    cout<<now<<endl;
}

signed main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}