自动搬运

查看原文

来自洛谷，原作者为

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

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

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

以下是正文

[语言月赛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");
}

视频题解

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