D. Conditional Operators 详细题解

一、问题重述

给定一个长度为 $2n+1$ 的 01 字符串，需要在其中插入 $n$ 个三元条件运算符 ?: 以及括号，使得最终表达式值为 $1$。运算符右结合：a?b:c?d:e 等价于 a?b:(c?d:e)。不能改变原字符串中字符的顺序。

需要判断可行性，如果可行，输出一个表达式（长度不超过 $10n+1000$）。

---

二、核心观察

2.1 运算符的本质

三元条件运算符 x?y:z 的作用是将三个表达式合并为一个表达式。每次操作相当于：

• 取三个相邻的表达式 $a,b,c$（对应字符串中的三个连续字符或子表达式）
• 将它们替换为 $a?b:c$

这个过程与二叉树的构造类似，最终整个字符串被折叠成一个表达式。

2.2 基本归约操作

定义 fold(l, r) 表示将子串 s[l..r] 归约为一个表达式，返回值 (expression_string, value)。核心逻辑是从右向左进行运算：

v = s[r]
for i = r-2 downto l step -2:
    v = (s[i] == '1') ? s[i+1] : v

即每次将 s[i]?s[i+1]:当前结果 合并，最终得到一个值 v 在 $\{0,1\}$。

---

三、可行性判断

3.1 后缀 1 的情况

如果字符串以 1 结尾，唯一无解的情况是 101。证明：

• 对于长度 $2n+1 \ge 5$ 的字符串，如果以 1 结尾：
  • 如果开头是 11，可以先将剩余部分归约为单个字符 $c$，则表达式变为 1?1:c 或 1?c:1，值均为 $1$。
  • 如果开头是 0$，可以先处理前三个字符：0?s[t]:1`（其中 $s[t]$ 是第二个字符），使其结果为 $1$，然后与后续归约。

3.2 存在相邻 11

如果字符串中存在相邻的两个 1，且它们之间的 0 的个数为偶数，并且这两个 1 之前的字符数为偶数，则有解。

原因：偶数个 0 可以通过 0?0:1 或 1?1:0 等操作消去，使两个 1 相邻。此时构造形如 ...?(...):1 的表达式即可得到 $1$。

3.3 需要排除的无解模式

01100 是一个经典无解情况。更一般地，如果字符串以 0 结尾，且所有相邻 1 对之间都有奇数个 0，则无解。因为任何操作都会保持这一性质，且无法将最后一个 0 变为 $1$。

---

四、构造算法

4.1 整体策略

标程采用贪心构造：

1. 寻找第一个满足特定条件的 1（即可以作为“分界点”的 1）
2. 将字符串分为三部分：
   • 左侧部分（可以归约为单个字符）
   • 中间的 1 及其后面的 0 或 1
   • 右侧剩余部分
3. 按照以下模板输出表达式：
   • 如果找到满足 i%2==0 && last%2==1 的 1，则构造 (左侧)?(中间):(右侧)
   • 否则处理结尾为 1 的情况（排除 101）

4.2 关键函数 fold

pair<string, char> fold(int l, int r) {
    // 将 s[l..r] 归约为一个表达式
    // 返回 (表达式字符串, 表达式的值)
}

它从右向左每次取三个相邻位置 s[i], s[i+1], 当前结果，合并为 s[i]?s[i+1]:当前结果。

---

五、完整标程（带详细注释）

#include<bits/stdc++.h>
using namespace std;

char s[333333];

// 计算表达式值：x ? y : z
char val(char x, char y, char z) {
    return x == '1' ? y : z;
}

// 将 s[l..r] 归约为一个表达式，返回 (表达式字符串, 表达式的值)
pair<string, char> fold(int l, int r) {
    string str;
    char v = s[r];                     // 初始值为最后一个字符
    // 构建表达式字符串
    for (int i = l; i < r; i += 2) {
        str += s[i];
        str += '?';
        str += s[i+1];
        str += ':';
    }
    str += s[r];
    // 从右向左计算表达式的值
    for (int i = r-2; i >= l; i -= 2) {
        v = val(s[i], s[i+1], v);
    }
    return make_pair(str, v);
}

void solve() {
    int n;
    scanf("%d", &n);
    n = 2 * n + 1;                     // 字符串实际长度
    scanf("%s", s + 1);                // 1-indexed 存储
    
    int last = 0;                      // 上一个 '1' 的位置
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1' && last > 0) {
            // 存在两个相邻的 '1'（中间可能有 0）
            // 条件：i 为偶数，last 为奇数，且中间有偶数个 0
            if (i % 2 == 0 && last % 2 == 1) {
                puts("Yes");
                
                // 构造表达式：左侧部分 ? 中间部分 : 右侧部分
                // 步骤1：构造从 last+1 到 i 的表达式
                string s4 = fold(last + 1, i).first;
                // 步骤2：构造从 i+1 到 n 的表达式
                auto tmp = fold(i + 1, n);
                string s5 = tmp.first;
                char v5 = tmp.second;
                
                if (last == 1) {
                    // 特殊情况：左侧只有一个字符
                    printf("1?(%s):(%s)\n", s4.c_str(), s5.c_str());
                    return;
                }
                
                // 步骤3：构造从 1 到 last-2 的表达式
                tmp = fold(1, last - 2);
                string s1 = tmp.first;
                char v1 = tmp.second;
                
                if (v1 == '1') {
                    // 左侧表达式值为 1
                    printf("(%s)?(%c?1:(%s)):(%s)\n", 
                           s1.c_str(), s[last-1], s4.c_str(), s5.c_str());
                } else {
                    // 左侧表达式值为 0
                    printf("((%s)?%c:1)?(%s):(%s)\n", 
                           s1.c_str(), s[last-1], s4.c_str(), s5.c_str());
                }
                return;
            }
        }
        if (s[i] == '1') {
            last = i;                  // 更新最后一个 '1' 的位置
        }
    }
    
    // 情况2：字符串以 '1' 结尾且不是 "101"
    if (s[n] == '1' && string(s+1) != "101") {
        puts("Yes");
        // 构造表达式
        auto left = (s[1] == '0') ? fold(1, 1) : fold(1, 3);
        auto mid = (s[1] == '0') ? fold(2, n-1) : fold(4, n-1);
        printf("(%s)?(%s):1\n", left.first.c_str(), mid.first.c_str());
        return;
    }
    
    // 无解
    puts("No");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

---

六、构造示例

以输入 2 10101 为例：

• 字符串长度 $2n+1=5$，实际 s[1..5] = 1 0 1 0 1
• 遍历找到 i=3 时，s[3]=1，last=1（上一个 1 在位置 1）
• 满足 i%2==0？3%2=1 不满足，继续
• i=5 时，s[5]=1，last=3，5%2=1 仍不满足
• 最终进入结尾 1 的分支，构造输出 (1?0:1)?(0):1 ✅

---

七、复杂度分析

• 时间复杂度：$O(n)$ 每个测试用例，总 $n$ 不超过 $1.5\times 10^5$
• 空间复杂度：$O(n)$ 用于存储表达式字符串
• 表达式长度：$O(n)$，满足 $\le 10n+1000$ 的要求

---

八、总结

本题的关键在于将三元条件表达式的计算过程抽象为从右向左的归约，并利用以下性质：

• 运算符 ?: 的右结合性决定了计算顺序
• 值只由最右边的字符和其左侧的奇数位置字符决定
• 字符串的模式可以通过奇偶性分类讨论

通过分析相邻 1 之间的 $0$ 个数奇偶性和前面字符数的奇偶性，得出可解的充要条件，并给出线性时间的构造算法。