B3683 [语言月赛202211] String Problem 题解

· · 题解

B3683 [语言月赛202211] String Problem 题解

Source & Knowledge

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

本题考察字符串处理、字符串判等和算法优化能力。

文字题解

题目大意

给定两个字符串 s 和 t，要求判断两字符串是否相等；此外有 q 次修改操作，每次修改某个字符串的某位字符，每次修改后求出两字符串是否相等。

解析

算法一：字符串暴力判等

使用 string 类型读入存储 s 和 t 两个字符串：

string s, t;
cin >> s >> t;

判断两个字符串相等只需要使用 == 运算符：

if (s == t) cout << "Yes\n";
else cout << "No\n";

对字符串某位置作出修改，只需要用[] 运算符进行单点修改。需要注意的是，string 的下标范围是 0 到 \mathrm{length} - 1，其中 \mathrm{length} 表示字符串长度，而输入的下标 p 范围是 1 到 n，所以需要将 p 减去 1 才能对应到其在字符串中的下标。

cin >> o >> p >> c;
if (o == 0) s[p - 1] = c;
else t[p - 1] = c;
if (s == t) cout << "Yes\n";
else cout << "No\n";

需要注意的是，每次判断两字符串是否相等的运算量在最坏情况下大约和字符串长度 (10^6) 相当，其一种可能的实现是：

bool equal(string s, string t) {
  if (s.length() != t.length()) return false;
  for (int i = 0; i < s.length(); ++i) if (s[i] != t[i]) return false;
  return true;
}

而我们一共需要处理大约 q = 10^6 次判断操作，所以总的运算量在最坏情况下大约为 10^{12} 次方。而计算机一秒大约可以处理 10^8（按如上方式计算出）的运算量。所以这一算法会在较大的数据下超时，只能获得 60 分。

算法二：存储不匹配的位置数量

考虑对算法一做出优化。

注意到对于上面的算法，每进行一次修改操作，我们只修改了字符串一位的信息，却把字符串的所有位置都重新比较了一遍。对于没有被修改的位置，我们没有必要去重新比较它们是否相等。

进一步思考发现，对于一次询问，我们也不需要直到它们具体哪一位是不同的，只需要知道他们是否存在不同的位置即可。这启发我们用一个变量 cnt 记录当前两字符串不同的位置数量。

初始输入 s 和 t 后，cnt 可以用如下的方式求出：

for (int i = 0; i < n; ++i) if (s[i] != t[i]) ++cnt;

考虑每次修改某个字符串的某个下标时，其他位置的不同数量不受影响。我们先在 cnt 里扣除当前位置对 cnt 的贡献（贡献指的是：如果 s_{p-1} \neq t_{p-1}，那么它会 cnt 增加 1，则 1 是它对 cnt 的贡献；如果他不会令 cnt 增加，则它对 cnt 的贡献为 0），然后对对应位置进行修改，最后加回这一位置对 cnt 做出的新贡献。

也就是说，在修改前，如果 s_{p-1} \neq t_{p-1}，那么我们给 cnt 减去 1，表示 p 这一位置对 cnt 的影响被去除了；做完修改后，如果 s_{p-1} \neq t_{p-1}，则我们给 cnt 加上 1，计算上这一位置对 cnt 的影响；当然如果修改前或修改后 s_{p-1} = t_{p-1}，那么我们在修改前或修改后不对 cnt 操作，因为这一位置对 cnt 没有影响。

写作代码就是：

cin >> o >> p >> c;
if (s[p - 1] != t[p - 1]) --cnt;        // 去掉 p 这一位置原来对 cnt 的影响
if (o == 0) s[p - 1] = c;
else t[p - 1] = c;
if (s[p - 1] != t[p - 1]) ++cnt;        // 加上 p 这一位置修改后对 cnt 的影响
if (cnt == 0) cout << "Yes\n";          // 如果有 0 个位置不同，说明两字符串相等
else cout << "No\n";

这样，每次判等的运算量被我们降低了很多，就可以通过本题了。

注意事项

  1. 如果使用 char 数组存储字符串，在 for 循环里采取类似 for (int i = 0; i < strlen(s); ++i) 的代码会造成超时，因为单次求 strlen(s) 的运算量大约也是字符串长度。

  2. 注意本题共有大约 10^6 次输入输出，需要关闭 cin 和 stdio 的同步、和 cout 的绑定，同时使用 \n 换行才能降低输入输出用时。方法是：在 main 函数开头加入：

    ios::sync_with_stdio(false);
cin.tie(0);

    并把代码中的 endl 全部改为 '\n'。详见视频题解。

视频题解

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

说明：视频题解中对 cnt 的定义是：两字符串相同的位置，而上文文字题解中对 cnt 的定义是两字符串不同的位置。两种定义不同，在代码实现上也有细微的差别，请注意区分，但原理是相同的。