题解归档 - cf113A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf113A
• 本地来源：problems/cf113A/idea.md
• 题目链接：https://codeforces.com/contest/113/problem/A
• 原始标题：cf113A — Grammar Lessons

思路

cf113A — Grammar Lessons

题意

Petya 语言每个词属于三类词性之一（形容词、名词、动词），各有阴阳性，对应 6 种固定后缀：

整行文本是恰好一个句子当且仅当：

1. 每个词都能识别为上述六种之一（按较长后缀优先匹配，避免 etra 被误判为 etr）；
2. 要么只有一个词；要么多个词构成 statement：形容词* + 名词 + 动词*，且所有词同性别。

否则输出 NO。

做法

逐词分类（tp 返回 1–6），状态机：

• ph=0：尚未见到名词，可出现形容词或名词；
• 见到名词后 ph=1，只允许动词；
• 名词计数 cntn 必须最终为 1（多词时）。

同时维护全局性别 gen（奇数类型为阳，偶数为阴）。

复杂度

词数 ≤ 10⁵（总字符），逐词 O(长度)，总 O(总字符)。

验证

• 样例 + 官方三例手测；
• stress.py 等价流程 500 组（gen 随机合法后缀词串 vs brute）。

代码

来源：problems/cf113A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:10:36
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
vector<string>w;
ll pd,tp,i,j,k,cnt,gen,found;
bool ends(string a,string b){
    if((ll)a.size()<(ll)b.size()) return 0;
    return a.substr(a.size()-b.size())==b;
}
ll classify(string a){
    if(ends(a,"liala")) return 1;
    if(ends(a,"lios")) return 0;
    if(ends(a,"etra")) return 3;
    if(ends(a,"etr")) return 2;
    if(ends(a,"inites")) return 5;
    if(ends(a,"initis")) return 4;
    return -1;
}
ll getgen(ll x){
    if(x==0 or x==2 or x==4) return 0;
    return 1;
}
ll gettp(ll x){
    if(x==0 or x==1) return 0;
    if(x==2 or x==3) return 1;
    return 2;
}
int main(){
    getline(cin,s);
    for(i=0;i<(ll)s.size();){
        j=i;
        while(j<(ll)s.size() and s[j]!=' ') j++;
        w.push_back(s.substr(i,j-i));
        i=j+1;
    }
    gen=-1;
    found=0;
    cnt=0;
    for(i=0;i<(ll)w.size();i++){
        tp=classify(w[i]);
        if(tp==-1){
            cout<<"NO\n";
            return 0;
        }
        if(gen==-1) gen=getgen(tp);
        else if(getgen(tp)!=gen){
            cout<<"NO\n";
            return 0;
        }
        if(gettp(tp)==1){
            cnt++;
            if(cnt>1){
                cout<<"NO\n";
                return 0;
            }
            found=1;
        }else if(gettp(tp)==0){
            if(found){
                cout<<"NO\n";
                return 0;
            }
        }else if(!found and (ll)w.size()>1){
            cout<<"NO\n";
            return 0;
        }
    }
    if((ll)w.size()>1 and !cnt){
        cout<<"NO\n";
        return 0;
    }
    cout<<"YES\n";
    return 0;
}