非官方题解|挑战赛#21-T5

T5午枫的mex

• 难度：普及/提高- ？

• 思路分析

1. 化简
   需要计算所有 $i⊕j (i,j∈[1,n])$ 的 $mex$（最小未出现的非负整数）
   （特判情况） $n=1$ 的特殊情况，直接输出 $1$ （因为只有 $1⊕1=0$ ，$mex$ 是 $1$ ）

2. 瞪眼：
   当 $n≥2$ 时，最大的异或结果会接近但不小于$2^k$，说人话就是最大异或结果 $≥2^k$（其中$2^{k-1} ≤ n < 2^k$）
   $mex$ 值实际上是这个 $2^k$

3. 计算：
   找到大于 $n$ 的最小 $2$ 的幂次方 $m$
   $mex$ 结果就是这个 $m$

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        //特判情况
        if(n==1){ 
            cout<<"1"<<endl; // mex{0}=1
            continue;
        }
        
        //计算大于n的最小2的幂次方
        long long m=1; //初始化为1
        while(m<=n)m*=2;//找到大于n的最小2^k 
        cout<<m<<endl;
    }
}

• 时间复杂度分析

此代码仅涉及 $t$ 次测试样例循环，以及while(m<=n)m*=2; ，复杂度为$log~n$
总复杂度：$O(t ×log~n)$