P9184 [USACO23OPEN] Moo Language B 题解

KidA · 2023-10-09 20:56:53 · 题解

恶♂趣♂味♂大♂模♂拟♂。

首先是构造语句部分：

• 开始肯定是尽可能地多用上不及物语句和及物语句；

• 接着，因为及物语句的单词数量一定比不及物语句多，所以贪心地尽可能多地将不及物语句改为及物语句；

• 然后，为了增加语句长度，再次贪心地在及物语句中尽可能多地添加名词和逗号即可。

接下来是输出部分：

• 对于一个语句中的单词，若其编号 \ge 1，则需要输出空格；若其编号 \ge 3，则需要输出逗号；

• 对于不是最后一句的语句，若它还能够与其他语句通过连词相连，则使用一个连词。

代码：

void solve(){
    //读入与初始化
    cin>>n>>c>>p,sum=tot=ttot=0;
    for(int i=0;i<4;i++) a[i].clear();
    for(int i=1;i<=n;i++){
        string s,op; cin>>s>>op;
        if(op[0]=='n') a[0].push_back(s);
        else if(op[0]=='t') a[1].push_back(s);
        else if(op[0]=='i') a[2].push_back(s);
        else a[3].push_back(s);
    }

    p+=min(p,(int)(a[3].size())); //计算语句总数
    for(;a[0].size()&&a[2].size()&&tot<p;sum+=2){ //使用不及物语句
        ans[++tot]=a[4];
        ans[tot].push_back(a[0].back()),ans[tot].push_back(a[2].back());
        a[0].pop_back(),a[2].pop_back();
    }
    for(ttot=tot;a[0].size()>=2&&a[1].size()&&tot<p;sum+=3){ //使用及物语句
        ans[++tot]=a[4];
        ans[tot].push_back(a[0].back()),ans[tot].push_back(a[1].back());
        a[0].pop_back(),a[1].pop_back();
        ans[tot].push_back(a[0].back());
        a[0].pop_back();
    }
    for(;ttot&&a[0].size()&&a[1].size();ttot--,sum++){  //尽量用及物语句替代不及物语句
        ans[ttot].pop_back();
        ans[ttot].push_back(a[1].back()),ans[ttot].push_back(a[0].back());
        a[0].pop_back(),a[1].pop_back();
    }
    for(;ttot!=tot&&a[0].size()&&c;c--,sum++) //添加名词和逗号
        ans[tot].push_back(a[0].back()),a[0].pop_back();

    cout<<sum+min(tot/2,(int)(a[3].size()))<<'\n'; //输出语句总数
    for(int i=1;i<=tot;i++){
        for(int j=0;j<ans[i].size();j++){
            if(j>2) cout<<',';
            if(j) cout<<' ';
            cout<<ans[i][j];
        }
        if(i<tot){
            if(i%2&&a[3].size()) //若能够使用连词
                cout<<' '<<a[3].back()<<' ',a[3].pop_back();
            else cout<<". ";
        }
    }
    if(sum) cout<<".\n"; //若有答案才输出句号
}