牛客多校第十场

A: Blackjack

思路

一个随机排列的数列,问前缀和大于$a$的时候小于$b$的概率

思路

img1

img2

大意就是枚举最后一次抽的牌的点数,找在剩下的$n-1$个牌中,前$i$个牌的前缀和范围在$[a-x,min(a,b-x)]$的概率

概率是$\frac{i!(n-i-1)!}{n!}$,这个概率可以预处理出来。

然后就是用可逆背包和滚动数组来求dp

AC代码

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
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 510;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

double dp[2][maxn][maxn], p[maxn];
int x[maxn];

int main() {
int n, a, b;
scanf("%d %d %d", &n, &a, &b);
dp[0][0][0] = 1;
for (int i = 1; i <= n; i ++) {
scanf("%d", &x[i]);
memcpy(dp[i&1], dp[(i&1)^1], sizeof(dp[0]));
for (int j = 1; j <= n; j ++)
for (int k = x[i]; k <= b; k ++)
dp[i&1][j][k] += dp[(i&1)^1][j-1][k-x[i]];
}
p[1] = 1./n;
for (int i = 2; i <= n; i ++)
p[i] = p[i-1] * (i-1) / (n-i+1);
double ans = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++)
for (int k = x[i]; k <= b; k ++)
dp[n&1][j][k] -= dp[n&1][j-1][k-x[i]];
for (int j = 0; j < n; j ++)
for (int k = max(0, a-x[i]+1); k <= a && k + x[i] <= b; k ++)
ans += dp[n&1][j][k] * p[j+1];
for (int j = n; j >= 1; j --)
for (int k = b; k >= x[i]; k --)
dp[n&1][j][k] += dp[n&1][j-1][k-x[i]];
}
printf("%.15f\n", ans);
return 0;
}

H: Wood Processing

http://www.orzff.cn/f1b7e3b7/

---------Thanks for your attention---------