专栏文章

题解 CF2094D

HHYdroKomide
CF2094D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipgbzt0
此快照首次捕获于
2025/12/03 11:33
3 个月前
此快照最后确认于
2025/12/03 11:33
3 个月前
查看原文

题意

给定一个 0-1 串，可以选择其中一些位置的数字变成两个并且放回原处。问一个串 pp 是否可以变成 ss。

思路

考虑对于这两个串分连续段，每段由 00 或者 11 组成。显然这两个串能分成的段数一定相同，同时这些段都是一一对应的。
那么对于在 pp 和 ss 中对应的同一段，ss 的段长度最大是 pp 中此段长度的两倍，此时所有 pp 中此段的数字都变成了两个。最小是 pp 中此段的长度，此时 pp 中此段数字都未翻倍。而在这两个长度之间的任何值都是合法的，否则为非法。
模拟判断即可，注意边界的特殊处理。
思考题：假设所有位数字都有 kk 的概率变成两个，求 ss 可以变成 pp 的概率。

程序如下

CPP
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+5;
int T,n;
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		string p,s;
		cin>>p>>s;
		int curs=0;
		bool flag=true;
		for(int i=0;i<p.size();i++){
			int stp=i,sts=curs;
			if(s[curs]!=p[i]){
				flag=false;
				break;
			}
			while(i!=p.size()-1&&p[i]==p[i+1])i++;
			int lenp=i-stp+1;
			while(curs!=s.size()-1&&s[curs]==s[curs+1])curs++;
			int lens=curs-sts+1;
			if(lenp>lens||(lenp<<1)<lens){
				flag=false;
				break;
			}
			curs++;
		}
		if(curs!=s.size())flag=false;
		if(flag)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

THE END

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...