Moo Language

GitHub 跳转原题关系图返回列表

枚举一类句和二类句数量，最大化可用连接词和逗号扩展名词后构造段落。

OJ: usaco

题目 ID: 1324

难度:普及/提高-

标签:构造枚举模拟字符串usaco

日期: 2026-07-11 16:31

题意

给定一个词库，单词分为四类：

名词 noun
及物动词 transitive-verb
不及物动词 intransitive-verb
连接词 conjunction

可以使用的标点只有逗号和句号，数量分别为 $C$ 和 $P$ 。

合法句子有两种：

一类句：名词 + 不及物动词
二类句：名词 + 及物动词 + 名词列表

两个句子可以用一个连接词合成一个复合句，但复合句不能继续合并。每个句子或复合句最后都要有句号。

要求构造一个合法段落，使使用的单词数量最大，并输出最大单词数和任意一个合法段落。

思路

先看一个小数据暴力，它直接枚举一类句、二类句、连接词和额外名词数量：

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:31
 * update_at: 2026-07-11 16:35
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int T;
int n, comma_cnt, period_cnt;
int noun_cnt, trans_cnt, intrans_cnt, conj_cnt;
vector<string> nouns;
vector<string> trans_verbs;
vector<string> intrans_verbs;
vector<string> conjs;

string take_word(vector<string> &words) {
    string res = words.back();
    words.pop_back();
    return res;
}

void construct_output(int best_words, int best_type1, int best_type2, int best_combine, int best_extra) {
    cout << best_words << '\n';
    if (best_words == 0) {
        cout << '\n';
        return;
    }

    vector<string> basic_sentences;
    for (int i = 1; i <= best_type1; i++) {
        basic_sentences.push_back(take_word(nouns) + " " + take_word(intrans_verbs));
    }
    for (int i = 1; i <= best_type2; i++) {
        basic_sentences.push_back(take_word(nouns) + " " + take_word(trans_verbs) + " " + take_word(nouns));
    }

    if (best_extra > 0) {
        int last = (int)basic_sentences.size() - 1;
        for (int i = 1; i <= best_extra; i++) {
            basic_sentences[last] += ", " + take_word(nouns);
        }
    }

    vector<string> final_sentences;
    int idx = 0;
    for (int i = 1; i <= best_combine; i++) {
        final_sentences.push_back(basic_sentences[idx] + " " + take_word(conjs) + " " + basic_sentences[idx + 1] + ".");
        idx += 2;
    }
    while (idx < (int)basic_sentences.size()) {
        final_sentences.push_back(basic_sentences[idx] + ".");
        idx++;
    }

    for (int i = 0; i < (int)final_sentences.size(); i++) {
        if (i > 0) cout << ' ';
        cout << final_sentences[i];
    }
    cout << '\n';
}

void solve_one() {
    int best_words = 0;
    int best_type1 = 0;
    int best_type2 = 0;
    int best_combine = 0;
    int best_extra = 0;

    // 小数据暴力：枚举一类句、二类句、连接词和额外名词数量。
    for (int type1 = 0; type1 <= intrans_cnt; type1++) {
        for (int type2 = 0; type2 <= trans_cnt; type2++) {
            for (int combine = 0; combine <= conj_cnt; combine++) {
                for (int extra = 0; extra <= comma_cnt; extra++) {
                    if (type1 + 2 * type2 + extra > noun_cnt) continue;
                    if (extra > 0 && type2 == 0) continue;

                    int sentence_cnt = type1 + type2;
                    if (combine > sentence_cnt / 2) continue;
                    if (sentence_cnt - combine > period_cnt) continue;

                    int words = 2 * type1 + 3 * type2 + combine + extra;
                    if (best_words < words) {
                        best_words = words;
                        best_type1 = type1;
                        best_type2 = type2;
                        best_combine = combine;
                        best_extra = extra;
                    }
                }
            }
        }
    }

    construct_output(best_words, best_type1, best_type2, best_combine, best_extra);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> comma_cnt >> period_cnt;
        noun_cnt = trans_cnt = intrans_cnt = conj_cnt = 0;
        nouns.clear();
        trans_verbs.clear();
        intrans_verbs.clear();
        conjs.clear();
        for (int i = 1; i <= n; i++) {
            string word, type;
            cin >> word >> type;
            if (type == "noun") {
                noun_cnt++;
                nouns.push_back(word);
            } else if (type == "transitive-verb") {
                trans_cnt++;
                trans_verbs.push_back(word);
            } else if (type == "intransitive-verb") {
                intrans_cnt++;
                intrans_verbs.push_back(word);
            } else {
                conj_cnt++;
                conjs.push_back(word);
            }
        }

        solve_one();
    }

    return 0;
}

正解也可以沿用这个思路，只是枚举范围本身已经足够小。设：

type1：一类句数量。
type2：基础二类句数量，每个基础二类句用 名词 + 及物动词 + 名词。
combine：用连接词合并的句子对数。
extra：接到某个二类句后面的额外名词数量，每个额外名词需要一个逗号。

对于固定的 type1 和 type2：

text

1
2
3需要名词数 = type1 + 2 * type2
基础单词数 = 2 * type1 + 3 * type2
基础句子数 = type1 + type2

连接词最多能合并 $floor(基础句子数 / 2)$ 对句子，同时不能超过词库中的连接词数量。

合并后需要的句号数为：

text

1基础句子数 - combine

如果句号不够，这个方案不可行。

如果至少有一个二类句，还可以把剩余名词用逗号接到最后一个二类句后面。额外名词数量为：

text

1min(剩余名词数, C)

于是当前方案使用单词数为：

text

12 * type1 + 3 * type2 + combine + extra

枚举所有 type1 和 type2，记录单词数最大的方案。

构造时：

先生成所有一类句。
再生成所有基础二类句。
如果有额外名词，把它们用逗号接到最后一个二类句后面。
把前 $2 * combine$ 个基础句两两用连接词合并。
剩下的基础句直接加句号输出。

代码

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:31
 * update_at: 2026-07-11 16:35
 */
#include <bits/stdc++.h>
using namespace std;

vector<string> nouns;
vector<string> trans_verbs;
vector<string> intrans_verbs;
vector<string> conjs;

int T;
int n, comma_cnt, period_cnt;

string take_word(vector<string> &words) {
    string res = words.back();
    words.pop_back();
    return res;
}

void solve_one() {
    cin >> n >> comma_cnt >> period_cnt;

    nouns.clear();
    trans_verbs.clear();
    intrans_verbs.clear();
    conjs.clear();

    for (int i = 1; i <= n; i++) {
        string word, type;
        cin >> word >> type;
        if (type == "noun") {
            nouns.push_back(word);
        } else if (type == "transitive-verb") {
            trans_verbs.push_back(word);
        } else if (type == "intransitive-verb") {
            intrans_verbs.push_back(word);
        } else {
            conjs.push_back(word);
        }
    }

    int noun_total = (int)nouns.size();
    int trans_total = (int)trans_verbs.size();
    int intrans_total = (int)intrans_verbs.size();
    int conj_total = (int)conjs.size();

    int best_words = 0;
    int best_type1 = 0;
    int best_type2 = 0;
    int best_combine = 0;
    int best_extra = 0;

    for (int type1 = 0; type1 <= intrans_total; type1++) {
        for (int type2 = 0; type2 <= trans_total; type2++) {
            int used_nouns = type1 + 2 * type2;
            if (used_nouns > noun_total) continue;

            int sentence_cnt = type1 + type2;
            int combine = min(conj_total, sentence_cnt / 2);
            int need_period = sentence_cnt - combine;
            if (need_period > period_cnt) continue;

            int extra = 0;
            if (type2 > 0) {
                extra = min(comma_cnt, noun_total - used_nouns);
            }

            int words = 2 * type1 + 3 * type2 + combine + extra;
            if (words > best_words) {
                best_words = words;
                best_type1 = type1;
                best_type2 = type2;
                best_combine = combine;
                best_extra = extra;
            }
        }
    }

    cout << best_words << '\n';
    if (best_words == 0) {
        cout << '\n';
        return;
    }

    vector<string> basic_sentences;

    for (int i = 1; i <= best_type1; i++) {
        string sentence = take_word(nouns) + " " + take_word(intrans_verbs);
        basic_sentences.push_back(sentence);
    }

    for (int i = 1; i <= best_type2; i++) {
        string sentence = take_word(nouns) + " " + take_word(trans_verbs) + " " + take_word(nouns);
        basic_sentences.push_back(sentence);
    }

    if (best_extra > 0) {
        int last = (int)basic_sentences.size() - 1;
        for (int i = 1; i <= best_extra; i++) {
            basic_sentences[last] += ", " + take_word(nouns);
        }
    }

    vector<string> final_sentences;
    int idx = 0;
    for (int i = 1; i <= best_combine; i++) {
        string sentence = basic_sentences[idx] + " " + take_word(conjs) + " " + basic_sentences[idx + 1] + ".";
        final_sentences.push_back(sentence);
        idx += 2;
    }
    while (idx < (int)basic_sentences.size()) {
        final_sentences.push_back(basic_sentences[idx] + ".");
        idx++;
    }

    for (int i = 0; i < (int)final_sentences.size(); i++) {
        if (i > 0) cout << ' ';
        cout << final_sentences[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

设词库大小为 $N$ 。

枚举 type1 和 type2 的复杂度为 $O(N^2)$ ，构造输出为 $O(N)$ 。

空间复杂度为 $O(N)$ 。

总结

本题的难点不在语法本身，而在把语法资源转成几个数量约束。

先确定最优的句子数量组合，再按组合构造段落，可以让输出细节变得可控。

1324 Moo Language

赛事信息

USACO 2023 US Open Contest, Bronze

题目描述

Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language! Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next. A sentence needs to follow one of the following formats:

Type 1: noun + intransitive verb.
Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun. Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period. Farmer John has a word bank of $N$ words, $C$ commas, and $P$ periods ( $1 \leq P,C\le N \leq 10^3$ ). He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words. Each input file contains $T$ ( $1\le T\le 100$ ) independent instances of this problem.

输入格式

The first line contains $T$ , the number of instances. Each instance is specified as follows: The first line consists of three integers, $N$ , $C$ , and $P$ . The $N$ following lines will consist of two strings. The first string will be the word itself that FJ can use (a string of at least 1 and at most 10 lowercase letters), and the second string will be either one of the following: noun, transitive-verb, intransitive-verb, or conjunction, denoting the type of the word. It is possible the same word occurs more than once in FJ’s word bank, but it will always have the same type each time it appears.

输出格式

In the first line, output the maximum possible number of words. In the second line, output any sequence of sentences with the maximum possible number of words. Any valid sequence will be accepted. The grader is sensitive to whitespace, so make sure not to output any extraneous spaces, particularly at the end of each line.

输入输出样例 #1

输入 #1

text

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
38
393
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

输出 #1

text

1
2
3
4
5
60

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

样例说明

For the first test case, the only valid sequence is the empty sequence. For each of the next two test cases, it is possible to construct a sequence of sentences using every word from the word bank except for one.

测试点性质

Inputs 2-6: $N\le 10$
Inputs 7-11: $N\le 100$
Inputs 12-16: $N\le 1000$
Inputs with remainder 2 when divided by 5: There are no transitive verbs.
Inputs with remainder 3 when divided by 5: There are no intransitive verbs.
Inputs with remainder 4 when divided by 5: There are no conjunctions.

Moo Language

目录

题意

思路

代码

复杂度

总结