cf edu152 C. Binary String Copying(字符串双哈希)

这篇具有很好参考价值的文章主要介绍了cf edu152 C. Binary String Copying(字符串双哈希)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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)bases+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]可以标识一个拷贝串,直接将数对放进集合中统计就可以了。

完整代码

写得比较丑陋。

//
// 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;
}

cf edu152 C. Binary String Copying(字符串双哈希),ACM23,哈希算法,散列表,算法文章来源地址https://www.toymoban.com/news/detail-613226.html

到了这里,关于cf edu152 C. Binary String Copying(字符串双哈希)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C# 字符串(String)

    C#基础学习入门系列- C# 字符串(String) C#字符串(String)是一种不可变的序列字符。任何对字符串的操作都会返回一个新的字符串。字符串在C#中是一个引用类型,使用System.String类表示。 字符串可以通过使用双引号或者@符号来创建。双引号用于创建普通字符串 ,例如: @符

    2024年01月21日
    浏览(57)
  • redis—String字符串

    目录 前言 1.字符串数据类型 2.常见命令 3.典型应用场景 字符串类型是Redis最基础的数据类型,关于字符串需要特别注意: 1)首先Redis中所有的键的类型都是字符串类型,而且其他几种数据结构也都是在字符串类似基础.上构建的,例如列表和集合的 元素类型是字符串类型,所以

    2024年02月02日
    浏览(50)
  • 字符串分割(split),将字符串按照指定字符进行分割。split(String regex)和split(String regex, int limit)

    一、 split(String regex) 字符串分割,将字符串按照指定字符进行分割,返回的是一个字符串数组。 原理:参数名称是 regex 表示的是以某个字符串进行字符分割。 实例1:根据空格切割 输出结果: 实例2:根据特殊字符进行“.”分割 输出结果: 二、 split(String regex, int limit) 字符

    2024年02月11日
    浏览(52)
  • Java Base64字符串与String字符串互转方法

    在使用String转Base64和Base64转String上有点小问题,特此记录。 结果: 也是跟上面差不多的思路,将Base64转为byte数组,再转为String

    2024年02月15日
    浏览(60)
  • 6.string字符串的比较

    比较结果是真或假, 比较:字符串是1和1比较 然后9和2 比较 大后面就不用比了 对应字符比他大就行了。 结果:如果这个是符合比较运算符的就返回真。反之假 跟具不同的目的选择不同的运算符, 结果只有真和假,运算符不是最后的结果。 总结:如果这个是符合比较运算符

    2024年02月15日
    浏览(42)
  • rust 字符串(String)详解

    rust中的 String ,是一个非常常用的 crate ,它的底层涉及到了rust中的所有权概念,不过这不是本章的内容,如果对rust所有权概念感兴趣的,可以查看另一篇文章:rust所有权 本文的目的还是介绍 String 的基本用法,以及有哪些常用的函数可以使用 字符串,也就是由一系列字符

    2024年02月03日
    浏览(47)
  • 【学到一个新名词】String interning(字符串驻留/字符串内部化)

    作者:张富春(ahfuzhang),转载时请注明作者和引用链接,谢谢! cnblogs博客 zhihu Github 公众号:一本正经的瞎扯 在阅读 VictoriaMetrics v1.95.1 的命令行手册的时候,发现这样一段: 什么是 String interning 呢?我通过了 wiki 链接学习了一下。 并且,我还找到了一个使用 String interning 技术

    2024年02月05日
    浏览(64)
  • Java中的字符串String

    目录 一、常用方法 1、字符串构造 2、String对象的比较 (1)、equals方法 (2)、compareTo方法 (3)、compareToIgnoreCase方法(忽略大小写进行比较) 3、字符串查找 4、转化 (1)数值和字符串转化 ​编辑 (2)大小写转换 (3)字符串转数组 (4)格式化 5、字符串替换 6、字符串

    2024年02月05日
    浏览(63)
  • Java中的String字符串练习

    目录 Java中的String字符串练习 01-用户登录 02-遍历字符串并统计字符个数 03-字符串拼接 04-字符串反转 注意点 05-金额转化(简单) 代码解释: 06-手机号屏蔽 07-身份证号码查看 易错点: 08-敏感词替换 注意点 toCharArray() 是Java中的一个方法,它用于将字符串转换为字符数组。 方法签

    2024年03月28日
    浏览(66)
  • Java的String(字符串详解)

    主要有三种,一种是直接使用常量去构造,要么使用new String来构造,或者还可以使用字符数组的形式。 String 类型本身并不存储数据,而是存储指向该字符串的引用,所以字符串类型是一个类,s1是一个引用,指向这个类。而这个类有两个成员变量,一个名称为value,这也是一

    2024年02月07日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包