大模拟

SleepinGod · 2023-10-09 17:38:00 · 题解

USACO 的模拟

题面

题目传送门

题目思路

• 逗号必定和名词放一起

• 连词要尽量多使用

• 先计算语句的总数（尽量多)，设 s 为句子的总数量， o 为连词数。 s = p + \min(p, o)

• 先尽量多的用不及物动词

• 在尽量多的用及物动词

• 由于使用及物动词可以多消耗名词，所以尽量将不及物动词语句替换成及物动词的句子

• 由于逗号可以和名词一一搭配，所以把他们加入一个及物动词语句内。

• 统计词数，输出所有语句（记得加上连词）

题目代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int t, n, c, p, sum, h, l;

vector<string> a[5], ans[N];  // 0 名词，1 连词，2 及物动词， 3 不及物动词  语句

int main() {
  for (cin >> t; t; t--, sum = h = l = 0) {
    cin >> n >> c >> p;
    for (int i = 0; i < 4; i++) {
      a[i].clear();
    }
    for (int i = 1, o; i <= n; i++) {
      string s, t;
      cin >> s >> t;
      if (t[0] == 'n') {
        o = 0;
      } else if (t[0] == 'c') {
        o = 1;
      } else if (t[0] == 't') {
        o = 2;
      } else {
        o = 3;
      }
      a[o].push_back(s);
    }
    p = p + min(p, (int)a[1].size()); // 句子数
    for (; a[0].size() && a[3].size() && h < p; sum += 2) {  
      ans[++h] = a[4];
      ans[h].push_back(a[0].back()), ans[h].push_back(a[3].back());
      a[3].pop_back(), a[0].pop_back();
    } // 尽量多的不及物语句
    for (l = h; a[0].size() >= 2 && a[2].size() && h < p; sum += 3) { 
      ans[++h] = a[4];
      ans[h].push_back(a[0].back()), ans[h].push_back(a[2].back());
      a[2].pop_back(), a[0].pop_back();
      ans[h].push_back(a[0].back()), a[0].pop_back();
    } // 尽量多的及物语句
    for (; l && a[0].size() && a[2].size(); l--, sum++) {
      ans[l].pop_back();
      ans[l].push_back(a[2].back()), ans[l].push_back(a[0].back());
      a[0].pop_back(), a[2].pop_back();
    } // 尽量将不及物语句替换成及物语句
    for (; l != h && a[0].size() && c; c--, sum++) {
      ans[h].push_back(a[0].back()), a[0].pop_back();
    } // 在及物语句乃加入尽可能多的名词及逗号
    cout << sum + min(h / 2, (int)a[1].size()) << '\n'; // 单词数
    for (int i = 1; i <= h; i++) {
      for (int j = 0; j < ans[i].size(); j++) {
        if (j > 2) {
          cout << ",";
        }  
        if (j) {
          cout << " ";
        }
        cout << ans[i][j];
      }
      if (i < h) { // 如果还有句子
        if (i % 2 && a[1].size()) { // 还可以使用连词
          cout << ' ' << a[1].back() << ' ';
          a[1].pop_back();
        } else {
          cout << ". "; // 不然输出句号
        }
      }
    }
    if (sum) {
      cout << "." << "\n"; // 最后的要输出句号， 如果没有句子就什么也不输出
    }
  }
  return 0;
}