题意
给定一个 01 串 $s$。每次操作你可以在任意位置插入一个字符串 $\texttt{01}$,问是否能在 $300$ 次操作以内,使得 $s$ 与 $s'$ 的对应位置都不相同(其中 $s'$ 表示 $s$ 首位翻转后的字符串,即 ${s'}_i = s_{\left\lvert s\right\rvert - i + 1}$)。
如果可以,给出构造方案。不要求操作次数最小。
$1 \leq \left\lvert s\right\rvert \leq 100$
题解
考虑 $s_1$ 是否等于 $s_n$。
- 如果 $s_1 = s_n$,那么可以让 $s \gets s_{2 \ldots n - 1}$,然后继续做。
$$\\$$ - 如果 $s_1 \neq s_n$,可以在 $s$ 的开头插入 $\texttt{01}$,或者在 $s$ 的末尾插入 $\texttt{01}$,这样可以让它们相等。
而容易发现,$s$ 中 0 的个数与 1 的个数不同时无解。