小红的01串【牛客tracker 每日一题】

小红的01串

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

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

输入描述：

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

输出描述：

对于每次询问，如果该字符串可以通过有限的操作使得所有字符相同，则输出"Y e s YesYes“，否则输出”N o NoNo"。

示例1

输入：

3 101 1111 1011

输出：

Yes Yes No

说明：

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

解题思路

首先分析操作特性，每次对长度为2 22的连续子串取反，仅会改变0 00或1 11的数量的偶数增减（如00 0000变11 1111时0 00减2 22、1 11加2 22），不会改变0 00和1 11数量的奇偶性；要使所有字符相同，需让0 00或1 11的数量变为0 00，这要求初始时0 00和1 11的数量不能同时为奇数（否则奇偶性不变，无法让其一数量变为0 00）。因此解题时统计每个字符串中0 00和1 11的数量，若两者均为奇数则输出N o NoNo，否则输出Y e s YesYes；该方法无需模拟操作过程，仅通过奇偶性判断，时间复杂度为O ( l e n ( s ) ) O(len(s))O(len(s))，适配所有字符串长度之和≤ 2 e 5 ≤2e5≤2e5的规模，高效且精准地判断是否可通过有限操作使所有字符相同。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e6+10;intmain(){ll t;cin>>t;while(t--){string s;cin>>s;ll cnt[]={0,0};for(char&c:s)cnt[c-'0']++;cout<<(cnt[0]&cnt[1]&1?"No\n":"Yes\n");}return0;}