K.Haitang and Ava(模拟)

时间复杂度：$O(|S|)$

题意

    给定一个字符串$S$，有如下几个构造操作：

  • 起始该字符串为空
  • 转换为$S+ava$或者$ava+S$
  • 转换为$S+avava$或者$avava+S$

    可以使用无数次上述操作，给定字符串，请问字符串是否能通过上述构造操作完成？若可以，则输出”Yes”,反之则输出”No”.

数据范围

  • $3 \le |S| \le 5 \times 10^5$

  • $\sum |S| \le 5 \times 10^5$

分析

    模拟题，根据构造规则，不难发现，满足构造规则的字符串有且只有一种构造方案，因为每个$ava$ 和 $avava$ 不存在重叠。手玩样例可知，每一项的分隔标志就是连续出现两个$a$,所以只需记录连续出现两个$a$的先后位置并暴力判断(长度不超过5)子串是否符合要求即可~

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin>>t;
    while(t--){
        string str;cin >> str;
        int n = str.size();
        str = " " + str;
        bool ok = 1;
        for (int i = 1; i <= n;i++)
            if(str[i]!='a'&&str[i]!='v')
                ok = 0;
        int last = 0;
        str += "a";
        if(str[1]!='a'||str[n]!='a') //特判起始和末尾位置
            ok = 0;
        for (int i = 1; i <= n;i++){
            if(str[i]=='a'&&str[i+1]=='a'){
                if (i - last != 3 && i - last != 5)
                    ok = 0;
                else if (i - last == 3 && (str[i - 1] != 'v' || str[i - 2] != 'a'))
                    ok = 0;
                else if (i - last == 5 && (str[i - 1] != 'v' || str[i - 2] != 'a' || str[i - 3] != 'v' || str[i - 4] != 'a'))
                    ok = 0;
                if(!ok)
                    break;
                last = i; //记录出现连续两个"a"的下标
            }
            //cout << i << endl;
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}