文章目录

CF1889A Qingshan Loves Strings 2 做题笔记

发布于

题意

给定一个 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 的个数不同时无解。


暂无评论

发表评论