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;
} |