70分代码求调,玄关
  • 板块P1381 单词背诵
  • 楼主wxw_zl
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/27 20:21
  • 上次更新2024/4/27 21:48:46
查看原帖
70分代码求调,玄关
469487
wxw_zl楼主2024/4/27 20:21

思路:用map分别记录一下每个字符串是不是要背的,然后双指针向后跳,用map看当前区间的贡献。

#include<bits/stdc++.h>
#define rise(i,l,r) for(int (i)=(l);(i)<=(r);(i)++)
#define fall(i,r,l) for(int (i)=(r);(i)>=(l);(i)--)
#define pii pair<int,int>
using namespace std;
const int maxn=1e5+10;
int n,m,cnt[maxn];
string a[1005],b[maxn];
map<string,int> mp;
map<string,bool>have;
vector<string>c;
void in() {
	cin>>n;
	rise(i,1,n) {
		cin>>a[i];
		have[a[i]]=1;//标记该单词要背 
	}
	cin>>m;
	rise(i,1,m)cin>>b[i];
}
pii solve() {
	int l=1,r=1,cnt=0,res=0,res_len=INT_MAX;
	while(l<=m&&r<=m+1) {
		while((b[r]!=b[l]||l==r)&&r<=m) {
			if(have[b[r]]==0) {
				r++;
				continue;
			}
			cnt+=(mp[b[r]]==0);
			mp[b[r]]++;
			if(cnt>res)res=cnt,res_len=r-l+1;
			else if(cnt==res)res_len=min(r-l+1,res_len);
			r++;
//			cout<<"循环1:"<<l<<" "<<r<<endl;
		}
		if(b[l]==b[r]) {
			l++;
			if(have[b[r]])res_len=min(res_len,r-l+1);
			else r--;
		}
		while((have[b[l]]==0||mp[b[l]]>1)&&l<=m&&l<=r) {
			if(have[b[l]])mp[b[l]]--;
			l++;
			res_len=min(res_len,r-l+1);
		}
		if(r==m+1&&have[b[l]]==1) {
			res_len=min(res_len,m-l+1);
			break;
		}
	}
	return {res,res_len};
}
int main() {
//	ios::sync_with_stdio(false);
	in();
	pii output=solve();
	cout<<output.first<<endl<<output.second;
	return 0;
}
/*
3
a
b
c
5
a
b
a
b
c
*/
2024/4/27 20:21
加载中...