自动搬运

查看原文

来自洛谷，原作者为

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

搬运于2025-08-24 21:14:34，当前版本为作者最后更新于2018-04-05 20:58:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

Source & Knowledge

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

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

文字题解

题目大意

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

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

求一共握了几次手。

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

• 对 $20\%$ 的数据，保证 $m = 0$。
• 对 $50\%$ 的数据，保证 $n, m \leq 100$。
• 对 $70\%$ 的数据，保证 $n, m \leq 10^3$。
• 对 $100\%$ 的数据，保证 $2 \leq n \leq 3 \times 10^4$，$1 \leq u, v \leq n$，$0 \leq p,q \leq m \leq 10^3$。

分析

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

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

算法二：依照题意枚举

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

• 如果 $i$ 和 $j$ 是朋友，则他们握手，令 ans++。
• 如果 $i$ 和 $j$ 是敌人，则他们不握手，ans 不变。
• 如果 $i$ 和 $j$ 是陌生人，则令 $k$ 从 $1$ 到 $n$ 枚举，如果存在一个 $k$ 使得 $k$ 是 $i$ 的朋友且是 $j$ 的敌人（或是 $j$ 的朋友且是 $i$ 的敌人），则符合陌生人之间不握手的条件，ans 不变，否则令 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;
  }
}

视频题解

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