首页 > 其他分享 >P8304 [CoE R4 D] 01 串

P8304 [CoE R4 D] 01 串

时间:2024-08-30 10:04:35浏览次数:11  
标签:R4 pre P8304 01 limits min suf ll define

思路:

要注意到添加 \(1\) 和删除 \(0\) 是等价的。

先令 \(0 \to -1\)。

首先猜了一个结论,先顺着走,做一个前缀和,若当且位置的前缀和 \(<0\),那么需要删除这个位置的 \(0\),使得前缀和为正;然后再反着做一遍,那么答案就是删除的 \(0\) 的个数。

暴力 Code:
int main(){
    n=read(),q=read();
    For(i,1,n){
        a[i]=get()-'0';
        if(!a[i])
          a[i]=-1;
    }
    while(q--){
        sum=ans=0;
        l=read(),r=read();
        For(i,l,r){
            sum+=a[i];
            if(sum<0){
                sum++,ans++;
                f[i]=1;
            }
        }
        _For(i,l,r){
            if(f[i]){
                f[i]=0;
                continue;
            }
            sum+=a[i];
            if(sum<0)
              sum++,ans++;
        }
        write(r-l+1-ans);
        putchar('\n');
    }
    return 0;
}

考虑优化,令 \(pre_i\) 表示 \([l,i]\) 的前缀和,\(suf_i\) 表示 \([i,r]\) 的后缀和。

则正着扫的时候,若 \(pre_i=-1\),相当于将 \(j \in [i,r]\) 的 \(pre_j\) 都增加了 \(1\),继续扫的时候若碰到 \(pre'_k = -1\),经过前面的加法操作前 \(pre_k = -2\),此时也需要给 \(j \in [k,r]\) 的 \(pre_j\) 增加 \(1\)。

那么我们就可以发现,后面若第 \(i\) 次找到 \(pre'_j=-1\),则原来的 \(pre_j = -i\)。

同时我们注意到 \(pre_i\) 是由 \(pre_{i-1}\) 加减 \(1\) 变换而来的,则访问的值域是连续的,则对于第一次正着扫需要的删除次数为:

\[-\min\limits_{i=l}^r pre_i \]

然后再考虑反着扫的贡献,同样也是找到 \(suf'_i = -1,-2,-3,\cdots\),但是这里 \(suf'\) 是 \(suf\) 经过正着扫后变化的。

在正着扫的时候,删除 \(i\) 处的 \(0\),相当于将 \(j \in [l,i]\) 的 \(suf_i\) 加 \(1\),即我们需要维护 \(i\) 这个位置右侧被删除的 \(0\) 的个数,因为正着扫是从左往右的,考虑做个差好维护一些,即相当于 \(-\min\limits_{i=l}^r pre_i\) 减去 \(i\) 左侧被删除的 \(0\) 的个数。

\(i\) 左侧被删除的 \(0\) 的个数,即 \(- \min\limits_{j=l}^i pre_j\),则我们得到了:

\[suf'_i = suf_i + (-\min\limits_{j=l}^r pre_j + \min\limits_{j=l}^i pre_j) = suf_i - \min\limits_{j=l}^r pre_j + \min\limits_{j=l}^i pre_j \]

则反着扫的贡献是:

\[-\min\limits_{i=l}^r suf'_i = -\min\limits_{i=l}^r \Big( suf_i - \min\limits_{j=l}^r pre_j + \min\limits_{j=l}^i pre_j \Big) = -\min\limits_{i=l}^r \Big( suf_i + \min\limits_{j=l}^i pre_j \Big) + \min\limits_{j=l}^r pre_j \]

则删除 \(0\) 的总数为:

\[\min\limits_{j=l}^r pre_j - \min\limits_{i=l}^r \Big( suf_i + \min\limits_{j=l}^i pre_j \Big) - \min\limits_{j=l}^r pre_j = - \min\limits_{i=l}^r \Big( suf_i + \min\limits_{j=l}^i pre_j \Big) \]

考虑这个式子的抽象意义:求出一个区间内不相交的一个后缀和加上一个前缀和的最小值,容斥一下,转化为区间和减去中间的一段,即我们要使得中间的一段最大,即区间最大子段和问题,使用线段树维护即可。

时间复杂度为 \(O(N \log N)\)。

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e6+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
inline char get(){
    char c;
    while(1){
        c=getchar();
        if(c=='0'||c=='1')
          break;
    }
    return c;
}
ll n,q,l,r,t,ans;
ll a[N],s[N];
class Tree{
public:
    struct Node{
        ll l,r;
        ll L,R;
        ll sum;
        ll data;
    }X[N<<2];
    Node pushup(Node A,Node B){
        Node Ans;
        Ans.l=A.l,Ans.r=B.r;
        Ans.sum=A.sum+B.sum;
        Ans.L=max(A.L,A.sum+B.L);
        Ans.R=max(B.R,B.sum+A.R);
        Ans.data=max({A.data,B.data,A.R+B.L});
        return Ans;
    }
    void build(ll k,ll l,ll r){
        X[k].l=l,X[k].r=r;
        if(l==r){
            X[k].sum=a[l];
            X[k].data=X[k].L=X[k].R=max(a[l],0ll);
            return ;
        }
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        X[k]=pushup(X[k<<1],X[k<<1|1]);
    }
    Node query(ll k,ll l,ll r){
        if(X[k].l==l&&r==X[k].r)
          return X[k];
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query(k<<1,l,r);
        else if(l>mid)
          return query(k<<1|1,l,r);
        else
          return pushup(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
    }
}T;
bool f[N];
int main(){
//	open("A.in","A.out");
    n=read(),q=read();
    For(i,1,n){
        a[i]=get()-'0';
        if(!a[i])
          a[i]=-1;
        s[i]=s[i-1]+a[i];
    }
    T.build(1,1,n);
    while(q--){
        l=read(),r=read();
        t=(r-l+1)+(s[r]-s[l-1]-T.query(1,l,r).data);
        if(!t)
          puts("-1");
        else{
        	write(t);
        	putchar('\n');
		}
    }
    return 0;
}

标签:R4,pre,P8304,01,limits,min,suf,ll,define
From: https://www.cnblogs.com/rgw2010/p/18388033

相关文章

  • 洛谷 P2680 [NOIP2015 提高组] 运输计划
    洛谷P2680[NOIP2015提高组]运输计划题意给出一棵树和\(m\)条路径,可以选择一条边,把边权改为\(0\),求\(m\)条路经长度最大值的最小值。思路看到最大值最小,可以想到二分答案,答案具有单调性。考虑如何判定答案\(x\)是否可行。统计所有长度大于\(x\)的路径,统计它们共......
  • Datawhale X 李宏毅苹果书(入门) AI夏令营 task01笔记
    官方学习链接:https://linklearner.com/activity/16/14/42机器学习基础导读        通俗来讲,机器学习就是让机器具备找一个函数的能力。这里指的“找一个函数”,指的是找一个能够描述一个场景数学规律的函数模型,具体方法大致是:让机器运行算法,通过输入的数据,确定合适的......
  • P10013 [集训队互测 2023] Tree Topological Order Counting
    Description给定一颗\(n\)个点的有根树,\(1\)是根,记\(u\)的父亲是\(fa_u\)。另给出一长度为\(n\)的权值序列\(b\)。称一个长度为\(n\)的排列\(a\)为这颗树的合法拓扑序,当且仅当\(\forall2\leu\len,a_u>a_{fa_u}\)。对每个点\(u\),定义\(f(u)\)为,在所有这......
  • luoguP5369 [PKUSC2018] 最大前缀和
    题目n<=20题解想了半天3位状态的折半,然后发现空间开不下(时间也不太行)所以放弃思考,直接枚举答案答案是a中的一个集合,设为S;记集合S的和为sum[S]考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部......
  • L2-013 红色警报 分数 25
    时间复杂度N*M≈2.5e6#include<bits/stdc++.h>usingnamespacestd;intn=510,m;constintN=510;vector<pair<int,int>>path;//储存所有边intp[N];//储存祖宗节点boolflag[N];//判断是否已经被去除voidinit()//初始化所有祖宗节点{......
  • [2017 ICPC Nanning] Rake It In
    https://ac.nowcoder.com/acm/contest/32183/A一个很有意思的搜索,先手希望结果尽可能的大,后手希望结果尽可能的小。所以在枚举的时候,先后手的策略是不一样的。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingldb=longd......
  • L2-010 排座位 分数 25
    #include<bits/stdc++.h>usingnamespacestd;constintN=1000;intp[N];intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}intmain(){intn,m,k;cin>>n>>m>>k;for(inti=1;i<=......
  • 信息学奥赛初赛天天练-78-NOIP2015普及组-基础题3-中断、计算机病毒、文件传输协议FTP
    NOIP2015普及组基础题38所谓的“中断”是指()A操作系统随意停止一个程序的运行B当出现需要时,CPU暂时停止当前程序的执行转而执行处理新情况的过程C因停机而停止一个程序的运行D电脑死机9计算机病毒是()A通过计算机传播的危害人体健康的一种......
  • Java面试题--2集合篇-01 __八股文 备战春招,秋招
    1.常见的集合有哪些?Java集合类主要由两个根接口Collection和Map派生出来的,Collection派生出了三个子接口:List、Set、Queue(Java5新增的队列),因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。注意:Collection是一个接口,Collections是一个工具类,Map不是Collectio......
  • AT_ddcc2017_final_d なめらかな木 题解
    首先考虑暴力DP,设\(f(i,v_1,v_2,now)\)为已经将前\(i\)个数填入,\(i\)填在\(v_1\),\(j\)填在\(v_2\)点,已经填完点的状态是\(now\)(状压一下存在一个longlong里)的方案数。转移时直接枚举下一个点暴力转移,只需要保证新的点没有被访问过,并且填上新点后,\(v_1\)的所有邻接......