2023年码蹄杯专科组第三场初赛 解题报告 | 珂学家

前言

题解

这是2023年第三场码蹄杯职业院校算法比赛，3D眩晕（字符串hash）挺有意思的。

这个系列赛，喜欢出典题。

3D眩晕

难度: 钻石

思路: 字符串hash

这题难在容错性上，就是允许有x次修改($x\le 3$)，然后寻找等价的子数组个数。

这题使用字符串hash应该没有疑问，kmp/z函数在这边有点吃力。

当时光有string hash，也不行，那何如切入呢？

其实可以从x($x\le 3$)切入

把问题转化为

相同长度的串，寻找最早的不同点

这里有2种解法

• 分治寻找

  分治递归寻找不同的点数

• 二分寻找不同点

  第i次二分，寻找第i个不同点

因为个数有限，所以剪枝快速返回

这边给的解法是

• 二分找不同点

#include <bits/stdc++.h>  using namespace std;  struct StringHash {     StringHash(const std::string &s, int64_t p, int64_t mod)         : s(s), p(p), mod(mod), pow(s.length() + 1), arr(s.length() + 1) {         int n = s.length();         pow[0] = 1l;         for (int i = 0; i < n; i++) {             pow[i + 1] = pow[i] * p % mod;             arr[i + 1] = (arr[i] * p % mod + s[i]) % mod;         }     }       int64_t query(int l, int r) {         int64_t tmp = arr[r + 1] - arr[l] * pow[r - l + 1] % mod;         return (tmp + mod) % mod;     }      string s;     int64_t p;     int64_t mod;     vector<int64_t> pow;     vector<int64_t> arr; };  int main() {      int t;     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);     cin >> t;     while (t-- > 0) {         string s0, s;         cin >> s0 >> s;          int64_t p1 = 13l, p2 = 17l;         int64_t mod = (int64_t)1e9 + 7;         StringHash hp1(s0, p1, mod), hp2(s0, p2, mod);         StringHash mp1(s, p1, mod), mp2(s, p2, mod);          int res = 0;         int n1 = s0.length(), n2 = s.length();         for (int i = 0; i <= n1 - n2; i++) {             // 统计不同的个数             int s = i;             for (int j = 0; s <= (i + n2) && j < 4; j++) {                 int l = s, r = i + n2 - 1;                 while (l <= r) {                     int m = l + (r - l) / 2;                     if (hp1.query(s, m) == mp1.query(s - i, m - i) && hp2.query(s, m) == mp2.query(s - i, m - i)) {                         l = m + 1;                     } else {                         r = m - 1;                     }                 }                 s = l + 1;             }              if (s > (i + n2)) {                 res++;             }         }         cout << res << endl;     }      return 0; } 

写在最后