Bzoj 1303(前缀和+乘法原理)

BZOJ 1303
因为题目是$1-n$排列,所以$b$只会出现一次,那么我们记录$b$的位置$p$,然后我们不难发现当$b$旁边连续的几个数中大于$b$和小于$b$的数的个数相同就会对答案作出贡献。我们记录左边大于$b$的数为$1$,小于$b$的数为$-1$,也就是差分序列(括号序列),然后从$p-1$到$1$求前缀和,记录在$sum$中,然后$l$数组就是记录某个前缀和出现的次数。右边同理,但是大于$b$的数为$-1$,小于$b$的数为$1$。然后根据乘法原理,左边有$l_i$个可匹配,右边有$r_i$个可匹配,答案就是$\sum_{i=-n}^n l_ir_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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5, N = 100000;
int n, b, p, a[MAXN], l[MAXN*2], r[MAXN*2];
void clean() {}
void solve() {
clean();
for (int i=1;i<=n;i++) {
scanf("%d", &a[i]);
if (a[i] == b) p = i;
}
int sum = 0;
l[N] = r[N] = 1;
for (int i=p-1;i>0;i--)
sum += (a[i] > b) ? 1 : -1, l[sum + N]++;
sum = 0;
for (int i=p+1;i<=n;i++)
sum += (a[i] < b) ? 1 : -1, r[sum + N]++;
int ans = 0;
for (int i=N-n;i<=N+n;i++) ans += l[i] * r[i];
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &b), solve();
return 0;
}
------ 本文结束 ------