题解：CF1404A Balanced Bitstring

找规律 + 模拟

先考虑问题的简化版：若给定的字符串只含字符 0 和 1 而无字符 ? 的干扰时该怎么做。

根据滑动窗口的思想，模拟一下不难发现若有解则一定满足

\forall i \in [1,n],s_i=s_{i \bmod k}

，即字符串一定存在一个长度为

k

的循环节。

所以我们只需要判定一下字符串是否以

k

作为周期。那么直接用周期第一段中的每个位置与其相关联的所有位置比较即可，若对于周期第一段满足，则整个字符串有解。

接下来回到本题：当存在字符 ? 的影响时该这么做。

其实也不复杂，还是根据周期第一段来枚举所有相隔

k

的倍数的位置判定是否相等。若当前考虑到周期第一段的一个位置

i

，该位置字符为 ?，且与之相关联的位置存在不为 ? 的字符，则考虑直接将第一段的位置

i

对应的字符 ? 进行替换。最后，若在找遍整个串中所有与

i

相关联的位置前，存在某个相关联的位置与

i

位置的字符不相同，则说明存在冲突，输出无解。

当然还有一个情况，若周期第一段的一个位置

i

对应的字符最后还是 ?，即位置

i

并没有通过与之相关联位置替换为具体的字符 0 或 1，那么我们就需要考虑一下周期第一段的这个字符 ? 能否通过合理的构造使得符合题意。

也就是要考虑周期第一段是否满足字符 0 和字符 1 的个数相等。

如果周期第一段已经不存在字符 ?，且满足字符 0 与字符 1 的个数相等，有。
如果周期第一段存在字符 ? 且个数为 $cnt$ ，且周期第一段中字符 0 与字符 1 之间还需要再添加 $diff$ 个字符才能使得字符 0 和字符 1 个数相等，则当 $cnt-diff$ 为偶数时有解。

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
int n,k;
void solve(){
	cin>>n>>k;
	string s;
	cin>>s;
	s=" "+s;
	rep(i,1,k){
		for(int j=i;j<=n;j+=k){
			if(s[i]=='?' && s[j]!='?') s[i]=s[j];
			else if(s[i]!='?' && s[j]!='?' && s[i]!=s[j]) return cout<<"NO",void();
		}
	}
	int cnt0=0,cnt1=0,cnt2=0;
	rep(i,1,k){
		if(s[i]=='0') cnt0++;
		else if(s[i]=='1') cnt1++;
		else cnt2++;
	}
	if(!cnt2 && cnt0==cnt1) return cout<<"YES",void();
	if(cnt2>=abs(cnt0-cnt1) && (cnt2-abs(cnt0-cnt1))%2==0) return cout<<"YES",void();
	cout<<"NO";
}

题解：CF1404A Balanced Bitstring

文章操作

找规律 + 模拟

相关推荐

评论

题解：CF1404A Balanced Bitstring