ABC见上一篇。
感觉这场比赛很有数学气息。
D：
显然必须要贴着之前的人坐下。
首先考虑没有限制的方案数。就是2n - 1（我们把1固定，其他的都只有两种方案，放完后长度为n）
我们发现对于一个限制，比它小的限制只有可能在它的一边。
于是对于有限制的一段，我们可以找到最靠近边界的两个限制，取其中最大的限制，递归计算向比它小的限制的方向走它的限制步所覆盖的一段，这一段应该包含目前区间内所有的限制，剩下的就是没有限制的，可以直接计算。
mycode：
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100 |
/* * Problem: Sereja and Cinema * Author: Shun Yao */#include <string.h>#include <stdlib.h>#include <limits.h>#include <assert.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <time.h>#include <map>#include <set>#include <list>#include <stack>#include <queue>#include <deque>#include <string>#include <vector>#include <bitset>#include <utility>#include <iomanip>#include <numeric>#include <sstream>#include <iostream>#include <algorithm>#include <functional>//using namespace std;const
int
MAXN = 100010, MOD = 1000000007LL;int
n, a[MAXN], sum[MAXN];long
long
inv[MAXN], f[MAXN], finv[MAXN];long
long
comb(int
x, int
y) { return
f[x + y] * finv[x] % MOD * finv[y] % MOD;}long
long
func(int
l, int
r) { long
long
ans; if
(sum[l - 1] == sum[r]) { ans = 1; int
i; for
(i = l; i < r; ++i) ans = (ans << 1) % MOD; return
ans; } int
p, q; for
(p = l; p <= r; ++p) if
(a[p]) break; for
(q = r; q >= l; --q) if
(a[q]) break; if
(p == q && a[p] == 1) return
comb(p - l, r - p); ans = 0; int
x, y; if
(a[p] >= a[q]) { x = p; y = x + a[p] - 1; if
(y >= q && y <= r) ans += func(x + 1, y) * comb(x - l, r - y); } if
(a[p] <= a[q]) { y = q; x = y - a[q] + 1; if
(x >= l && x <= p) ans += func(x, y - 1) * comb(x - l, r - y); } return
ans % MOD;}int
main(/*int argc, char **argv*/) { int
i; scanf("%d", &n); sum[0] = 0; for
(i = 1; i <= n; ++i) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + (a[i] != 0); } inv[1] = 1; for
(i = 2; i < MAXN; ++i) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; f[0] = finv[0] = 1; for
(i = 1; i < MAXN; ++i) { f[i] = f[i - 1] * i % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } printf("%I64d", func(1, n)); fclose(stdin); fclose(stdout); return
0;} |
E：
这个题目我们可以发现实际上就是取一个区间的数集{a[i]},所求就是:1/2 * a[1] + 1/4 * a[2] + 1/8 * a[3] + ……，由于精度所以我们可以忽视a[50]以后的。
我们可以考虑一个数为结果带来的代价。我们考虑比V大的数，Let the position of elements on the left: p1> p2> ... >
Ps1. And positions right: q1 < q2 < ... < qs2.这样它带来的代价就是
。
mycode:
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95 |
/* * Problem: Sereja and Dividing * Author: Shun Yao */#include <string.h>#include <stdlib.h>#include <limits.h>#include <assert.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <time.h>#include <map>#include <set>#include <list>#include <stack>#include <queue>#include <deque>#include <string>#include <vector>#include <bitset>#include <utility>#include <iomanip>#include <numeric>#include <sstream>#include <iostream>#include <algorithm>#include <functional>//using namespace std;const
int
MAXN = 300010;int
n, a[MAXN];std::vector<std::pair<int, int> > v;std::set<int> s;double
solve(int
x) { double
two, c1, c2; int
cnt, prev, y; s.insert(x); std::set<int>::iterator it = s.find(x); two = 1.0; cnt = 0; prev = x; c1 = 0.0; while
(cnt < 50) { y = *(--it); c1 += (prev - y) * two; if
(y == 0) break; ++cnt; two /= 2.0; prev = y; } it = s.find(x); two = 1.0; cnt = 0; prev = x; c2 = 0.0; while
(cnt < 50) { y = *(++it); c2 += (y - prev) * two; if
(y == n + 1) break; ++cnt; two /= 2.0; prev = y; } return
c1 * c2;}int
main(/*int argc, char **argv*/) { int
i; double
ans; scanf("%d", &n); for
(i = 1; i <= n; ++i) scanf("%d", a + i); for
(i = 1; i <= n; ++i) v.push_back(std::make_pair(-a[i], i)); std::sort(v.begin(), v.end()); s.insert(0); s.insert(n + 1); ans = 0.0; for
(i = 0; i < n; ++i) ans += solve(v[i].second) * a[v[i].second]; printf("%.9lf", ans / 2.0 / n / n); fclose(stdin); fclose(stdout); return
0;} |
原文：http://www.cnblogs.com/hsuppr/p/3518053.html