A16148 | Miriany and Matchstick
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Miriany's matchstick is a $2 \times n$ grid that needs to be filled with characters A or B.
He has already filled in the first row of the grid and would like you to fill in the second row. You must do so in a way such that the number of adjacent pairs of cells with different characters $^\dagger$ is equal to $k$ . If it is impossible, report so.
$^\dagger$ An adjacent pair of cells with different characters is a pair of cells $(r_1, c_1)$ and $(r_2, c_2)$ ( $1 \le r_1, r_2 \le 2$ , $1 \le c_1, c_2 \le n$ ) such that $|r_1 - r_2| + |c_1 - c_2| = 1$ and the characters in $(r_1, c_1)$ and $(r_2, c_2)$ are different.
He has already filled in the first row of the grid and would like you to fill in the second row. You must do so in a way such that the number of adjacent pairs of cells with different characters $^\dagger$ is equal to $k$ . If it is impossible, report so.
$^\dagger$ An adjacent pair of cells with different characters is a pair of cells $(r_1, c_1)$ and $(r_2, c_2)$ ( $1 \le r_1, r_2 \le 2$ , $1 \le c_1, c_2 \le n$ ) such that $|r_1 - r_2| + |c_1 - c_2| = 1$ and the characters in $(r_1, c_1)$ and $(r_2, c_2)$ are different.
输入格式
The first line consists of an integer $t$ , the number of test cases ( $1 \leq t \leq 1000$ ). The description of the test cases follows.
The first line of each test case has two integers, $n$ and $k$ ( $1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 3 \cdot n$ ) – the number of columns of the matchstick, and the number of adjacent pairs of cells with different characters required.
The following line contains string $s$ of $n$ characters ( $s_i$ is either A or B) – Miriany's top row of the matchstick.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case has two integers, $n$ and $k$ ( $1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 3 \cdot n$ ) – the number of columns of the matchstick, and the number of adjacent pairs of cells with different characters required.
The following line contains string $s$ of $n$ characters ( $s_i$ is either A or B) – Miriany's top row of the matchstick.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, if there is no way to fill the second row with the number of adjacent pairs of cells with different characters equals $k$ , output "NO".
Otherwise, output "YES". Then, print $n$ characters that a valid bottom row for Miriany's matchstick consists of. If there are several answers, output any of them.
Otherwise, output "YES". Then, print $n$ characters that a valid bottom row for Miriany's matchstick consists of. If there are several answers, output any of them.
输入输出样例
输入 #1
4 10 1 ABBAAABBAA 4 5 AAAA 9 17 BAAABBAAB 4 9 ABAB
输出 #1
NO YES BABB YES ABABAABAB NO
In the first test case, it can be proved that there exists no possible way to fill in row $2$ of the grid such that $k = 1$ .
For the second test case, BABB is one possible answer.
The grid below is the result of filling in BABB as the second row.
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{array}$ The pairs of different characters are shown below in red:
$\begin{array}{|c|c|} \hline \color{red}{A} & A & A & A \cr \hline \color{red}{B} & A & B & B \cr \hline \end{array}$ —————————————————
$\begin{array}{|c|c|} \hline A & A & \color{red}{A} & A \cr \hline B & A & \color{red}{B} & B \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & \color{red}{A} \cr \hline B & A & B & \color{red}{B} \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline \color{red}{B} & \color{red}{A} & B & B \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & \color{red}{A} & \color{red}{B} & B \cr \hline \end{array}$
There are a total of $5$ pairs, which satisfies $k$ .
For the second test case, BABB is one possible answer.
The grid below is the result of filling in BABB as the second row.
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{array}$ The pairs of different characters are shown below in red:
$\begin{array}{|c|c|} \hline \color{red}{A} & A & A & A \cr \hline \color{red}{B} & A & B & B \cr \hline \end{array}$ —————————————————
$\begin{array}{|c|c|} \hline A & A & \color{red}{A} & A \cr \hline B & A & \color{red}{B} & B \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & \color{red}{A} \cr \hline B & A & B & \color{red}{B} \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline \color{red}{B} & \color{red}{A} & B & B \cr \hline \end{array}$
—————————————————
$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & \color{red}{A} & \color{red}{B} & B \cr \hline \end{array}$
There are a total of $5$ pairs, which satisfies $k$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted