场上过了 C 但没有过 D，现在想来，C 和 D 的难度其实差距并不大，只是 D
需要思考角度找对而已。
C 题解
设 表示从 出发到达 的最大概率，那么在计算 时，我们提出所有出边 的
形成一个序列，我们要计算的就是这个序列在进行操作后所能得到的最大的结果。
假设
的选取方法已经确定，我们只需算出序列中每个元素最后保留的概率即可。设
表示每个元素的优先级，每次选
时都是选剩余元素中 最大的那个。设 表示优先级为
的元素最后被保留的概率，下文称其为贡献系数 。
你发现每个元素的贡献系数只和优先级有关，所以让最后的结果最大，只需让
第 小的点的贡献系数也是第 小的即可。于是重点在于怎么计算 。
设 表示对于一个元素，有
个优先级低于它的，有
个优先级高于它的，它最后被保留下来的概率。转移就是 。初值为
。
设序列总长为 。那么 就是 。因为优先级越大的元素被保留的概率显然越大，所以 。设 的所有出边 对应的 从小到大排序的结果为 ，那么 。
于是本题就做完了。时间复杂度 。
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
| const int N = 5e3 + 5,M = 2e5 + 5;
int n,m;
vector<int> G[N];
double f[N];
double dp[N][N];
inline void work() {
cin >> n >> m;
for(int i = 1;i <= n;i++) G[i].clear();
for(int i = 1;i <= m;i++) {
int u,v;
cin >> u >> v;
G[u].push_back(v);
}
f[n] = 1;
for(int i = n - 1;i >= 1;i--) {
double sum = 0;
vector<double> tmp;
for(auto j : G[i]) tmp.push_back(f[j]);
sort(tmp.begin(),tmp.end());
for(int k = 0;k < tmp.size();k++)
sum += tmp[k] * dp[k][tmp.size() - 1 - k];
f[i] = sum;
}
printf("%.10lf\n",f[1]);
}
int main() {
int n = 5000;
for(int i = 0;i <= n;i++) dp[i][0] = 1.0 / (i + 1);
for(int i = 0;i <= n;i++)
for(int j = 1;j <= n;j++) {
int all = i + j + 1;
if(j >= 2) dp[i][j] += dp[i][j - 2] * (j - 1) / all;
dp[i][j] += dp[i - 1][j - 1] * i / all;
}
int T;
cin >> T;
while(T--) work();
return 0;
}
|
D 题解
一开始设 表示从 走到 的期望步数，后来发现根本做不得。主要是
的递推式是二阶的，还要主元法解方程，很难套回到原题的限制中去。所以不妨换种思路，设
表示 走到 的期望步数，那么最后的答案就是 。
列 的式子：。
推式子可以得到 。
手算前几项容易找到规律：，证明归纳即可。
那么这个就很容易套到 DP 中去了。设 表示 DP 了 ，
的答案。暴力转移可以做到 。
但注意到最优解的
肯定是单调不降的，所以 ，转移就是调和级数复杂度了，时间复杂度 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
typedef double db;
int n,m;
db f[N][N];
int main() {
cin >> n >> m;
f[0][0] = 0;
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++) {
f[i][j] = 1e9;
for(int k = 1;k <= j && k * (n - i + 1) <= m;k++)
f[i][j] = min(f[i][j],f[i - 1][j - k] + 2.0 * (j - k) / k);
}
db ans = 1e9;
for(int i = 1;i <= m;i++)
ans = min(ans,f[n][i]);
printf("%.10lf\n",ans + n);
return 0;
}
|