这是一道找规律题。
不妨从小情况入手。当 \(n=2\) 时，显然令 \(a=\{ 0,1 \}\) 是最优的，此时进行一次操作得到 \(2\)，为最大的答案。这是最基础的情况，也就是对于 \(n\) 更大的情况，答案最多也只能是 \(2\)。接下来观察 \(\operatorname{mex}\) 的性质。
-
\(\operatorname{mex}(0,1)=2\)
-
\(\operatorname{mex}(0,2)=1\)
-
\(\operatorname{mex}(1,2)=0\)
不难发现，原来在 \(0,1,2\) 中，只要有了其中的两个数，便可以通过一次 \(\operatorname{mex}\) 转换为第三个数。有了这个性质，便可以开始构造答案了。
因为 \(\operatorname{mex}(1,2)=0\)，\(\operatorname{mex}(0,2)=1\)，所以 \(\{0,1\}\) 可由 \(\{1,2\}\) 和 \(\{0,2\}\) 分别操作后得到。把其中相同的 \(2\) 放在中间，可得到 \(\{1,2,0\}\)。这就是 \(n=3\) 的一组合法解。
对于 \(n\) 更大的情况，可以照着上述思路继续推。把推出来的结果列表：
2
0 1
1 2 0
2 0 1 2
0 1 2 0 1
不难发现在每一列以及最外层的斜线上，都是 \(0,1,2\) 在循环滚动。于是便可以很方便地输出了。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int T,n,cnt;
cin >> T;
while( T -- )
{
cin >> n;
cnt = 1;
for( int i = 1 ; i <= n ; i ++ )
{
cout << ( cnt + ( n - i + 1 ) ) % 3 << ' ';
cnt = ( ( cnt - 1 ) % 3 + 3 ) % 3;
}
cout << endl;
}
return 0;
}