ABC见上一篇。
感觉这场比赛很有数学气息。
D：
显然必须要贴着之前的人坐下。
首先考虑没有限制的方案数。就是2n - 1（我们把1固定，其他的都只有两种方案，放完后长度为n）
我们发现对于一个限制，比它小的限制只有可能在它的一边。
于是对于有限制的一段，我们可以找到最靠近边界的两个限制，取其中最大的限制，递归计算向比它小的限制的方向走它的限制步所覆盖的一段，这一段应该包含目前区间内所有的限制，剩下的就是没有限制的，可以直接计算。
mycode：
/*
* 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:
/*
* 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;
}