CF1861B Two Binary Strings

One_JuRuo · 2023-09-01 23:56:08 · 题解

思路

最近熬夜打 CF，视力下降了。没看到题目里给了第一位和最后一位必定是 0 和 1，导致想了半天。

考虑枚举字符串的位置 i。

首先如果遇到了两个串第 i 位都是 1，那么可以直接覆盖中间的片段，一定能成功。

如果遇到不同的位置，考虑找到最近的 0 与第一位的 0 做操作，选最近的是为了减少损失相同 1 的可能。如果找不到就肯定无解。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,flag,xz;
char s1[5005],s2[5005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",s1+1,s2+1),n=strlen(s1+1),flag=0;
        for(int i=1;i<=n;++i)
        {
            if(s1[i]=='1'&&s2[i]=='1'){break;}
            if(s1[i]!=s2[i])
            {
                int ff=0;
                for(int j=i+1;j<n;++j)
                    if(s1[j]==s2[j]&&s1[j]=='0')
                    {
                        ff=1,i=j;break;
                    }
                if(!ff)
                {
                    flag=1;break;
                }
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}