B3712 [语言月赛202302] 大碗宽面 题解

· · 题解

[语言月赛202302] 大碗宽面 题解

Source & Knowledge

2023 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考查二维 bool 数组、枚举技巧。

文字题解

题目大意

有 n 个人，其中 p 对人是敌人，q 对人是朋友，其余每对人均是陌生人。

朋友之间会握手一次，
敌人之间不会握手，
对一对陌生人而言，如果其中一个人的朋友之一是另一个人的敌人，则不握手，否则握手。

求一共握了几次手。

如果令 m = p + q，保证：

分析

算法一：均为陌生人的情况

如果 m = 0，则意味着大家都是陌生人，不存在敌人和朋友关系。那么一对陌生人之间一定会握手。考虑对于每个人，都会和其它 n - 1 个人握手一次，总共握手 n \times (n - 1) 次。而 a 和 b 握手与 b 和 a 握手是同一种情况，我们计算了两次，所以总方案数要除掉 2。因此当 m = 0 时，答案就是 n \times (n - 1) / 2。

算法二：依照题意枚举

我们可以枚举每对人 (i,j)。记录握手次数 ans。

判断两人是否是敌人或朋友可以用两个二维数组 isFriend 和 isEnemy 记录。

枚举部分代码如下：

for (int i = 1; i <= n; ++i) 
  for (int j = i + 1; j <= n; ++j) if (isFriend[i][j]) {
    ++ans;
  } else if (!isEnemy[i][j]) {
    bool flag = true; // flag 记录是否握手
    for (int k = 1; k <= n; ++k) 
      if ((isFriend[i][k] && isEnemy[k][j]) || (isFriend[j][k] && isEnemy[k][i])) { // 注意判断条件需要加括号
        flag = false; // 此时符合不握手条件。
        break; // 无需继续枚举
      }
    if (flag) ++ans; // 如果枚举结束后 flag 仍是 1，则表示不存在不握手的条件，则握手。
  }

这一算法需要三层长度为 n 的 for 循环，因此运算量在 n^3 左右。可以通过 n \leq 100 的数据。当 n = 10^3 时，运算量在 10^9 左右，而计算机一秒只能处理大约 10^8 次运算，这个算法会超时。

算法三：优化点对枚举

注意到陌生人点对数量实在是太多了，大约有 n^2 - m 对。但是大部分陌生人都满足握手条件，是无效枚举。考虑正难则反，我们先算出本身假设所有陌生人都握手时的答案，然后减去不握手的陌生人对数。

首先算出所有陌生人都握手的答案：在算法一中已经解释了一共有 n \times (n - 1) / 2 对人。且有 q 对敌人。这 q 对敌人不握手，其他人均握手。所以此时答案是 n \times (n - 1) / 2。

接下来考察一对敌人关系 (u, v) 可以造成哪些人不握手：考虑枚举 v 的朋友 w。考察 u 和 w，满足『v 是 u 的敌人且是 w 的朋友』，所以如果 u 和 w 是陌生人，则它们不握手。类似的也要枚举 u 的朋友。所以可以按照枚举敌人关系-朋友关系的方式来判定不握手的陌生人。如何枚举 v 的朋友呢？可以令 w = 1 \sim n 都枚举一遍，检查 isFriend[w][v] 是否为 true 即可。每次枚举到一对不握手的陌生人，就令 ans--。

最后一个问题是，答案可能会算重。所以需要一个额外的数组 calced[u][v] 表示我们已经计算过 u 和 v 不握手的情况了。

int enemy[2][maxm];
for (int i = 1; i <= q; ++i) { // 因为要枚举敌人关系，所以读入时需要记录敌人的信息
  cin >> enemy[0][i] >> enemy[1][i];
  isEnemy[enemy[0][i]][enemy[1][i]] = isEnemy[enemy[1][i]][enemy[0][i]] = true;
}

for (int i = 1; i <= q; ++i) { // 枚举敌人关系
  int u = enemy[0][i], v = enemy[1][i];
  for (int w = 1; w <= n; ++w) if (isFriend[v][w] && (!isEnemy[u][w]) && (!isFriend[u][w]) && (!calced[u][w])) {
    --ans;
    calced[u][w] = calced[w][u] = true;
  }
  swap(u, v); // 交换 u,v 再来一遍，相当于枚举原先 u 的朋友。
  for (int w = 1; w <= n; ++w) if (isFriend[v][w] && (!isEnemy[u][w]) && (!isFriend[u][w]) && (!calced[u][w])) {
    --ans;
    calced[u][w] = calced[w][u] = true;
  }
}

这一算法一共需要开三个大小为 n^2 的 bool 数组。当 n = 3 \times 10^4 时会超过空间限制。注意到 calced 数组可以和 isEnemy 数组合并：如果两个人是敌人，那么他们当然已经从答案中被去除了。所以 calced[u][v] 即可以用来表示 (u,v) 是已经计算过不会握手的陌生人，也可以表示他们本身是敌人。总之用 calced 数组来表示已经计算过不会握手的人，则可以省去 isEnemy 数组。此时只需要开两个大小为 n^2 的 bool 数组，空间可以承受。

int enemy[2][maxm];
for (int i = 1; i <= q; ++i) { // 因为要枚举敌人关系，所以读入时需要记录敌人的信息
  cin >> enemy[0][i] >> enemy[1][i];
  calced[enemy[0][i]][enemy[1][i]] = calced[enemy[1][i]][enemy[0][i]] = true;
}

for (int i = 1; i <= q; ++i) { // 枚举敌人关系
  int u = enemy[0][i], v = enemy[1][i];
  for (int w = 1; w <= n; ++w) if (isFriend[v][w] && (!isFriend[u][w]) && (!calced[u][w])) {
    --ans;
    calced[u][w] = calced[w][u] = true;
  }
  swap(u, v); // 交换 u,v 再来一遍，相当于枚举原先 u 的朋友。
  for (int w = 1; w <= n; ++w) if (isFriend[v][w] && (!isFriend[u][w]) && (!calced[u][w])) {
    --ans;
    calced[u][w] = calced[w][u] = true;
  }
}

视频题解

完整代码请在视频中观看。