12174_page-0001.jpg

 

滑动窗口

最多只有s种情况，分别对应s种窗口。事先检查总共n个长度为s或者最后几个不完整的窗口分别是否只包含不重复元素。再枚举s种情况，如果对应窗口都正确，则答案+1.

检查是否只包含不重复元素，和Unique Snow题中类似，用到了滑动窗口。

本题就是在处理两端不完整窗口时需要小心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int t, n, m;
int a[maxn], pl[maxn], pr[maxn];
map<int, int>mpl, mpr;
bool ok[maxn];
int main() {
	scanf("%d", &t);
	while (t--) {
		mpl.clear(); mpr.clear();
		memset(ok, 0, sizeof(ok));
		scanf("%d%d", &n, &m);
		for (int i = 0; i < m; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 0; i < m; i++) {
			if (!mpl.count(a[i])) {
				mpl[a[i]] = i;
				pl[i] = -1;
			}
			else {
				pl[i] = mpl[a[i]];
				mpl[a[i]] = i;
			}
		}
		for (int i = m - 1; i >= 0; i--) {
			if (!mpr.count(a[i])) {
				mpr[a[i]] = i;
				pr[i] = INF;
			}
			else {
				pr[i] = mpr[a[i]];
				mpr[a[i]] = i;
			}
		}
		int R = m - 1, L = m - 1;
		while (L >= 0 && R >= 0) {
			while (R - L + 1 > n)R--;
			if (R == m - 1) {
				
				if (pr[L] > R) {
					ok[L] = 1;
					if (R - L + 1 == n)R--;
					else L--;
				}
				else R = pr[L] - 1;
			}
			else {
				while (R - L + 1 < n&&L >= 0) {
					L--;
					if (pr[L] <= R) {
						R = pr[L] - 1;
					}
				}
				if (L >= 0)ok[L] = 1;
				R--;
			}
		}
		int ans = 0;
		R = 0;
		while (R < min(n, m)) {
			if (pl[R] >= 0)break;
			bool flg = 1;
			for (int i = R + 1; i < m; i += n) {
				if (!ok[i]) {
					flg = 0;
					break;
				}
			}
			if (flg)ans++;
			R++;
		}
		if (m < n&&R == m)ans = n;
		cout << ans << endl;
	}
	return 0;
}