LA 3716 DNA Regions

题目

LA 3716 DNA Regions

题解

对于固定的i，j可以作为左端点的前一个的条件是

$(i-j)*p/100>=(sum[i]-sum[j])$

即

$sum[i]*100 - i*p <= sum[j]*100-j*p$

（这里为了防止整除的时候出事情所以先两边乘个100）,如果设

$Ai=100*sum[i]-i*p$

那么即是要求

$min \{ j \} (j<i且Aj<=Ai)$

方法一：我比较智障用的权值线段树，第一次忘了把0扔进去，后来没有把$Ai$离散还T了一发，离散之后也比别人慢10倍，告诉我们线段树常数大的要死。

方法二：本来想过单调队列，但是因为直接取队首好像没法做，因为这样是找的最大的$Ai$,然后神犇说使得之前的$Ai$在队列中有序，单调增然后二分查找就行了。

代码

方法一 552ms

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=(1<<30);
const int maxn=150000+10;char s1[maxn],s2[maxn];
int n,p,val[maxn],sum[maxn],a[maxn],tmp[maxn];struct Node{int m;Node *lc,*rc;Node(){m=INF,lc=rc=NULL;}inline void UP(){m=min(lc->m,rc->m);}
}*root;#define mid ((l+r)>>1)
void build(Node* &p,int l,int r)
{p=new Node();if(l==r) return ;build(p->lc,l,mid);build(p->rc,mid+1,r);p->UP();
}void updata(Node* &p,const int &pos,const int &val,int l,int r)
{if(l==r){p->m=min(p->m,val);return ;}if(pos<=mid) updata(p->lc,pos,val,l,mid);else updata(p->rc,pos,val,mid+1,r);p->UP();
}int query(Node* &p,const int &L,const int &R,int l,int r)
{if(L<=l&&r<=R) return p->m;int ret=INF;if(L<=mid) ret=min(ret,query(p->lc,L,R,l,mid));if(mid<R ) ret=min(ret,query(p->rc,L,R,mid+1,r));return ret;
}inline void solve()
{scanf("%s%s",s1+1,s2+1);for(int i=1;i<=n;++i) {a[i]=(s1[i]!=s2[i]);sum[i]=sum[i-1]+a[i];tmp[i]=val[i]=100*sum[i]-i*p;}tmp[n+1]=val[n+1]=0;sort(tmp+1,tmp+n+2);int k=unique(tmp+1,tmp+n+2)-tmp-1;for(int i=1;i<=n+1;++i) val[i]=lower_bound(tmp+1,tmp+k+1,val[i])-tmp;build(root,1,k);int ans=-1;updata(root,val[n+1],0,1,k);for(int i=1;i<=n;++i) {ans=max(ans,i-query(root,val[i],k,1,k));updata(root,val[i],i,1,k);}if(ans==-1) printf("No solution.\n");else printf("%d\n",ans);
}int main()
{while(scanf("%d%d",&n,&p)==2){if(!n&&!p) break;solve();}return 0;
}

方法二： 46ms

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=(1<<30);
const int maxn=150000+10;char s1[maxn],s2[maxn];
int n,p,val[maxn],sum[maxn],a[maxn],A[maxn];int Que[maxn],id[maxn],Ql,Qr;inline void solve()
{scanf("%s%s",s1+1,s2+1);for(int i=1;i<=n;++i) {a[i]=(s1[i]!=s2[i]);sum[i]=sum[i-1]+a[i];A[i]=100*sum[i]-i*p;}int ans=-1;Ql=1,Qr=0;Que[++Qr]=0;id[Qr]=0;for(int i=1;i<=n;++i) {int pos=lower_bound(Que+Ql,Que+Qr+1,A[i])-Que;if(pos!=Qr+1) ans=max(ans,i-id[pos]);if(A[i] > Que[Qr]) Que[++Qr]=A[i],id[Qr]=i;}if(ans==-1) printf("No solution.\n");else printf("%d\n",ans);
}int main()
{while(scanf("%d%d",&n,&p)==2){if(!n&&!p) break;solve();}return 0;
}