传送门
题意：
构造
3
×
n
3 times n
3×n 个长度为
l
l
l 的字符串，每一位只有
0
,
1
,
2
0,1,2
0,1,2 三个数字，且满足第
i
i
i 位一共有
n
n
n 个
0
0
0,
n
n
n 个
1
1
1 ,
n
n
n 个
2
2
2
并且使得这些字符串中字典序最大的字符串字典序尽可能小。
题解：
第
1
1
1 位一定有
n
n
n 个
2
2
2 ,考虑三进制，那么字典序最大的字符串
t
t
t
≥
2
×
3
l
−
1
+
n
−
1
geq 2 times 3^{l-1} +n-1
≥2×3l−1+n−1
我们可以使得
t
=
2
×
3
l
−
1
+
n
−
1
t=2 times 3^{l-1} +n-1
t=2×3l−1+n−1 ,并且一定能构造出满足题意的字符串。
我们只需让已经构造出来的以
2
2
2为开头的字符串以如下形式变换：
1.0
−
>
1
1.0->1
1.0−>1
1
−
>
2
1->2
1−>2
2
−
>
0
2->0
2−>0
2.
2.
2.
0
−
>
2
0->2
0−>2
1
−
>
0
1->0
1−>0
2
−
>
1
2->1
2−>1
假设以
2
2
2开头第
i
i
i 位有
x
x
x 个
0
0
0 ,那么
1
1
1，
2
2
2 总共有
n
−
x
n-x
n−x 个，经过上述变换，就可以满足最终
0
0
0 的个数有
x
+
n
−
x
=
n
x+n-x=n
x+n−x=n
代码：
#pragma GCC diagnostic error "-std=c++11"
#include
#include
#include
#include
#include
#include
#include
