90分 #2WA 求助
  • 板块P1381 单词背诵
  • 楼主Ray662
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/5 10:15
  • 上次更新2024/8/5 11:05:35
查看原帖
90分 #2WA 求助
502658
Ray662楼主2024/8/5 10:15
#include <bits/stdc++.h>
#define int long long
#define _for(i, a, b)  for (register int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 1e5 + 5;
int n, m, ans1, ans2;
string tmp, s[N];
map<string, int> vis, f;
inline bool valid(int x) {
	int cnt = 0;
	f.clear();
	_for (i, 1, x) {
		if (! f[s[i]] && vis[s[i]] == 2)  cnt ++ ;
		f[s[i]] ++ ;
	}
	if (cnt == ans1)  return 1;
	_for (i, 2, m - x + 1) {
		if (f[s[i - 1]] == 1 && vis[s[i - 1]] == 2)  cnt -- ;
		if (! f[s[i + x - 1]] && vis[s[i + x - 1]] == 2)  cnt ++ ;
		f[s[i - 1]] -- , f[s[i + x - 1]] ++ ;
		if (cnt == ans1)  return 1;
	}
	return 0;
}
signed main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	_for (i, 1, n)  cin >> tmp, vis[tmp] = 1;
	cin >> m;
	_for (i, 1, m) {
		cin >> s[i];
		if (vis[s[i]] == 1)  ans1 ++ , vis[s[i]] = 2;
	}
	int l = ans1, r = m, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (valid(mid))  ans2 = mid, r = mid - 1;
		else  l = mid + 1;
	}
	cout << ans1 << endl << ans2 << endl;
	return 0;
}
2024/8/5 10:15
加载中...