Slavic's Exam 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求将字符串 $s$ ~s~ 中的每个 ? 替换为小写字母，使目标串 $t$ ~t~ 成为 $s$ ~s~ 的子序列，并输出任意可行结果。核心解法是贪心双指针匹配，遇到 ? 优先匹配当前需要的 $t$ ~t~ 字符，剩余 ? 补 a。

分析

核心观察

若当前字符是 ?，将它替换为 $t$ ~t~ 当前待匹配字符一定不劣于替换为其他字符，因为它能推进匹配进度且不会影响后续字符的可匹配性。

思路

维护指针 $i$ ~i~ 遍历 $s$ ~s~，指针 $idx$ ~idx~ 指向 $t$ ~t~ 中下一个需要匹配的位置。对于每个位置 $i$ ~i~：

若 $s_i$ ~s_i~ 是 ?，则将其设为 $t_{idx}$ ~t_{idx}~（若 $idx$ ~idx~ 尚未越界），并将 $idx$ ~idx~ 加 $1$ ~1~；若 $idx$ ~idx~ 已经等于 $|t|$ ~|t|~，则任意填 a。
若 $s_i$ ~s_i~ 不是 ?，且 $idx < |t|$ ~idx < |t|~ 且 $s_i = t_{idx}$ ~s_i = t_{idx}~，则匹配成功， $idx$ ~idx~ 加 $1$ ~1~。
其他情况不匹配，继续向后扫描。

该贪心策略的正确性基于：? 作为万能字符，越早用于匹配 $t$ ~t~ 的当前字符，就能为后续字符留下更多机会；若某个 ? 不匹配当前字符而等后续可能匹配，反而可能因后续非 ? 字符错过匹配，因此当前匹配是最优的。

遍历结束后，若 $idx = |t|$ ~idx = |t|~，说明全部匹配成功，将所有剩余的 ? 替换为 a（样例中未提及，但参考代码和逻辑如此），输出 YES 和结果；否则输出 NO。

具体示例

以样例第一组 s = "?????"，t = "xbx" 为例：

初始 $idx=0$ ~idx=0~，遍历所有 ?，依次将前三个 ? 设为 x, b, x， $idx$ ~idx~ 变为 $3$ ~3~，剩余两个 ? 填 a，得到 xabax，匹配成功。

以样例第四组 s = "ab??e"，t = "dac" 为例：

遍历 $s$ ~s~：a 不匹配 d，b 不匹配 d，遇到第一个 ? 设为 d， $idx=1$ ~idx=1~；第二个 ? 设为 a， $idx=2$ ~idx=2~；e 不匹配 c，最终 $idx=2 < 3$ ~idx=2 < 3~，输出 NO。

算法步骤

对每个测试用例，读入字符串 $s$ ~s~ 和 $t$ ~t~。
初始化匹配指针 idx = 0。
遍历 $s$ ~s~ 的每个字符 ch：
- 若 ch 为 ?：
  - 若 idx 小于 t 的长度，则将当前字符设为 t[idx]，并将 idx 加 $1$ ~1~；
  - 否则，将当前字符设为 a。
- 否则（ch 不是 ?）：
  - 若 idx 小于 t 的长度且 ch == t[idx]，则将 idx 加 $1$ ~1~。
遍历结束后，若 idx == t.length()，则输出 YES 和修改后的 $s$ ~s~；否则输出 NO。

复杂度分析

时间： $O(|s|)$ ~O(|s|)~，每个字符处理常数次，所有测试用例总长度 $O(2 \times 10^5)$ ~O(2 \times 10^5)~。
空间： $O(1)$ ~O(1)~ 额外空间（不计输入输出）。

实现注意事项

在判断非 ? 字符是否匹配时，必须确保 idx < t.size()，否则访问 t[idx] 越界；参考代码中缺少该判断，实现时需补全。
若已匹配完所有 $t$ ~t~，后续 ? 可统一填 a，其他字符保持不变。
输出时，YES 和 NO 大小写均可，但本题解统一输出大写。
所有测试用例的 $|s|$ ~|s|~ 之和不超过 $2 \times 10^5$ ~2 \times 10^5~，使用 string 类型直接存储和修改即可。

源代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        int idx = 0;
        int n = (int)s.size(), m = (int)t.size();

        for (int i = 0; i < n; ++i) {
            if (s[i] == '?') {
                if (idx < m) {
                    s[i] = t[idx];
                    ++idx;
                } else {
                    s[i] = 'a';
                }
            } else {
                if (idx < m && s[i] == t[idx]) {
                    ++idx;
                }
            }
        }

        if (idx == m) {
            cout << "YES\n" << s << '\n';
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

import sys

def solve():
    input_data = sys.stdin.read().strip().split()
    T = int(input_data[0])
    pos = 1
    out_lines = []
    for _ in range(T):
        s = list(input_data[pos]); pos += 1
        t = input_data[pos]; pos += 1
        idx = 0
        m = len(t)
        for i in range(len(s)):
            if s[i] == '?':
                if idx < m:
                    s[i] = t[idx]
                    idx += 1
                else:
                    s[i] = 'a'
            else:
                if idx < m and s[i] == t[idx]:
                    idx += 1
        if idx == m:
            out_lines.append("YES")
            out_lines.append("".join(s))
        else:
            out_lines.append("NO")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

目前没有评论。