[8.16考试] 玩具
分类:
IT文章
•
2022-10-12 17:19:50
Problem
儿时的玩具总是使我们留恋,当小皮还是个孩子的时候,对玩具更是情有独钟。小皮是一个兴趣爱好相当广泛且不专一的人,这这让老皮非常地烦恼。也就是说,小皮在不同时刻所想玩的玩具总是会不同,而有心的老皮也会尽量
满足他的要求,帮他买一些新玩具。
一开始小皮有一个长度为N的玩具序列 , 小皮的玩具可以用小写字母a，b，c,...，z表示。小皮可能会有q种需求每种需求用一个二元组(x,y)表示，代表小皮在此时最喜欢x这种玩具，他希望老皮帮他买回y个玩具x，
小皮希望知道假如用这y个玩具去**替换原来的玩具**,最多可以产生多长的连续为x的这种玩具序列。
### 输入格式
第一行一个整数N，代表小皮有N个玩具。
接来下一行一个由小写字母构成的字符串,表示初始的玩具序列。
接下来一个整数q，代表小皮有q种需求。
接下来q行，每一行一个二元组(x,y)。
### 输出格式
q行，每一行一个答案。
### 样例输入
5
aabaa
2
a 1
b 2
### 样例输出
5
3
### 数据范围：$$N<=2000,q<=3*10^5,1<=y<=N$$
## Solution
N<=2000，可以想到可能是O($n^2$) 的算法。O($n*q$)发现是过不了的，
所以我们想到离线去做。设$f[i][j]$代表从1到i全部变成字母j需要用多少次。$ff[i][j]$代表用i次操作把字母j变成的连续序列最长的长度是多长。
我们只需输出$ff[i][j]$就可以了。然后我们想怎么得出$ff$数组就行了。
我们先跑一遍，把f数组处理出来，接下来枚举左右端点，处理出ff数组
。可以发现需要递推ff数组
$$ff[i][j]=max(ff[i][j],ff[i-1][j]+1)$$
代码如下
```cpp
#include
#include
#include
#include
using namespace std;
int f[2010][30],ff[2010][30],mx[20100];
char s[201010];
int main()
{
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
char ss[3];
int n,m,x;
cin>>n;
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
int k=s[i]-'a';
for(int j=0;j<26;j++)
if(k==j)
f[i][j]=f[i-1][j];
else
f[i][j]=f[i-1][j]+1;
}
//cout<>q;
for(int i=1;i<=q;i++)
{
scanf("%s%d",ss,&x);
int k=ss[0]-'a';
printf("%d
",min(n,ff[x][k]));
}
}
```
### 博主蒟蒻，可以随意转载，但必须附上原文链接[k-z-j](https://www.cnblogs.com/kzj-pwq/)。[9][0]
