嫌弃讲题人的我，准备好好写一篇题解。
观察数据范围：\(1\le N\le 50\)。
如果是 \(20\)，想到 \(2^{20}\)；如果是 \(40\)，想到 \(2^{40\div 2}\)；若果是 \(50\) 呢？\(2^{25}\) 有点大，于是想到 \(2^{50\div 3}\)。但是如何去凑？
Hint
| \(N\) | \(S\) | \(T\) | \(res\) |
|---|---|---|---|
| \(6\) | \(\tt{XXXXXX}\) | \(\tt{YYYYYY}\) | \(\tt{XYXYX}\) |
| \(8\) | \(\tt{XXXXXXXX}\) | \(\tt{XXXXXXXX}\) | \(\tt{XXXXXXXX}\) |
| \(20\) | \(\tt{YYYXYYXXXXXYYXYYXXXY}\) | \(\tt{YXYYXXXYYXYYYYYYXXYY}\) | \(\tt{YYYXYXXYXXYYYYYXXY}\) |
备注：第一行是最坏情况，第二行最好，第三行随机。
What you can see
答案长度都很大？再看看。最小长度多少？
lemma: 答案 \(\ge \lfloor \frac{2N}{3}\rfloor\)。
证明：\(N=3k+r\)证明长度是 \(3\) 的答案 \(\ge 2\) 和 \(r\) 的部分。
-
长度为 \(1\)。最坏 \(S=\tt{X},T=\tt{Y}\)，答案是 \(0\)。
-
长度为 \(2\)。若有一个相同，答案 \(\ge 1\)；若都不相同即 \(S=\tt{XX},T=\tt{YY}\)，可交换使答案为 \(2\)。
-
长度为 \(3\)。第一个和第三个若有一个相同，转化为 长度为 \(2\) 的加上 \(1\)，答案显然 \(\ge 2\)；都不相同，若第二个相同（\(S=\tt{XXX},T=\tt{YXY}\)）或不相同（\(S=\tt{XXX},T=\tt{YYY}\)），均可答案 \(\ge 2\)。
考虑 \(r\) 是几。
-
\(r=0\) 显然 答案 \(\ge \lfloor \frac{2N}{3}\rfloor\)。
-
\(r=1\)，\(1\times 2\) 对除 \(3\) 下取整没有影响。
-
\(r=2\)，\(2\times 2\) 贡献一个 \(1\)，正好。
即证。
待更，对不起。
标签：20,相同,157,tt,Sol,ge,ARC,答案,长度 From： https://www.cnblogs.com/SFlyer/p/17636339.html