0%

[NOIp2011] 选择客栈

题目

题目链接

题目大意:给出长度为 $n$ 的序列 $\\{a_n\\}, \\{b_n\\}$,找出有多少对 $(i, j)$ 满足 $a_i = a_j, \exists k \in [i, j] \text{ st. } b_k \le p, i \ne j$。$1 \le n \le 2 \times 10^6, 1 \le p \le 100$。

思路

算法一

每次枚举 $i, j, k$ 并判断,时间复杂度 $O(n ^ 3)$。

算法二

预处理 $f_i = f_{i - 1} + [b_i \le p]$,每次枚举 $(i, j)$ 并判断。

时间复杂度 $O(n ^ 2)$。

算法三

考虑枚举 $j$,用类似 vector 的东西存下相同的 $a_i$ 的 $i$,二分找出最大的 $i$ 满足 $f_j - f_{i - 1} > 0$。

时间复杂度 $O(n \log n)$。

算法四

考虑枚举 $j$,维护 $cnt_i$ 表示 $i$ 之前有多少个 $k$ 满足 $a_i = a_k$,$lst_i$ 表示 $a_i$ 上次出现的位置,用 $pos$ 表示离 $j$ 最近的满足 $b_i \le p$ 的点,$s_i$ 表示 $a_i$ 当前的方案数。

每次遇到一个点时先判断是否满足 $b_i \le p$,然后判断当前的 $pos$ 是否大于等于 $lst_{a_{i}}$,然后更新答案。

代码

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

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;

LL s[10010], cnt[10010], lst[10010];
LL ans;
int n, k, p, a, b, pos;

int main() {
read(n), read(k), read(p);
for (int i = 1; i <= n; ++i) {
read(a), read(b);
if (b <= p) pos = i;
if (pos >= lst[a]) s[a] = cnt[a];
lst[a] = i;
ans += s[a];
++cnt[a];
}
printf("%lld\n", ans);
return 0;
}

后记

以后就把 OI 当爱好了 ^^。