题目重点：证明通配位置只需枚举一个切分点，用线性增量维护成本，避免指数搜索和提前取模。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- x,y 非负整数；每个 ! 独立替换为 0 或 1，固定字符不变。
- 01/10 是两个位置的子序列对，非连续子串。先最小化完整整数成本，再对最终答案取模。
- 示例函数返回完整最小成本，调用方按正式接口需要再做取模；不假称返回值已取模。
解题路线
- 若 x≤y，取两个通配位置 p<q，比较赋值 1…0 与 0…1，其余字符相同。两端的代价差为 y−x，中间每个字符也贡献 y−x，因此交换成 0…1 不增加成本，差值为 (q−p)(y−x)。
- 反复交换逆序通配赋值，得到某个最优解中所有通配位置先取 0 后取 1。固定的 0/1 不需要呈单调顺序。于是只剩 m+1 个切分点，m 是通配数。
- 初始把所有 ! 设 1，一遍扫描计算完整成本。再从左到右逐个把 ! 改 0；设左右已有 0/1 计数为 L0,L1,R0,R1，变化量是 yL1+xR1−xL0−yR0。每改一个就是下一切分点，更新最小值。
- 若 x>y，反转字符串并交换 x,y，问题和值完全等价，转回 x≤y 情形。实现只维护计数，不重复扫描所有位置对。
- 64 位或大整数保存完整成本，不能在每个切分点先取模再比较大小，因为取模不保序。最终按题目接口返回 answer%1000000007。
手动走一遍
训练例 '1!0',x=1,y=3。替换 0 得 '100'，有两个 10，成本 6；替换 1 得 '110'，也有两个 10，成本 6。例 '!!',x=1,y=3 取 00 或 11 的成本 0；不能只检查 01。长串里的固定字符仍保留原位。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def minimum_pair_cost(text: str, cost01: int, cost10: int) -> int:
"""Count all i<j pairs; ! is freely replaced by 0 or 1."""
if cost01 < 0 or cost10 < 0 or any(c not in "01!" for c in text):
raise ValueError("nonnegative costs and a binary/wildcard string required")
if cost01 > cost10:
text = text[::-1]
cost01, cost10 = cost10, cost01
values = ["1" if c == "!" else c for c in text]
total0 = values.count("0")
total1 = len(values) - total0
left0 = left1 = score = 0
for c in values:
if c == "1":
score += cost01 * left0
left1 += 1
else:
score += cost10 * left1
left0 += 1
answer = score
left0 = left1 = 0
for index, original in enumerate(text):
c = values[index]
if original == "!":
right0 = total0 - left0
right1 = total1 - left1 - 1
score += cost10 * left1 + cost01 * right1
score -= cost01 * left0 + cost10 * right0
total0 += 1
total1 -= 1
c = "0"
answer = min(answer, score)
if c == "0":
left0 += 1
else:
left1 += 1
return answer
复杂度
O(n) 时间、O(n) 示例数组空间，可只用原串与通配切分计数缩到 O(1) 辅助空间。6,558 组长度 0..6 字符串/费用组合逐一穷举全部通配赋值独立核对，包含 x<y、x>y、相等和零成本。
易错点与追问
容易失分的边界
- 把 count01 当相邻次数。
- 把整个串排序，改变固定字符。
- 在不同切分点的成本已取模后选最小。
- 忽略零成本、全通配和没有通配的输入。
继续深挖
- 若每个位置对有不同权重，交换证明哪一项失效？
- 需要输出最优替换串时如何记录切分点？
- 加入必须恰好 r 个 1 的约束，固定字符计数如何影响可行切分？
