CF1187题解

前言

这套题相对来讲难度不算高，并且质量也很好，建议尝试

CF1187A

一眼秒，但我没有
考虑s，t只有这一种排列方式，所以取一下 \(max(n-s,n-t)\)

#include<bits/stdc++.h>
using namespace std;
int T,n,s,t;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&s,&t);
		printf("%d\n",n-min(s,t)+1);
	}
}

CF1187B

一眼秒，先预处理出每一个字母出现的次数所对应的下标
然后对于每个串O（1）查询即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int ans,n,m;
int num[30][N],lst[30],tot[30];
char s[N],c[N];
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		num[s[i]-'a'][++lst[s[i]-'a']]=i;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%s",c+1);
		int len=strlen(c+1);
		for(int j=1;j<=len;j++){
			tot[c[j]-'a']++;
		}
		for(int j=0;j<=25;j++){
			ans=max(num[j][tot[j]],ans);
			tot[j]=0;
		}
		printf("%d\n",ans);
		ans=0;
	}
}

CF1187C

考虑t=0时当且仅当区间内存在一个严格降序，这显然是不好处理的
t=1时区间内所有的数都要满足不降序列，这显然是很好处理的
我们先设 \(z[i]=1\) 为 \(a[i]<=a[i+1]\)，为0则反之或不确定
然后和为