尺取法70pts求助
查看原帖
尺取法70pts求助
285617
黑影洞人楼主2022/10/25 19:41
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#define N 1145
#define M 114514
using namespace std;
int ans,n,m,cnt,a[N],b[M],tmp[M],vis[N],len;
bool ck[M];
int res,rle=2147483647;
string s;
map<string,int>mp;
void add(int i){
	if(tmp[b[i]]==0&&vis[b[i]])ans++;
	tmp[b[i]]++;
	len++;
	if(ans==res)rle=min(rle,len);
}
void del(int i){
	if(tmp[b[i]]==1&&vis[b[i]])ans--;
	tmp[b[i]]--;
	len--;
	if(ans==res)rle=min(rle,len);
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s;
		if(mp.find(s)==mp.end())mp[s]=++cnt;
		a[i]=mp[s];
		vis[a[i]]++;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		cin>>s;
		if(mp.find(s)==mp.end())mp[s]=++cnt;
		b[i]=mp[s];
		if(ck[b[i]])continue;
		if(vis[b[i]])res++,ck[b[i]]=1;
	}
	if(!res)return puts("0\n0"),0;
	else printf("%d\n",res);
	int l=1,r=0;
	while(r<=m){
		add(++r);
		if(ans==res)rle=min(rle,len);
		//printf("%d %d\n",l,r);
		while(l<=r&&ans==res)del(l++);
		//printf("%d %d\n",l,r);
		if(ans==res)rle=min(rle,len);
	}
	printf("%d",rle);
	return 0;
}
2022/10/25 19:41
加载中...