自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:16:58，当前版本为作者最后更新于2024-12-17 23:55:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛 202412] 顽强拼搏奖的四种发法 题解

Source & Knowledge

本题来源于 2024 年 12 月的语言月赛，主要考察二维数组和模拟。

文字题解

题目大意

根据给定的提交记录，按照四种不同的规则确定获得顽强拼搏奖的队伍编号。

解析

【读入】
由于必须先确定那些队伍是获得奖牌的队伍，所以必须把所有提交记录先读入进来存储下来再做操作。我们用一个数组 record[i][3] 的三个数分别表示一条记录的 tid,pid 和 state。同时，我们用一个 pass 数组来记录一支队伍通过了哪些题。

for (int i = 1; i <= n; ++i) {
  cin >> record[i][0] >> record[i][1] >> record[i][2];
  int tid = record[i][0], pid = record[i][1];
  if (record[i][2]) pass[tid][tid] = 1;
}

【获奖判定】
解出至少 $k$ 题的队伍获奖，因此可以通过检查 pass[i] 数组里有多少个 $1$ 来确定第 $i$ 支队伍是否获奖，然后把是否获奖存储在 win 数组里。

for (int i = 1; i <= t; ++i) {
  int cnt = 0;
  for (int j = 1; j <= p; ++j) if (pass[i][j]) ++cnt;
  if (cnt >= k) win[i] = true;
}

【顽强拼搏奖判定】
接下来重新遍历一遍提交信息，按规定判定更新顽强拼搏奖即可。

int a = -1, b = -1, c = -1, d = -1;
for (int i = 1; i <= n; ++i) {
  int tid = record[i][0], pid = record[i][1], state = record[i][2];
  if (state == 1) {
    a = tid;
    if (!passed[tid][pid]) {
      b = tid;
      if (!win[tid]) c = tid;
      int curpassed = 0;
      for (int j = 1; j <= p; ++j) curpassed += pass[tid][j];
      if (curpassed == 0) {
        d = tid;
      }
    }
    passed[tid][pid] = 1;
  }

注意这里重新维护了每个题目的通过情况，因此要事先清空 pass 数组。

通过上述步骤，我们可以有效地计算出按照四种不同规则获得顽强拼搏奖的队伍编号。