题解：CF2094D Tung Tung Sahur

· · 题解

一道字符串遍历的问题。先看范围是 n\le2\times10^5，所以不能暴力枚举每一个打击是否是双响。仔细观察后会发现，当字符串 p 中出现一段一样的字符，比如 LLL 时，s 里也会相应地出现若干个 L。我们称这两段字符串为对应字符串。你会发现对于 s 上的对应字符串，我们有两个限制：一是它不能小于 p 上的对应字符串，因为每一次打击至少产生一次声响；二是相对的，它不能大于 p 上的对应字符串的长度的两倍，因为每一次打击至多产生两次声响。

察觉到以上规律以后，我们可以定义两个指针，两个指针从左往右扫到一段重复字符的末尾，然后进行长度比较。如果不符合上述限制，就输出 NO。当整个字符串遍历完以后都没出现问题，就是 YES。

代码如下（其实有些地方可以优化一下，但是影响不大）：

#include<bits/stdc++.h>
using namespace std;
const int N=805;
int t,n,m,k,l,r,flg;
int a[N][N],book[2*N];
string s,p;
queue<int> q;
int main()
{
   cin>>t;
    while(t--)
    {
        cin>>p>>s;
        n=p.size(),m=s.size();
        p='0'+p,s='0'+s,l=1,r=1,flg=0;
        int lcnt=0,rcnt=0;
        while(l<=n&&r<=m)
        {
            while(l<=n&&p[l]=='L') l++,lcnt++;
            while(r<=m&&s[r]=='L') r++,rcnt++;
            if(!(lcnt<=rcnt&&rcnt<=lcnt*2)) break;
            lcnt=0,rcnt=0;
            while(l<=n&&p[l]=='R') l++,lcnt++;
            while(r<=m&&s[r]=='R') r++,rcnt++;
            if(!(lcnt<=rcnt&&rcnt<=lcnt*2)) break;
            lcnt=0,rcnt=0;
            if(l>n&&r>m) flg=1;
        }
        if(flg) cout<<"YES\n";
        else cout<<"NO\n";
    }
   return 0;
}