首页 > 试题广场 >

小红的01串

[编程题]小红的01串

小红拿到了一个01串，她每次可以选择一个长度为2的连续子串取反（0变1，1变0），她想知道，是否能在有限的操作次数内使得所有字符相同？
共有 $q$ 组询问。

第一行输入一个正整数，代表询问次数。
每次询问输入一个字符串，仅由'0'和'1'组成。
所有字符串长度之和不超过200000。

对于每次询问，如果该字符串可以通过有限的操作使得所有字符相同，则输出"Yes"，否则输出"No"。

示例1

输入

Yes
Yes
No

第一组询问，先对前两个字符操作，变成"011"，然后对后两个字符操作，变成"000"。
第二组询问，不需要任何操作。
第三组询问，显然无法通过有效的操作次数使得所有字符相等。

算法知识视频讲解

想吃火锅的大卫在求佛

第一类操作：00 11 其实是可以0/1随意切换

第二类操作：01 10 就是交换位置，也就是把0或1往某个方向驱赶

所以无论串是什么样的，都可以只执行第二类操作把0和1分别驱赶到两端，一端为0，另一端为1

000...01...1111 最后达到这种效果，因为只是对0/1做驱赶，所以0和1的数量均没有发生变化。

最后观察

000...01...1111

很容易得到结论，0的个数如果是奇数并且1的个数也是奇数就不行（如果1的个数是偶数那就全部1变0，如果0的个数是偶数就全部变成1）

0或1当中只要是有一方的个数是偶数都可以通过第一类操作变成对方从而完成变换。

发表于 2025-06-27 12:00:08 回复(1)

提交观点

难度：

1条回答 26收藏 105浏览

小红的01串

扫一扫，把题目装进口袋