首页 > 其他分享 >CF873B Balanced Substring

CF873B Balanced Substring

时间:2024-07-31 23:06:43浏览次数:11  
标签:01 CF873B int sum maxt Substring Balanced mint 300000

Abstract

传送门
本题定义平衡串为 0 和 1 数量相等的字符串,要求我们找出给定 01 串中含有的最大平衡串。

Idea

如果把 1 视为 +1 ,0视为 -1,那么一个 01 串是平衡串当且仅当其和值为 0 ,那么问题就转变为寻找给定 01 串中和值为 0 的最长子段。

首先做一个前缀和,a[i] 表示前 i 项的和值,那么对于区间 [l,r] ,只要 a[r] - a[l-1] == 0,它就是一个平衡串,暴力枚举 l 和 r ,时间复杂度是 O(n^2),显然超时。实际上,对于每一个 a[i] ,我们只希望找到一个 a[j] ,使得 a[i] == a[j] ,那么我们可以考虑存储 a[i] 出现的最大序号和最小序号,然后取其差值即可得到答案,细节见代码。

Code

#include <bits/stdc++.h>
using namespace std;
// buyy
int a[300000];
int mint[300000];
int maxt[300000];
int main()
{
    int n;
    memset(mint, 0x3f3f3f3f, sizeof mint);
    memset(maxt, -0x3f3f3f3f, sizeof maxt);
    scanf("%d\n", &n);
    int sum = 0;
    int ans = 0;
    for (int i = 1; i < n + 1; i++)
    {
        char c = getchar();
        if (c == '1')
        {
            sum++;
        }
        else
        {
            sum--;
        }
        if (sum > 0)
        {
            mint[sum] = min(mint[sum], i);
            maxt[sum] = max(maxt[sum], i);
        }
        else if (sum == 0)
        {
            ans = i;
        }
        else
        {
            int p = -sum + n;
            mint[p] = min(mint[p], i);
            maxt[p] = max(maxt[p], i);
        }
        a[i] = sum;
    }

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)
        {
            continue;
        }
        if (a[i] < 0)
        {
            a[i] = -a[i] + n;
        }
        ans = max(ans, maxt[a[i]] - mint[a[i]]);
    }
    cout << ans;
    return 0;
}

标签:01,CF873B,int,sum,maxt,Substring,Balanced,mint,300000
From: https://www.cnblogs.com/carboxylBase/p/18335703

相关文章

  • mysql中substring_index类似split分组功能
     这条MySQL语句中使用了substring_index函数来处理training_pictures列的数据。下面是该函数的具体用法:substring_index(str,delim,count):这个函数会返回字符串str中第count个出现的分隔符delim之前的所有字符,或者之后的所有字符(取决于count的正负)。具体到你提供的查询:s......
  • Solution - Atcoder ABC280Ex Substring Sort
    对于这种子串问题,且有多个基础串,一个比较直观的想法就是先上个广义SAM。考虑SAM与字典序如何联系上。因为跳\(\operatorname{fail}\)相当于是删除子串的一个前缀,直接这样子明显是不行的,因为跳了\(\operatorname{fail}\)字典序没有一个很直观地表示。但是反过来考虑反串,......
  • imbalanced-learn库的作用和安装
    imbalanced-learn是一个Python库,‌专门用于处理不平衡数据集的机器学习问题。‌ 这个库提供了一系列的重采样技术、‌组合方法和机器学习算法,‌旨在提高在不平衡数据集上的分类性能。‌Imbalanced-learn支持欠采样、‌过采样、‌结合欠采样和过采样的方法,‌以及一些集成学习方法......
  • 线段树(原理、构造和区间查询,例题:Balanced Lineup)
    概念原理    线段树是分治法和二叉树的结合,二叉树上的节点都是根据分治得到的。节点所表示的,也就是线段,可以是区间和、最值或者是其他的,,每次分治,左右子树各一半,每个节点的值代表了以它为根的子树上所有节点的值。通过线段树,大区间的解可以从小区间的解合并而来。构......
  • Imbalanced Arrays
    还没有仔细看官方题解和洛谷题解,重新做的时候看一下有没有什么可以吸收的说一下我的做法:首先看到第二个条件,不难想出\(i\)和\(-i\)只有可能选一个,此时观察样例,以及发现\(b\)刚好有\(n\)个数,所以不难想到最终\(b\)的构造方案是由\(1\)~\(n\)的每一个数或其相反数组成的,且每个数......
  • 题解:SP11469 SUBSET - Balanced Cow Subsets
    SP11469(折半搜索)题目大意:给出$N$个数,求可以被分成两个和相等的集合的子集数。思路分析:首先考虑朴素的DFS,每个数有三种情况:选为$A$集合,选为$B$集合,两个集合都不选。暴力DFS时间复杂度为$3^{20}$。观察到$N$很小,而$3^{10}$是可以通过本题的,于是考虑折半搜索。我......
  • CF1237F Balanced Domino Placements
    比较有意思的Counting,想到横竖两种骨牌的独立性就很好做了考虑如果枚举最后放了\(x\)块横着的骨牌,\(y\)块竖着的骨牌,直接考虑它们的摆放不方便,不妨转化一下在所有空余的行中,选择\(x+2y\)行,且满足其中有\(y\)对相邻的行;在所有空余的列中,选择\(2x+y\)列,且满足其中有\(x......
  • D2. Sum over all Substrings (Hard Version)
    原题链接题解code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lldp[1000005]={0};voidsolve(){lln,ans=0;cin>>n;strings;cin>>s;s=""+s;//使字符串1索引化for(lli=1......
  • [namespace hdk] Balanced_tree 整合
    代码#include<bits/stdc++.h>usingnamespacestd;namespacehdk{ namespacebalanced_tree{ constintN=2000001,inf=114514191; classsplay{ private: introot,tot; structtree{ intw; intcnt,size; intfa,son[2]; }t[N];......
  • [题解]AT_abc158_e [ABC158E] Divisible Substring
    思路首先发现一个事情,任意一个子串都可以由\(s\)的某一个后缀的后面删除一些字符得到。因此假如\(s\)的某一个后缀的值为\(x\),那么我们可以减去后面的我们不用的数字\(a\),然后除以\(10\)的若干次幂得到,即\(\frac{x-a}{10^n}\)。于是得到:\[\frac{x-a}{10^n}\equi......