A6957 | 完美的洗牌
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
魔术师手中有两叠扑克牌，我们把它们记作牌堆 $A$ 和牌堆 $B$。
牌堆 $A$ 中包含 $N$ 张牌，从上到下依次记录为字符串 $S_1$。
牌堆 $B$ 中包含 $M$ 张牌，从上到下依次记录为字符串 $S_2$。
现在魔术师进行一次“完美洗牌”操作：他将这就两堆牌交错地插在一起，形成了一堆新的牌（包含 $N+M$ 张），记作 $S_3$。
在洗牌过程中，魔术师必须遵守以下规则：
1. **顺序保留**：来自 $S_1$ 的牌在 $S_3$ 中的相对顺序不能改变；来自 $S_2$ 的牌在 $S_3$ 中的相对顺序也不能改变。
2. **完全使用**：$S_3$ 必须恰好包含 $S_1$ 和 $S_2$ 中的所有字符，不多也不少。
现在给你三个字符串 $S_1, S_2, S_3$，请你判断 $S_3$ 是否能由 $S_1$ 和 $S_2$ 通过上述“洗牌”规则得到。
牌堆 $A$ 中包含 $N$ 张牌，从上到下依次记录为字符串 $S_1$。
牌堆 $B$ 中包含 $M$ 张牌，从上到下依次记录为字符串 $S_2$。
现在魔术师进行一次“完美洗牌”操作：他将这就两堆牌交错地插在一起，形成了一堆新的牌（包含 $N+M$ 张），记作 $S_3$。
在洗牌过程中，魔术师必须遵守以下规则：
1. **顺序保留**：来自 $S_1$ 的牌在 $S_3$ 中的相对顺序不能改变；来自 $S_2$ 的牌在 $S_3$ 中的相对顺序也不能改变。
2. **完全使用**：$S_3$ 必须恰好包含 $S_1$ 和 $S_2$ 中的所有字符，不多也不少。
现在给你三个字符串 $S_1, S_2, S_3$，请你判断 $S_3$ 是否能由 $S_1$ 和 $S_2$ 通过上述“洗牌”规则得到。
输入格式
输入共三行。
第一行包含一个字符串 $S_1$。
第二行包含一个字符串 $S_2$。
第三行包含一个字符串 $S_3$。
第一行包含一个字符串 $S_1$。
第二行包含一个字符串 $S_2$。
第三行包含一个字符串 $S_3$。
输出格式
如果 $S_3$ 是由 $S_1$ 和 $S_2$ 交错组成的，输出
1；否则输出 0。输入输出样例
输入 #1
aabcc dbbca aadbbcbcac
输出 #1
1
输入 #2
aabcc dbbca aadbbbaccc
输出 #2
0
## 样例解释与数据范围
### 样例 #1 解释
**输出：1 (True)**
$S_1 = \text{"aabcc"}$, $S_2 = \text{"dbbca"}$
$S_3 = \text{"aadbbcbcac"}$
我们可以这样拆分 $S_3$：
- $S_3$ 的第 1, 2 位
- $S_3$ 的第 3, 4, 5 位
- $S_3$ 的第 6 位
- $S_3$ 的第 7 位
- $S_3$ 的第 8 位
- $S_3$ 的第 9 位
- $S_3$ 的第 10 位
合并起来正是 $S_1$ 和 $S_2$ 的顺序交错。
### 样例 #2 解释
**输出：0 (False)**
虽然 $S_3$ 包含了 $S_1$ 和 $S_2$ 的所有字符，但在尝试匹配时会发现，无法在保持 $S_1$ 和 $S_2$ 内部顺序的前提下组成 $S_3$。例如最后两个字符
### 数据范围
对于 $100\%$ 的数据：
- 字符串仅包含小写英文字母。
- $0 \le |S_1|, |S_2| \le 200$。
- $0 \le |S_3| \le 400$。
**数据点分布：**
- 测试点 1-5：$|S_1|, |S_2| \le 5$ (极小数据)
- 测试点 6-15：$|S_1|, |S_2| \le 50$
- 测试点 16-25：$|S_1|, |S_2| \le 200$
### 样例 #1 解释
**输出：1 (True)**
$S_1 = \text{"aabcc"}$, $S_2 = \text{"dbbca"}$
$S_3 = \text{"aadbbcbcac"}$
我们可以这样拆分 $S_3$：
- $S_3$ 的第 1, 2 位
aa 来自 $S_1$。- $S_3$ 的第 3, 4, 5 位
dbb 来自 $S_2$。- $S_3$ 的第 6 位
c 来自 $S_1$。- $S_3$ 的第 7 位
b 来自 $S_2$。- $S_3$ 的第 8 位
c 来自 $S_1$。- $S_3$ 的第 9 位
a 来自 $S_2$。- $S_3$ 的第 10 位
c 来自 $S_1$。合并起来正是 $S_1$ 和 $S_2$ 的顺序交错。
### 样例 #2 解释
**输出：0 (False)**
虽然 $S_3$ 包含了 $S_1$ 和 $S_2$ 的所有字符，但在尝试匹配时会发现，无法在保持 $S_1$ 和 $S_2$ 内部顺序的前提下组成 $S_3$。例如最后两个字符
cc 无法在不打乱顺序的情况下被放置。### 数据范围
对于 $100\%$ 的数据：
- 字符串仅包含小写英文字母。
- $0 \le |S_1|, |S_2| \le 200$。
- $0 \le |S_3| \le 400$。
**数据点分布：**
- 测试点 1-5：$|S_1|, |S_2| \le 5$ (极小数据)
- 测试点 6-15：$|S_1|, |S_2| \le 50$
- 测试点 16-25：$|S_1|, |S_2| \le 200$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？