cf edu152 C. Binary String Copying(字符串双哈希)
题目链接:https://codeforces.com/contest/1849/problem/C
题目大意
给定一个01字符串,长度为n,拷贝m份,对每一份进行相应操作:将 [ L i , R i ] [L_i,R_i] [Li,Ri]的字符排序,实际就是调整为0在前1在后,问得到的m个副本有多少个不同串。数据范围:n和m都是2e5。
思路
字符串哈希。预处理连续0串和1串的哈希值。
字符串 s 1 s_1 s1和 s 2 s_2 s2拼接得到的字符串 s 1 s 2 s_1s_2 s1s2的哈希值为 f ( s 1 s 2 ) = f ( s 1 ) ∗ b a s e ∣ s ∣ + f ( s 2 ) f(s_1s_2)=f(s_1)*\mathop{base}^{\left| s \right|}+f(s_2) f(s1s2)=f(s1)∗base∣s∣+f(s2)
int merge(ll h1, ll h2, int n) {
return (h1 * bofs[n] % M + h2) % M;
}
逆过来,也可以求某个子串的哈希值,将基的幂次预处理可以 O ( 1 ) O(1) O(1)求得。
int Slice(int l, int r) {
return (ha[r] - ((ll)ha[l - 1] * bofs[r - l + 1] % M) + M) % M;
}
之后,我们可以
O
(
1
)
O(1)
O(1)去求某个字符串的哈希值了。比如对10001100,操作区间
[
3
,
7
]
[3,7]
[3,7],可以通过拼接10,000,11,0四个串的哈希值得到。将这些哈希值放入set
中统计。这个方法可以拓展到由任意字符构成的字符串,不过编码比较复杂,要取模。同时单哈希还会被卡,要用两个基做双哈希才行。
正解:对于每个位置 i i i,记录往左第一个0的位置 l i l_i li,和往右第一个1的位置 r i r_i ri,操作区间 [ x , y ] [x,y] [x,y]等价于操作区间 [ l x , r y ] [l_x,r_y] [lx,ry],因此通过操作 [ l x , r y ] [l_x,r_y] [lx,ry]可以标识一个拷贝串,直接将数对放进集合中统计就可以了。
完整代码
写得比较丑陋。文章来源:https://www.toymoban.com/news/detail-613226.html
//
// Created by zkr on 2023/7/27.
//
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1e9 + 7;
const int B1 = 29, B2 = 31;
int bofs1[200005], bofs2[200005]; // 先将基预处理出来
int ha1[200005], ha01[200005], ha11[200005];
int ha2[200005], ha02[200005], ha12[200005];
int Slice1(int l, int r) {
return (ha1[r] - ((ll)ha1[l - 1] * bofs1[r - l + 1] % M) + M) % M;
}
int Slice2(int l, int r) {
return (ha2[r] - ((ll)ha2[l - 1] * bofs2[r - l + 1] % M) + M) % M;
}
int merge1(ll h1, ll h2, int n) {
return (h1 * bofs1[n] % M + h2) % M;
}
int merge2(ll h1, ll h2, int n) {
return (h1 * bofs2[n] % M + h2) % M;
}
void solve() {
// 2e5进行2e5次排序
// 统计每个区间的0和1,直接排序构造该串,插入哈希表中
// 可以O(1)获取子串的哈希
int n, m;
cin >> n >> m;
string s; cin >> s;
for (int i = 1; i <= n; i++) {
ha1[i] = ((ll)ha1[i - 1] * B1 + s[i - 1]) % M;
} // [1,n]
for (int i = 1; i <= n; i++) {
ha2[i] = ((ll)ha2[i - 1] * B2 + s[i - 1]) % M;
} // [1,n]
vector<int> cnt(n + 1);
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1') cnt[i] = cnt[i - 1] + 1;
else cnt[i] = cnt[i - 1];
} // [1,n]
set<pair<int, int>> st;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
int sum = y - x + 1;
int cnt1 = cnt[y] - cnt[x - 1]; // 0011 x=1 y=3
int cur1 = Slice1(y + 1, n);
if (cnt1 >= 1) cur1 = merge1(ha11[cnt1], cur1, n - y);
if (sum - cnt1 >= 1) cur1 = merge1(ha01[sum - cnt1], cur1, n - y + cnt1);
cur1 = merge1(ha1[x - 1], cur1, n - x + 1); // [x, y]
// 直接拼接得到哈希值
int cur2 = Slice2(y + 1, n);
if (cnt1 >= 1) cur2 = merge2(ha12[cnt1], cur2, n - y);
if (sum - cnt1 >= 1) cur2 = merge2(ha02[sum - cnt1], cur2, n - y + cnt1);
cur2 = merge2(ha2[x - 1], cur2, n - x + 1); // [x, y]
st.insert({cur1, cur2});
}
cout << st.size() << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ha01[0] = 0, ha11[0] = 0; // [1,n]
bofs1[0] = 1;
for (int i = 1; i <= 2e5; ++i) {
bofs1[i] = ((ll)bofs1[i - 1] * B1) % M;
ha01[i] = ((ll)ha01[i - 1] * B1 + '0') % M;
ha11[i] = ((ll)ha11[i - 1] * B1 + '1') % M;
}
ha02[0] = 0, ha12[0] = 0; // [1,n]
bofs2[0] = 1;
for (int i = 1; i <= 2e5; ++i) {
bofs2[i] = ((ll)bofs2[i - 1] * B2) % M;
ha02[i] = ((ll)ha02[i - 1] * B2 + '0') % M;
ha12[i] = ((ll)ha12[i - 1] * B2 + '1') % M;
}
int t; cin >> t;
while (t--)
solve();
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-613226.html
到了这里,关于cf edu152 C. Binary String Copying(字符串双哈希)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!