求调,玄关
查看原帖
求调,玄关
488395
Proxima_Centauri楼主2023/12/6 22:41

40pts,尺取法,第一问对了,第二问WA

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
string a[1010];
string s[100010];
map<string, int> vis, t;
int main()
{
	int n, m;
	cin >> n;
	for (int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		vis[a[i]];
		t[a[i]] = 1;
	}
	cin >> m;
	int k = 0;
	for (int i = 1; i <= m; i++) 
	{
		cin >> s[i];
		if (t[s[i]] == 1) k++;
		if (t[s[i]] >= 1) t[s[i]]++;
	}
	if (k == 0)
	{
		cout << 0 << endl << 0 << endl;
		return 0;
	}
	int sum = 0, ans = 1e9;
	for (int l = 1, r = 0; l <= m; l++)
	{
		while (sum != k && r < m)
		{
			if (!vis.count(s[++r])) continue;
			vis[s[r]]++;
			if (vis[s[r]] == 1) sum++;
		}
		if (ans > r - l + 1 && sum == k) ans = r - l + 1;
		vis[s[l]]--;
		if (!vis[s[l]]) sum--;
	}
	cout << k << endl << ans << endl;
	return 0;
 } 
2023/12/6 22:41
加载中...