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

点击量：196

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

目录

题目描述

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

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

输入输出描述

输入描述:

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

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

第二行是一个由F和L组成的字符串\(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;
}