English version

Each operation transform three adjacent characters into one. If the string starts with 11, the answer should be yes since we can first transform the remaining part into a single 0 or 1 and then the value of 11? is always $1$.

If the string ends with 1, only 101 has no solution, otherwise it starts with 11 or 0, or we can transform 10? in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation 0?(anything):1 makes 1.

If an operation transformed a string ending with 0 into one ending with 1, it must be 1?1:0 makes 1.

Consider the case where the strings contains 11 as a substring. After transforming the remaining part, ?11?? or ??11? will be derived. The cases are 01100, 00110, 01110, 10110. All other cases start with 11 or end with 1.

All cases of ??11? have a solution:

(0?0:1)?1:0 makes 1.

(0?1:1)?1:0 makes 1.

1?(0?1:1):0 makes 1.

However, 01100 has no solution.

Since 0?0:1 equals 1, before the last 1, any two adjacent 0's with no 1 in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former 1, i.e., (..)*1(00)*1(..)*0 in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former 1 guarantees that it will not become 01100.

Another case is that the string ends with 0 and every pair of adjacent 1's has an odd number of 0's in between. Since 0(1?0:1)0 makes 000, 1(0?1:0)1 makes 101, 10(1?0:0)01 makes 10001, there is no way to change the parity of the consecutive 0's to make 11 to change the ending 0 into 1.

In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring.

Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{black}(00)^*\color{red}1\color{blue}((00)^*01)^*\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution.

In conclusion, it has a solution if and only of at least one of the two following conditions is met:

• It ends with 1 but it is not 101.
• It has two adjacent 1's such that there are even 0's in between and the number of characters before the former 1 is even.

中文版本

英文题解里描述了做本题的一种思路，以及证明。

如果要直接写做法的话，是下面这样：

假设字符串下标从 $1$ 开始编号。

首先判断是否存在 $i,j$ 使得 $i$ 是奇数，$j$ 是偶数，$s_i$ 和 $s_j$ 都是 1，且这两个字符中间都是 0。

• 如果是，那么先把中间的 0 和 $s_j$ 写成 (0?0:0?0:.....:1)，表达式的值为 1（一定有偶数个 0），然后分三种情况：

  • 如果 $i=1$，那么就直接把 $s_j$ 后面的部分变成一个数，最后变成 (1?1:*) 是 1。

  • 否则考虑把 $s$ 的第 $1\sim i-2$ 位变成一个数，并计算出这个值。

    • 如果值为 0 那么有 ((0?*:1)?1:*) 等于 1。
    • 如果值为 1 那么有 (1?(*?1:1):*) 等于 1。

• 否则，判断是否满足字符串末尾是 1 且本身不等于 101：

  • 如果是，那么字符串一定以 0 或 10 开头，于是第一位或前三位操作后一定是 0，然后留下开头的 0 和结尾的 1，把中间的部分变成一个数，最后 (0?*:1) 结果一定是 1。
  • 否则，无解。

此外，还有一种比较特别的解法：

可以发现构造的过程中需要用到不超过两层括号（不算整个表达式最外面一层）。所以如果你要是猜到了这一点可以直接使用动态规划从右到左扫这个字符串，记录每一层栈中的内容。最多三层栈，每层栈最多两个比特，一共 $6^3+6^2+6=258$ 种状态。大概也能过。

不知道有没有什么奇怪的乱搞可以搜过去。不过我还是欢迎吧。