https://vjudge.net/contest/422848
A - A Dangerous Maze
题意
给若干个门，每次从中随机选取一个门，每个门对应有一个数值$x_i$.若$x_i>0$，则你将在$x_i$分钟后离开迷宫，反之你将在$x_i$分钟后回到原地。现在，你每次闲置（没有等待某个$x_i$时）时都会随机选一个门进入。问离开迷宫的时间期望。
分析
列公式。
设期望为$E$，则其为离开迷宫的时间期望+选取$x_i<0$的门浪费掉的时间期望。
设n~1~是$x_i>0$的门个数,n~2~是$x_i<0$的门的个数。
先直接得出$E=\frac{\sum{(x_i>0?x_i:0)}}{n_1}×\frac{n_1}{n} + (E + \frac{\sum{(x_i<0?x_i:0)}}{n_2})×\frac{n_2}{n}$.
化简得到$E=\frac{\sum abs(x_i)}{n_1}$.
代码
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
| #include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
void done(int& s1, int& s2)
{
int u = __gcd(s1, s2);
s1 /= u, s2 /= u;
}
int main()
{
int t;
scanf("%d", &t);
int kase = 1;
while(t--)
{
int n; scanf("%d", &n);
int a[n];
int s1 = 0, n1 = 0, n2 = 0;
for(int i = 0; i < n; ++i){
scanf("%d", &a[i]);
if(a[i] > 0) n1++;
s1 += abs(a[i]);
}
if(n1){
done(s1, n1);
printf("Case %d: %d/%d\n", kase++, s1, n1);
}
else printf("Case %d: inf\n", kase++);
}
return 0;
}
|
B - Discovering Gold
分析
尝试期望dp。思路是设$dp[i]$表示从位置$i$到终点能获得的金币期望，则$dp[n]=n$,要求$dp[i]$只需要对$dp[i+1]$~$min\{dp[n],dp[i + 6]\}$求平均数，再加上$i$即可。
这是因为在位置$i$必然获得$i$元，然后根据$dp[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
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 105;
double dp[maxn];
int main()
{
int t, kase = 1;
scanf("%d", &t);
while(t--)
{
int n; scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lf", &dp[i]);
for(int i = n - 1; i >= 1; --i){
double tmp = 0;
for(int j = i + 1; j < i + 1 + min(6, n - i); ++j) tmp += dp[j];
dp[i] += (tmp / double(min(6, n - i)));
}
printf("Case %d: %.10lf\n", kase++, dp[1]);
}
return 0;
}
|
C - Race to 1 Again
分析
设$dp[i]$表示从$i$到1需要的次数期望，打$dp$的表即可。不过多注意细节。
注意在找一个数$x$的因子时，使用遍历$i$可以只遍历到$\sqrt x$，但注意此时它除了因子$i$还有一个$\frac{x}{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
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 100500;
double dp[maxn] = {0};
int main()
{
int t;
int n;
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i < maxn; ++i){
n = 0;
int j;
for(j = 2; j * j < i; ++j){
if(i % j == 0){
dp[i] += dp[j] + dp[i / j];
n += 2;
}
}
if(j * j == i){
n++;
dp[i] += dp[j];
}
n += 2;
dp[i] += n;
dp[i] /= n - 1;
}
scanf("%d", &t);
int kase = 1;
while(t--)
{
scanf("%d", &n);
printf("Case %d: %.7lf\n", kase++, n == 1 ? 0 : dp[n]);
}
return 0;
}
|
D - Birthday Paradox
题意
现在已知在地球上，人群人数大于等于23时，其中有2个人生日相同的概率大于50%。
现在在另外一个公转周期为$x$天的星球上，问有2个人生日相同的概率大于50%时，人群至少要多大？
分析
高中概率题，比较水
代码
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
| #include <bits/stdc++.h>
using namespace std;
int kase = 0;
void work(double x)
{
double now = 1;
double i = 0;
while(now > 0.5)
{
now *= (x - i) / x;
i++;
}
printf("Case %d: %.0lf\n", ++kase, i - 1);
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
double n;
scanf("%lf", &n);
work(n);
}
return 0;
}
|
G - Dice(III)
题意
给一个N面骰子，每面相同，问投多少次，才能让所有面都正面朝上一次？求期望。
分析
递推一下。设$dp[i]$表示$n$面骰子$i$面朝上过一次的期望，$dp[1]=1$.
则$dp[i]=dp[i-1]+\frac{n}{n-(i-1)}$.
即$i$面朝上期望=$i-1$面朝上期望+要多投一面朝上的期望.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
const int maxn = 100005;
double dp[maxn];
int n;
int main()
{
int t;
int kase = 1;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
dp[1] = 1;
for(int i = 2; i <= n; ++i){
dp[i] = dp[i - 1] + double(n) / double(n - (i - 1));
}
printf("Case %d: %.8f\n", kase++, dp[n]);
}
return 0;
}
|
H - Island of Survival
分析
首先贪心，为了避免老虎占比变大，遇到鹿肯定不要杀。
然后就是讨论+dp了。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
double dp[maxn][maxn];
int t, d;
int main()
{
int T;
scanf("%d", &T);
int kase = 1;
while(T--)
{
scanf("%d%d", &t, &d);
if(t % 2 != 0){
printf("Case %d: 0.00000000\n", kase++);
continue;
}
memset(dp, 0, sizeof(dp));
dp[t][d] = 1;
for(int i = t; i >= 0; i -= 2){
for(int j = d; j >= 0; --j){
int sum = i * j + i * (i - 1) / 2 + i;
if(!sum) continue;
if(j) dp[i][j - 1] += dp[i][j] * i * j / sum;
if(i >= 2) dp[i-2][j] += dp[i][j] * i * (i - 1) / 2 / sum;
}
}
double ans = 0;
for(int i = 0; i <= d; ++i) ans += dp[0][i];
printf("Case %d: %.10f\n", kase++, ans);
}
return 0;
}
|
