2029B.md (2455B)
1 Source: https://codeforces.com/problemset/problem/2029/B 2 3 B. Replacement 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have a binary string$^{\text{∗}}$ $s$ of length $n$, and Iris gives you another binary string $r$ of length $n-1$. 22 23 Iris is going to play a game with you. During the game, you will perform $n-1$ operations on $s$. In the $i$-th operation ($1 \le i \le n-1$): 24 25 * First, you choose an index $k$ such that $1\le k\le |s| - 1$ and $s_{k} \neq s_{k+1}$. If it is impossible to choose such an index, you lose; 26 * Then, you replace $s_ks_{k+1}$ with $r_i$. Note that this decreases the length of $s$ by $1$. 27 28 If all the $n-1$ operations are performed successfully, you win. 29 30 Determine whether it is possible for you to win this game. 31 32 $^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$. 33 34 Input 35 36 Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows. 37 38 The first line of each test case contains a single integer $n$ ($2\le n\le 10^5$) — the length of $s$. 39 40 The second line contains the binary string $s$ of length $n$ ($s_i=\mathtt{0}$ or $\mathtt{1}$). 41 42 The third line contains the binary string $r$ of length $n-1$ ($r_i=\mathtt{0}$ or $\mathtt{1}$). 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 45 46 Output 47 48 For each test case, print "YES" (without quotes) if you can win the game, and "NO" (without quotes) otherwise. 49 50 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 51 52 Example 53 54 Input 55 56 ``` 57 6 58 59 2 60 61 11 62 63 0 64 65 2 66 67 01 68 69 1 70 71 4 72 73 1101 74 75 001 76 77 6 78 79 111110 80 81 10000 82 83 6 84 85 010010 86 87 11010 88 89 8 90 91 10010010 92 93 0010010 94 ``` 95 96 Output 97 98 ``` 99 NO 100 101 YES 102 103 YES 104 105 NO 106 107 YES 108 109 NO 110 ``` 111 112 Note 113 114 In the first test case, you cannot perform the first operation. Thus, you lose the game. 115 116 In the second test case, you can choose $k=1$ in the only operation, and after that, $s$ becomes equal to $\mathtt{1}$. Thus, you win the game. 117 118 In the third test case, you can perform the following operations: $\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}$.