题解 修改01串

题目描述

数据范围:

具体做法与心路历程

这道题作为$T1$真心觉得出题人毒瘤好吧是我太菜。看这题目感觉妥妥的贪心，贪心思路都有，且还是对的。可惜只有$50pts$,然后开始优化贪心，搞了个线段树，一码就是$300+$，结果错了。CYJian线段树贪心A了，还只有200+。考完才知道正解是$DP!$，然而我连想都没想。

具体做法

方法是$DDP$。设$f[i][0/1]$表示使第$1$ ~ $i$位全部变成$0$,且有没有对下一位进位的方案数,$a[i]$表示原字符串的字符。转移为:

$f[i][0]=min(f[i-1][0]+1-a[i],f[i-1][1]+a[i])$. 第$i-1$位如果没进位，且第$i$位为$1$，那么答案+1,否则不加，如果第$i-1$位进位，且第$i$位不为$1$，那么答案+1,否则不加。在这些情况中取最小值即可。$[i][1]=min(f[i-1][0]+2-a[i],f[i-1][1]+1-a[i]$. 第$i-1$位没进位，且第$i$位为$0$，答案+2,为1则+1,第$i-1$位进位，第$i$位为$0$则答案+1,否则不加。

这个如果不修改则$O(n)$就做完了，如果修改的话可以考虑$DDP$,发现这个式子可以写成广义矩阵的形式，用线段树维护即可。话说我DDP板子题都没打过的蒟蒻这些题倒是做了几道了

$\mathcal{C}ode$

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年11月01日 星期五 22时09分42秒 *******************************/ #include<cstdio> #include<algorithm> #include<string> #include<cstring> using namespace std; struct IO{ template<typename T> IO & operator>>(T&res) { T q=1;char ch; while((ch=getchar())<'0' or ch>'9')if(ch=='-')q=-q; res=(ch^48); while((ch=getchar())>='0' and ch<='9') res=(res<<1)+(res<<3)+(ch^48); res*=q; return *this; } }cin; struct Matrix{ int a[2][2]; int * operator[](const int i) { return a[i]; } const int * operator[](const int i) const { return a[i]; } Matrix operator*(const Matrix p) { Matrix t; t[0][0]=min(a[0][0]+p[0][0],a[0][1]+p[1][0]); t[0][1]=min(a[0][0]+p[0][1],a[0][1]+p[1][1]); t[1][0]=min(a[1][0]+p[0][0],a[1][1]+p[1][0]); t[1][1]=min(a[1][0]+p[0][1],a[1][1]+p[1][1]); return t; } }; const int maxn=3e5+10; const Matrix M0={{{0,1},{2,1}}}; const Matrix M1={{{1,2},{1,0}}}; int n,m,a[maxn]; string s; /*{{{线段树*/ namespace SegmentTree{ Matrix tr[maxn*4]; void update(int k) { tr[k]=tr[k<<1]*tr[k<<1|1]; } void build(int k,int l,int r) { if(l==r) { tr[k]=(a[l]?M1:M0); return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); l update(k); } void modify(int k,int l,int r,int pos) { if(l==r) { tr[k]=(a[pos]?M1:M0); return; } int mid=(l+r)>>1; if(pos<=mid) modify(k<<1,l,mid,pos); else modify(k<<1|1,mid+1,r,pos); update(k); //print(tr[k]); } Matrix query(int k,int l,int r,int x,int y) { if(l>=x && r<=y) return tr[k]; int mid=(l+r)>>1; if(y<=mid) return query(k<<1,l,mid,x,y); if(x>=mid+1) return query(k<<1|1,mid+1,r,x,y); return query(k<<1,l,mid,x,y)*query(k<<1|1,mid+1,r,x,y); } }; /*}}}*/ int main() { //freopen("string.in","r",stdin); //freopen("string.out","w",stdout); cin>>n; s.resize(n+1); s[0]='$'; scanf("%s",&s[1]); cin>>m; for(int i=1;i<=n;i++) a[i]=s[i]-'0'; SegmentTree::build(1,1,n); while(m--) { int opt,l,r; cin>>opt>>l>>r; if(opt==1) { Matrix ans=SegmentTree::query(1,1,n,l,r); printf("%d\n",min(ans[0][0],ans[1][0]+1)); } else { if(a[l]^r) { a[l]=r; SegmentTree::modify(1,1,n,l); } } } }