Moo Language (USACO Bronze 2023 US Open)

此题总体上是一个比较繁琐的模拟题，规则有一些隐蔽，需要较高的思维能力。

问题要求我们按照一批规则，造出一系列句子，以使用最多的单词为目标。

首先可以看到，句号和连词的数量限制了句子的最大数量。设 $s$ 为句子的总数量， $p$ 为句号数， $o$ 为连词数，则： $s=p+min(p,o)$

接下来我们比较理想的目标，是找到一个规律，可以直接生成有多少个及物动词的句子，多少个非及物动词的句子，多少个逗号这样一套完整的方案。但经过一番搜索之后，发现并不好确定这样的规律。但我们仔细观察，应该可以发现一个规律，就是最佳的答案一定是句子数量最多的，因为在可行的情况下，增加句子只带来结果更优，而不会更差：句子数量直接决定动词和连词的数量，所以句子越多，动词和连词使用越多。而对于名词，如果名词数量不足，那么多使用不及物动词，就可以使得使用完所有名词之后，动词数量和句子数量同时达到最大，这是更优的。而如果名词数量充足，则可以多使用及物动词，同时达到最大的句子数量，此时也不会出现句子少比句子多更优的情况。

有了这个规律之后，我们就可以大体分两部完成生成过程，第一步生成尽量多的句子。第二步固定住句子数量，通过更换一些词，来使得单词数量达到最优：

先尽量多的用不及物动词，这样可以造出尽量多的句子。
然后再尽量多的用及物动词，直到名词用完，或者及物动词用完。
然后如果此时还有剩下的名词以及及物动词（因为最上面的语句最大数量限制），则尽量将不及物动词语句替换成及物动词的句子，这样可以消耗更多单词。
由于逗号可以和名词一一搭配，所以把他们加入一个及物动词语句内。
连词要尽量多使用，所以第0、2、4...句子后面要加上连词，直到用完所有连词。

最后，统计词数，输出所有语句。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, N;
int C, P;
 
int cn, ci, ct, cc;
vector<string> noun;
vector<string> iv;
vector<string> tv;
vector<string> conj;
vector<string> ans[2005];
 
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &N, &C, &P);
        noun.clear(); iv.clear(); tv.clear(); conj.clear();
        for (int i = 0; i < N; i++) {
            char s[15], typ[20];
            scanf("%s %s", s, typ);
            if (typ[0] == 'n') {
                noun.push_back(s);
            } else if (typ[0] == 't') {
                tv.push_back(s);
            } else if (typ[0] == 'i') {
                iv.push_back(s);
            } else {
                conj.push_back(s);
            }
        }
        cn = noun.size(); ci = iv.size(); ct = tv.size(); cc = conj.size();
 
        int s = P+min(P,cc);
        int sum = 0;
        int h = 0;
        for (; noun.size() && iv.size() && h < s; h++) {    // 尽量用不及物动词
            ans[h].clear();
            ans[h].push_back(noun.back()); noun.pop_back();
            ans[h].push_back(iv.back());   iv.pop_back();
            sum += 2;
        }
        for (; noun.size() >= 2 && tv.size() && h < s; h++) {    // 尽量用及物动词
            ans[h].clear();
            ans[h].push_back(noun.back()); noun.pop_back();
            ans[h].push_back(tv.back());   tv.pop_back();
            ans[h].push_back(noun.back()); noun.pop_back();
            sum += 3;
        }
        for (int i = 0; i < h && noun.size() && tv.size(); i++) {  // 用及物动词替换不及物动词
            if (ans[i].size() == 2) {
                ans[i].pop_back();
                ans[i].push_back(tv.back());   tv.pop_back();
                ans[i].push_back(noun.back()); noun.pop_back();
                sum++;
            }
        }
        for (int i = 0; i < h; i++)                         // 用逗号加入更多名词
            if (ans[i].size() == 3) {
                while (noun.size() && C) {
                    ans[i].push_back(noun.back());
                    noun.pop_back();
                    C--;
                    sum++;
                }
                break;
            }
        printf("%d\n", sum + min(h/2, cc));
        for (int i = 0; i < h; i++) {
            if (i) printf(" ");
            for (int j = 0; j < ans[i].size(); j++) {
                printf("%s", ans[i][j].c_str());
                if (j < ans[i].size()-1) 
                    if (j >= 2)
                        printf(", ");
                    else
                        printf(" ");
            }
            if (i % 2 == 0 && i != h-1 && conj.size()) {
                printf(" %s", conj.back().c_str());
                conj.pop_back();
            } else printf(".");
        }
        printf("\n");
    }
    return 0;
}