結果
問題 |
No.1192 半部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:51:14 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,872 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 53,956 KB |
最終ジャッジ日時 | 2025-06-12 15:51:34 |
合計ジャッジ時間 | 4,008 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 TLE * 1 -- * 21 |
ソースコード
def is_subsequence(s, t): i = j = 0 len_s = len(s) len_t = len(t) while i < len_s and j < len_t: if s[i] == t[j]: i += 1 j += 1 return i == len_s def find_min_subsequence(S, T): set_T = set(T) # 情况一:检查S中是否有字符不在T中 min_char = None for c in S: if c not in set_T: if min_char is None or c < min_char: min_char = c if min_char is not None: return min_char # 情况二:检查S是否是T的子序列 if is_subsequence(S, T): return -1 # 情况三:构造结果字符串 result = [] current_pos = 0 n = len(S) while current_pos < n: min_c = None min_i = -1 # 遍历从current_pos开始的所有字符,寻找最小的c,使得result + c 不是T的子序列 for i in range(current_pos, n): c = S[i] temp_result = result + [c] if not is_subsequence(temp_result, T): if (min_c is None) or (c < min_c): min_c = c min_i = i # 如果找到符合条件的c if min_i != -1: result.append(S[min_i]) current_pos = min_i + 1 else: # 没有找到,选择current_pos处的字符,继续处理 result.append(S[current_pos]) current_pos += 1 # 检查当前result是否满足条件 if not is_subsequence(result, T): break # 检查最终的result是否满足条件 if not is_subsequence(result, T): return ''.join(result) else: return -1 # 读取输入 S = input().strip() T = input().strip() # 处理特殊情况:S为空字符串的情况 if not S: print("") else: res = find_min_subsequence(S, T) print(res)