0%

[洛谷 P1638] 逛画展

题目

题目链接

题目大意:给出一个长度为 $n$ 的序列,要求找到一段连续的子序列,满足子序列里出现所有 $1$ 到 $m$ 中的数。$1 \le n \le 10^6, 1 \le m \le 2000$。

思路

想了下 Two Pointers 应该算某种意义上的队列?

考虑用两个指针 $l, r$ 分别指向当前区间的左端点和右端点,维护一个 $s$ 表示当前区间内有多少不同的数,$v_i$ 表示当前区间里数 $i$ 的个数。

如果当前区间里的数不够就把 $r$ 往右移,够了的话就更新答案,然后把 $l$ 往右移。

然后就做完了。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int a[1000010], vis[2010];
int n, m, l = 1, r, ansl = 1, ansr, s, min = 0x3f3f3f3f;

int main() {
read(n), read(m);
ansl = 1, ansr = n;
for (int i = 1; i <= n; ++i) read(a[i]);
while (l <= n) {
while (s < m && r < n) {
++r;
if (!vis[a[r]]) ++s;
++vis[a[r]];
}
--vis[a[l]];
if (!vis[a[l]]) --s;
++l;
if (r - l < min && s == m) ansl = l, ansr = r, min = r - l;
}
printf("%d %d\n", ansl, ansr);
return 0;
}