T5 午枫的MEX 题目大意 求 mex{i⊕j∣i∈[1,n],j∈[1,n]}mex\{i\oplus j \mid i\in [1,n],j\in[1,n] \}mex{i⊕j∣i∈[1,n],j∈[1,n]} . 解题思路 通过打表，善于观察的同学可能会发现一定规律：{1,n≤22⌈log⁡n⌉,n>2\begin{cases} \begin{aligned} 1,n\leq 2\\ 2^{\lceil\log{n}\rceil},n>2 \end{aligned} \end{cases}{1,n≤22⌈logn⌉,n>2 。 证明：对于 nnn 的最高位 111，仅保留这一位 111，对于低位可以任取，此时覆盖了 nnn 最高位为 111 的所有情况；然后 nnn 的最高位 111 这一位为 000，次高位为 111，对于低位可以任取，此时覆盖了 nnn 次高位为 111 的所有情况。依次类推，所以最小的不能被表示的就是 2⌈log⁡n⌉2^{\lceil\log{n}\rceil}2⌈logn⌉，n=1,2n=1,2n=1,2 特判。 时间复杂度 O(Tlogn)O(Tlogn)O(Tlogn) 参考代码

注意到 题意：两个数 0<i,j<n0<i,j<n0<i,j<n 进行异或得到的最大值 +1+1+1 求这个值（好像不是((( 很自然的想到：对于一个数 2k+1>n>2k2^{k+1}>n>2^k2k+1>n>2k 存在 100...0100...0100...0 （有 k 个 0 ）这个二进制 异或后一定存在 2k+1 2k+1−12^k+1 ~ 2^{k+1}-12k+1 2k+1−1 这些值 （cao我~显示不出来） 2k2^k2k 可以通过 2k+12^k+12k+1 异或 111 得到 于是： 如果 n=2kn = 2^kn=2k 为 2k2^k2k 否则为 2log2(n)+12^{log_2(n)+1}2log2 (n)+1 (向上取整不会打) 用代码写就是 注意 nnn 要开 long long (不开 long long 见祖宗((( 代码

注意到对于任意 i(1≤i<2⌈log⁡2n⌉)i(1\le i\lt 2^{\lceil\log_2 n\rceil})i(1≤i<2⌈log2 n⌉)，(2⌈log⁡2n⌉)⊕i=(2⌈log⁡2n⌉)+i(2^{\lceil\log_2 n\rceil})\oplus i=(2^{\lceil\log_2 n\rceil})+i(2⌈log2 n⌉)⊕i=(2⌈log2 n⌉)+i，并且肯定无法异或出 2⌈log⁡2n⌉+12^{\lceil\log_2 n\rceil+1}2⌈log2 n⌉+1。所以答案是 2⌈log⁡2n⌉+12^{\lceil\log_2 n\rceil+1}2⌈log2 n⌉+1。 诶我超我好像没特判

T5午枫的MEX * 难度：普及/提高- ？ * 思路分析 1. 化简 需要计算所有 i⊕j(i,j∈[1,n])i⊕j (i,j∈[1,n])i⊕j(i,j∈[1,n]) 的 mexmexmex（最小未出现的非负整数） （特判情况） n=1n=1n=1 的特殊情况，直接输出 111 （因为只有 1⊕1=01⊕1=01⊕1=0 ，mexmexmex 是 111 ） 2. 瞪眼： 当 n≥2n≥2n≥2 时，最大的异或结果会接近但不小于2k2^k2k，说人话就是最大异或结果 ≥2k≥2^k≥2k（其中2k−1≤n<2k2^{k-1} ≤ n < 2^k2k−1≤n<2k） mexmexmex 值实际上是这个 2k2^k2k 3. 计算： 找到大于 nnn 的最小 222 的幂次方 mmm mexmexmex 结果就是这个 mmm * 时间复杂度分析 此代码仅涉及 ttt 次测试样例循环，以及while(m<=n)m*=2; ，复杂度为log nlog~nlog n 总复杂度：O(t×log n)O(t ×log~n)O(t×log n)