提高3Day4T4

常规
,
1

提高三Day4 T4

题目描述：

定义一个字符串 s 中字符 c 的价值为 s 中出现的最长连续字符 c 的个数。

现在对于一个询问，给出一个字符 c_i 和数字 m_i ，表示最多修改字符串中的 m_i 个字符，问字符 c_i 的价值最大为多少

输入格式

第一行一个数字 n ，表示字符串的长度

接下来一个字符串 s ，表示初始字符串

第三行包含一个数字 q ，表示询问的个数

接下来 q 行，每行一个数字 m_i 和一个字符 c_i ，表示能够修改的次数以及需要计算价值的字符

输出格式

对于每一个询问，输出该次询问的答案

数据范围

1≤ n ≤1500

1≤ q ≤200000

1≤ m_i ≤ n , c_i 为小写英文字母

Sol:

由于数据范围只给了一个，考场直接写正解

刚开始的时候由于没有注意到最长连续(最长是我后面加的)，写了个贪心，写完才发现题目没读懂，重头来过

发现 n 比较小 , q 比较大，考虑 n^2 预处理后 O(1) or O(logn) 查询

我们可以预处理出对于每一个字符 c ,某一个 m 下的答案最值

而这个 m 其实就是将任意几个 c 串连起来的花费

显然， m 越大，答案越大，满足一个单调性，查询的时候用二分查找最大的边界值，然后加上余下的就是答案

Code :

第一步先处理除所有字符的连续区间

pos代表字符区间(l,r),tot[c]代表字符c在字符串中的总数

#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int n;
int precost[30][N],tot[30];
int maxn[30][N];
string s;
vector<pair<int,int> >pos[30];
vector<int>cas[30];
int main(){
	cin>>n>>s;
	s=" "+s;
	int last=1;
	tot[s[1]-'a'+1]++;
	for(int i=2;i<=n;i++){
		tot[s[i]-'a'+1]++;
		if(s[i]!=s[last]){
			pos[s[last]-'a'+1].push_back(make_pair(last,i-1));
			last=i;
		}
	}
   pos[s[last]-'a'+1].push_back(make_pair(last,n));

第二步处理出连接连续串 (a_i,a_i+1,..a_j) 需要的花费，这里是前缀和

for(int k=1;k<=26;k++){
	for(int i=1;i<pos[k].size();i++){
		int last=pos[k][i-1].second,now=pos[k][i].first;
		precost[k][i]=precost[k][i-1]+now-last-1;
	}
}

第三步是真正的预处理，maxn[k][Cost]代表字符k在Cost的花费下的最大答案，cas[k]代表字符k的最优答案总数

由于可能出现aabaa bbbb abbba的情况，连接前两个a串需要1花费，变为5，后两个需要3花费，变为5，但是用1个花费连接前两个，再用2花费扩宽前面可以得到7，比后面优，所以要排除后面的做法，也就是将要排除的maxn[k][?]设为0，不加人cas中

记住加入边界

	for(int k=1;k<=26;k++){
		int siz=pos[k].size();
		for(int i=0;i<siz;i++){
			for(int j=i;j<siz;j++){
				int Cost=precost[k][j]-precost[k][i],
					Val=pos[k][j].second-pos[k][i].first+1;
				maxn[k][Cost]=max(maxn[k][Cost],Val);
			}
		}
		int last=0;
		for(int i=1;i<=n;i++){
			if(maxn[k][last]+i-last>=maxn[k][i]){
				maxn[k][i]=0;
			}
			else{
				last=i;
			}
		}
		cas[k].push_back(0); 
		for(int i=1;i<=n;i++){
			if(maxn[k][i])	cas[k].push_back(i);
		}
		cas[k].push_back(100005);
	}

然后就是简单的查询

int q;
	cin>>q;
	while(q--){
		int m;
		char c;
		cin>>m>>c;
		int k=c-'a'+1;
		auto p=lower_bound(cas[k].begin(),cas[k].end(),m);
		if(*p!=m)	p--;
		cout<<maxn[k][*p]+min(n-tot[k],m)-*p<<"\n";
	}
	return 0;
}
6 个赞