I.一个字符串游戏
一个很有意思的题，假设sum[ i ]为前 i 个字符不同的个数，假设[ L , R ]是合法的，那么 可以变形一下：，我可以令，那么对于每个x，我只要找到最小的一个k（k<x）...
一个很有意思的题，假设sum[ i ]为前 i 个字符不同的个数，假设[ L , R ]是合法的，那么![\"\\frac{sum[r]-sum[l-1]}{r-(l-1)}<=\\frac{p}{100}\"](\"/images/csdn/15455685541T65n4S5568554.gif\")
可以变形一下：![\"100*sum[r]-p*r<=100*sum[l-1]-p*(l-1)\"](\"/images/csdn/1545568555BAuP1545568555.gif\")
，我可以令![\"f(x)=100*sum[x]-p*x\"](\"/images/csdn/15455685551hT54556r85N55.gif\")
，那么对于每个x，我只要找到最小的一个k（k<x），使得f(x)<=f(k)即可，注意这样求出来的区间是[ k+1, x ]，不是[ k , x ]，还有就是要设置初始值f(0)=0，这些操作可以借助区间最大值线段树实现。
#include<bits/stdc++.h>
#define ls o*2
#define rs o*2+1
using namespace std;
const int maxn=2e5,inf=1e9;
char s[maxn],t[maxn];
int mx[maxn*4],sum[maxn],p,n;
void up(int o,int l,int r,int k,int v)
{
if(l==r)
{
mx[o]=v;
return;
}
int m=(l+r)/2;
if(k<=m)up(ls,l,m,k,v);
else up(rs,m+1,r,k,v);
mx[o]=max(mx[ls],mx[rs]);
}
int qu(int o,int l,int r,int v)
{
if(mx[o]<v)return inf;
if(l==r)return l;
int m=(l+r)/2;
if(mx[ls]>=v)return qu(ls,l,m,v);
else return qu(rs,m+1,r,v);
}
int main()
{
cin>>p>>s+1>>t+1;
n=strlen(s+1);
for(int i=1;i<=n*4;i++)
mx[i]=-inf;
int ans=0;
up(1,0,n,0,0);//特别重要
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1];
if(s[i]!=t[i])sum[i]++;
int v=100*sum[i]-p*i;
int k=qu(1,0,n,v);
up(1,0,n,i,v);
ans=max(ans,i-k);
}
cout<<ans<<endl;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：WebService就是这么简单 下一篇：选择排序就这么简单
