← 返回题目列表

Codeforces · 2073/G

G. 文件损坏

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Corrupted File - 原题 PDF 第 1 页
原题PDF第13页
Corrupted File - 原题 PDF 第 2 页
原题PDF第14页
可复制的 PDF 提取文本
Problem G
                     Corrupted File
                     Time limit: 2 seconds


The WannaLaugh malware is a new computer malware that is spreading on the internet. If a computer is infected by
this malware, then the malware will corrupt all files in the computer. A file in a computer contains zero or more bits.
The malware corrupts a file by performing zero or more operations. In one operation, the malware randomly picks two
consecutive bits and replaces them with a single bit. The new bit is 1 if both of the replaced bits are 1, or 0 otherwise.

For example, the malware might corrupt a file with bits 11011011 as follows:

   1. The malware picks the first and second bits: 11011011 →1011011.

   2. The malware picks the second and third bits: 1011011 →101011.

   3. The malware picks the third and fourth bits: 101011 →10011.

Alternatively, the malware might first pick the third and fourth bits: 11011011 →1101011.

At the start of the day, you have a file containing n bits, denoted by B. You spend the day surfing the internet, including
checking on your favorite programming contest website, just like many ICPC contestants would do. At the end of the
day, the same file contains m bits, denoted by C. You want to determine whether this file could have been corrupted
by the WannaLaugh malware, or if it must have changed for other reasons.

Input
The first line of input contains one integer t (1 ≤t ≤10 000) representing the number of test cases. After that, t test
cases follow. Each of them is presented as follows.

The first line of input contains two integers n and m (1 ≤m ≤n ≤100 000). The second line contains a string with
n characters, each is either 0 or 1, representing the bits B. The third line contains a string with m characters, each is
either 0 or 1, representing the bits C.

The sum of n across all test cases in one input file does not exceed 100 000.

Output
For each test case, output yes if the file with bits B could have been corrupted by the WannaLaugh malware into bits
C, or no otherwise.





The 2025 ICPC Asia Pacific Championship Problem G: Corrupted File

Sample Input #1                          Sample Output #1

 3                                      yes
 8 5                                    yes
 11011011                               no
 10011
 3 3
 101
 101
 3 2
 101
 00


Explanation for the sample input/output #1

The first test case corresponds to the example from the problem description.

For the second test case, it is possible that the malware performs zero operations.

For the third test case, it is impossible for the malware to corrupt a file with bits 101 so that it has bits 00.





The 2025 ICPC Asia Pacific Championship Problem G: Corrupted File