题解 CF2094D

· · 题解

题意

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

思路

考虑对于这两个串分连续段，每段由 0 或者 1 组成。显然这两个串能分成的段数一定相同，同时这些段都是一一对应的。

那么对于在 p 和 s 中对应的同一段，s 的段长度最大是 p 中此段长度的两倍，此时所有 p 中此段的数字都变成了两个。最小是 p 中此段的长度，此时 p 中此段数字都未翻倍。而在这两个长度之间的任何值都是合法的，否则为非法。

模拟判断即可，注意边界的特殊处理。

思考题：假设所有位数字都有 k 的概率变成两个，求 s 可以变成 p 的概率。

程序如下

#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