牛客176A 染色 题解【贪心】【字符串】

作者: wjyyy 分类: 字符串,解题报告,贪心 发布时间: 2018-11-05 14:39

点击量:22

 

    我好像又理解错题意了……或者说“有点莽”……

 

题目描述

fizzydavid和leo有\(n\)个方格排成一排,每个方格初始是白色。fizzydavid有红色染料,leo有蓝色染料。他们共进行了\(m\)次操作,在每次操作中,fizzydavid或者leo会选择若干个(可以是零个)连续相邻的方格并用自己的染料给这些格子染色。当一个格子被染成某个颜色时,这种染料会覆盖之前这个格子上的颜色。

现在你并不知道他们每次操作选择了哪些格子,只知道每次操作是谁进行的,以及最终这\(n\)个方格的颜色。你需要判断是否存在某种选择格子的方式使得操作完之后\(n\)个方格的颜色与给定的相同。你还发现,\(n\)个格子最终都不是白色。

输入输出描述

输入描述:

第一行包含一个整数\(T\),表示本组数据共有\(T\)组测试点。

对每组测试点的第一行是一个由RB组成的字符串\(s\)表示最终格子的颜色。R表示红色,B表示蓝色,同时字符串的长度为\(n\)。

第二行是一个由FL组成的字符串\(t\)表示\(m\)次操作,F表示某次是fizzydavid操作,L表示是leo操作,同时字符串的长度为\(m\)。

输出描述:

对每组测试点输出一行,如果满足条件输出Yes否则输出No

样例1

输入样例:

3
R
FL
RRRBR
FFFF
BRRBBRB
LFL

输出样例:

Yes
No
Yes

样例1说明

对第一个测试点,第二次操作可以是空的。

对第二个测试点,\(s\)中有B,但是\(t\)中没有L,因此不合法。

对第三个测试点,BBBBBBB->BRRRRRB->BRRBBRB就是合法的。

数据规模与约定

所有数据满足\(T\le 20\)。

\(50\%\)的数据满足\(n,m\le 15\),

\(80\%\)的数据满足\(n,m\le 100\),

\(100\%\)的数据满足\(n,m\le 100000\)。

题解:

    一开始想了个结论,就是可以把两个字符串“缩”一下,也就是把同种字母串变成一个字符。这个操作对于颜色串肯定是没有问题的,但是对于操作串就会有影响。但是我还是直接做了交上去爆零orz。

    当操作串连续出现相同字母时,多个字母可以对原颜色串的不同位置进行修改,比如对于颜色串BRBRB,我现在有FF,就可以分别把两个位置上的R涂色。

    对于染色操作,我们是可以覆盖的,也就是说时间靠后的操作优先级高,那么时间靠前的操作优先级就低,修改时无论格子上有没有颜色都进行修改。我们可以把操作顺序从后往前看,其实是进行了“如果格子上有颜色则不进行修改”的变化。

    这样一来操作就变得方便了许多,我们考虑倒过来做,首先给出一个填满的颜色串和一个倒过来的操作序列,每次可以选择一个相应的颜色消掉。这个消掉的意思就是说这个位置的颜色已经定了,以后不再做出任何影响,因此可以合并这个颜色两侧的颜色。当剩余颜色\(>3\)时,选择中间的颜色块一定比两侧的优,因为消掉中间的可以减少2个块,消掉两边的只能减少一个。当剩余颜色不超过\(3\)时,需要判断当前颜色情况是下列哪一种\[\left\{\begin{matrix}\tt RBR\\\tt BRB\\\tt BR\\\tt RB\\\tt B\\\tt R\end{matrix}\right.\]

    此时对于前两种情况,消掉前后任意一个均可,对于后面四种,消去的情况唯一,此时特判剩下哪一种,最后判断是否全部清空,然后输出答案。时间复杂度\(O(Tm)\)。

Code:

#include<cstdio>
#include<cstring>
char s[100100],t[100100];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        scanf("%s",t+1);
        int cnt=0;
        for(int i=1;s[i]!='\0';++i)
        {
            s[i]=(s[i]=='R')?'F':'L';//直接化为一致,方便判断
            if(s[i]!=s[i-1])
                ++cnt;
        }
        int flag=0;
        int m=strlen(t+1);
        for(int i=m;i;--i)
            if(cnt>3)
                cnt-=2;
            else if(cnt==3)//针对最后几步需要判断
            {
                if(s[1]==t[i])//删一头
                    --cnt;
                else
                    cnt-=2;//删中间
            }
            else if(cnt==2)
            {
                if(s[1]==t[i])//删掉之后要标记剩下的是另一个
                    flag=1;
                --cnt;
            }
            else if(cnt==1)
            {
                if(!flag&&s[1]==t[i])//依据上面的标记判断
                    --cnt;
                if(flag&&s[1]!=t[i])
                    --cnt;
            }
        if(cnt)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */