[语言月赛202304H] 写大作业 题解

· · 题解

[语言月赛202304H] 写大作业 题解

Source & Knowledge

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

本题考察字符串处理和算法技巧。

文字题解

题目大意

给出 n 个字符串 s_1, s_2, \dots s_n，有 q 次操作，要么把 s_x 和 s_y 拼接合并，要么比较 s_x 和 s_y 是否能经过重排后变成相同的字符串。

解析

首先思考如何判定两个字符串经过重排后可以相同，容易发现等价的条件是每个字符在字符串内出现的次数相等。例如，对 s_1 = \texttt{abbc}，s_2 = \texttt{bacb}，因为字符 \texttt{a} 在两串中都出现了一次，\texttt b 在两串中都出现了两次，\texttt c 在两串中都出现了三次，所以两串重排后可以相等。于是问题转化成维护每个字符串中字符的出现次数。

60 分做法

可以依照题意模拟，每次对于操作 1，使用 string 类的 += 运算符将两个字符串拼接：

if (o == 1) s[y] += s[x];

对于操作 2，可以开一个大小为 26 的数组 b，b_i 表示第 i 个字母的出现次数。扫描一遍 s_x，把 s_x 出现的字母在 b 数组里增加 1，再扫描一遍 s_y，把 s_y 出现的字母在数组里减小 1。最后看一遍 b 数组是否全 0，如果是则说明两串相似，否则不相似。

注意每次操作之前都必须要清空 b 数组。

if (o == 2) {
  for (int i = 0; i < 26; ++i) b[i] = 0;
  for (int i = 0; i < s[x].length(); ++i)
    ++b[s[x][i] - 'a'];
  for (int i = 0; i < s[y].length(); ++i)
    --b[s[y][i] - 'a'];
  if (count(b, b + 26, 0) == 26) { // 这个函数的意思是找 b[0] 到 b[25] 中 0 的数量，需要 algorithm 头文件
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

100 分做法

可以发现实际地拼接两个字符串是不必要的。我们最终检查的只是两串的字符出现数量。于是我们考虑直接维护字符出现数量。

具体地，设 b_{i, j} 表示第 j 个字符在字符串 s_i 中出现的次数。

这样合并两串的时候，只需要合并两串对应的 b 数组即可。检查两串是否相似是，同样只需要检查两串的 b 数组。

cin >> o >> x >> y;
if (o == 1) {
  for (int j = 0; j < 26; ++j) b[y][j] += b[x][j];
} else {
  bool ans = true;
  for (int j = 0; j < 26; ++j) if (b[x][j] != b[y][j]) ans = false;
  cout << (ans ? "Yes\n" : "No\n");
}

视频题解

完整代码请在视频题解中查看。