[LOJ529] 自然语言

Description

符合汉语结构的字符串定义为：字符串 N 是符合条件的，把一个合法字符串中的任意一个 N 替换成 NV 或 NVN 得到的字符串都是符合条件的。

符合英语结构的字符串是这样定义的：字符串 N 是符合条件的。把一个合法字符串中的任意一个 N 替换成 NV 或 NVN 或 VN 得到的字符串都是符合条件的。

给定一个由 N,V 构成的字符串，判断它是否是合法的英语结构/汉语结构字符串。

Solution

我们发现，一个字符串符合英语结构，当且仅当其中包含 N，且不包含连续出现的 N。

一个字符串符合汉语结构，那么它一定符合英语结构。除此之外，它的开头不得是 V。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

signed main()
{
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        int a=0,b=0;
        for(auto i:s) if(i=='N') a=b=1;
        for(int i=1;i<s.length();i++) if(s[i]=='N'&&s[i-1]=='N') a=b=0;
        if(s[0]=='V') b=0;
        cout<<a<<" "<<b<<endl;
    }
}