首页 > 试题广场 >

String Covering

[编程题]String Covering
  • 热度指数：26 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小苯有一个长度为 n 的全 0 字符串 s，初始时 s_i = \texttt{`0'} 对所有 1 \leqq i \leqq n 成立。

\hspace{15pt}小苯可以进行以下操作任意次：
\hspace{23pt}\bullet\,选择两个相邻的位置 i 和 i+1\left(1 \leqq i \leqq n-1\right)，将这两个位置都变成 \texttt{`1'}。
\hspace{30pt}需要注意的是：如果一个位置在之前的操作中已经被变成 \texttt{`1'}，后来的操作仍然可以覆盖它，将其保持为 \texttt{`1'} 或再次变成 \texttt{`1'}。

\hspace{15pt}小苯希望通过若干次操作，使得字符串变成给定的目标状态 t，其中 t 是一个长度为 n，仅由字符 \texttt{`0'} 和 \texttt{`1'} 组成的字符串。
\hspace{15pt}你的任务就是判断：是否可以通过有限次操作使得字符串 s 变成目标状态 t。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n\left(1 \leqq n \leqq 5 \times 10^5\right)，表示字符串的长度。
\hspace{15pt}第二行输入一个长度为 n、仅由 \texttt{`0'} 和 \texttt{`1'} 组成的字符串 t。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 5 \times 10^5。


输出描述:
\hspace{15pt}对于每一组测试数据，新起一行。如果可以通过操作使字符串变成 t，输出 \texttt{YES}，否则输出 \texttt{NO}。
示例1

输入

3
3
110
2
01
5
01111

输出

YES
NO
YES

说明

\hspace{15pt}对于第三组测试数据：
\hspace{23pt}\bullet\,第一次变 i=2、i=3 位置，串会变成：\texttt{。
\hspace{23pt}\bullet\,第二次变 i=4、i=5 位置，串会变成：\texttt{。
\hspace{15pt}因此可达，输出 \texttt{YES}。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 56浏览

热门推荐

相关试题

String Covering

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号