本人暂时感觉一些简单题的解题方法有:
1。迭代的升级版:用线性数列的方法推矩阵,最后高斯消元。

  1. 考虑每个的期望(设当前状态到终点状态的期望),一般会形成一个有环的Dp,然后高斯消元。

bzoj3270

利用期望dp,利用概率*总期望=期望得出概率。


bzoj3036

一个显然的做法为dp[i]表示i到终点的期望
第二种做法就是利用期望的线性性,求每条边对期望的贡献,即每条边的长度乘以被经过的期望次数。所以我们可以考虑算出每条边的期望经过次数。
求边的期望经过次数处理叫麻烦,我们可以考虑求点的期望经过次数,用dp(u)表示,那么对于一个出点为u的边,它的期望经过次数便为w*dp(u).然后点这个就可以和上题一样,$dp(v) \longleftarrow dp(u)*\frac{1}{|G_{u}|}$,据sengxian大大说

因为这种方法计算答案十分的便捷,而且适用范围广,所以这种『利用期望的线性性质,单独计算贡献的方法』是我们计算期望首选的方法.


bzoj3450

设当前出现长度为i的comb的概率为$C_{i}$
每次需要$\sum{C_{i}*(2i+1)}$和$\sum C_{i}$
考虑维护$\sum{C_{i}*i}$和$\sum C_{i}$
设每次成功概率为x
$\sum{C_{i}*i} \rightarrow \sum{C_{i}*(i+1)}*x \rightarrow \sum C_{i}*x+\sum C_{i}*i*x$
$\sum C_{i} \rightarrow \sum C_{i}$
$\sum C_{i} = 1$
$\sum C_{i}*i$就是期望…


bzoj4318: OSU!

上一道题的升级版,主要是分数变成$x^3$了。
$Ans = \sum C_{i-1} (i^3-(i-1)^3)=\sum C_{i-1} (3i^2-3i+1)=\sum C_{i-1} (3(i-1)^2+3(i-1)+1)$
所以要多维护一个$\sum{C_{i}i^2}$,即平方的期望
$\sum{C_{i}i^2} \rightarrow \sum C_{i}*(i+1)^2*x \rightarrow \sum C_{i}*(i^2+2i+1)*x$


bzoj1415:聪聪可可

做法1:很显然先处理出s[i][j]表示可可处于j点,聪聪处于i点,聪聪下一步会移动到哪里。
表示可可在b,聪聪在a,可可被吃的期望步数$f[a][b]=\sum \frac {f[s[a][b’]][b’]} {|V_{b}|}+1$,然后很显然这个东西是拓扑的(因为猫和老鼠的距离在不断地缩小。我们记搜即可
做法2:还是可以考虑sengxian的那种方法。 因为是DAG,所以是期望和概率相等,每条边被经过的期望次数之和便为每个点被经过的期望次数-1,所以我们要求每个点被经过的概率。f[i][j]表示,第j个点,然后xjb乱搞呗


bzoj2554:color

终于碰到一道比较神的题了,我没有任何想法,然后看了lrd的题解,恍然大悟.
http://www.cnblogs.com/liu-runda/p/6803126.html

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
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 9;
int num[26], n;
char s[N];
double t, P[N], g[N], f[N], ans, a[N], b[N]; // f[i] = a[i] * f[i + 1] + b[i];
int main () {
scanf("%s", s);
n = strlen(s);
for (int i = 0; i < n; ++i) ++num[s[i] - 'A'];
for (int i = 1; i < n; ++i) P[i] = 2.0 * i * (n - i) / n / (n - 1), g[i] = 1.0 / P[i];
a[1] = 1; b[1] = g[1];
for (int i = 2; i < n; ++i) {
b[i] = g[i] + 1.0 * (i - 1) / i / 2 * b[i - 1];
a[i] = 1.0 * (i + 1) / i / 2;
t = 1.0 - 1.0 * (i - 1) / i / 2 * a[i - 1];
a[i] /= t;
b[i] /= t;
}
f[n] = 0;
for (int i = n - 1; i; --i) f[i] = a[i] * f[i + 1] + b[i];
for (int i = 0; i < 26; ++i) ans += 1.0 * num[i] / n * f[num[i]];
printf("%.1f\n", ans);
return 0;
}

1417: Pku3156 Interconnect

直接往暴力的方向想,就是hash保存状态,然后转移
设m为总边数,$m=\frac{n(n-1)}{2},x$为连端没有联通的边数$\sum_{i}\sum_{j}sz[i]*sz[j]。$

  • 根据上面那道题,我想到的递推式为$f[s]=\frac{m}{x}+\sum_{i}\sum_{j}f[merge(s,i,j)]\frac{sz[i]*sz[j]}{x}$
  • 常规的递推式为$f[s]=\frac{1}{m}((m-x)f[S]+\sum_{i}\sum_{j}f[merge(s,i,j)])+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
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 35, M = 1005, P = 1e9 + 7;
map<int, double>dp;
int n, m, num[N], pm[35][N], p[35], f[N];
int find (int x) { while (x != f[x]) x = f[x] = f[f[x]]; return x; }
int get (int *f, int n) { int ret = 0; for (int i = 1; i <= n; ++i) ret = (233ll * ret + f[i]) % P; return ret; }
double Dfs (int d) {
int x = 0, *num = pm[d], n = p[d], S = get(num, n);
if (n == 1) return 0;
if (dp.count(S)) return dp[S];
double ret = m;
for (int i = 1; i < n; ++i) for (int j = i + 1; j <= n; ++j) {
p[d + 1] = n - 1;
for (int k = 1; k < j; ++k) pm[d + 1][k] = pm[d][k];
pm[d + 1][i] += pm[d][j];
for (int k = j + 1; k <= n; ++k) pm[d + 1][k - 1] = pm[d][k];
sort(pm[d + 1] + 1, pm[d + 1] + p[d + 1] + 1); //可以优化
ret += Dfs(d + 1) * num[i] * num[j];
x += num[i] * num[j];
}
return dp[S] = ret / x;
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) f[i] = i;
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
if (find(u) != find(v)) f[find(u)] = find(v);
}
m = n * (n - 1) / 2;
for (int i = 1; i <= n; ++i) ++num[find(i)];
for (int i = 1; i <= n; ++i) if (i == find(i)) pm[0][++p[0]] = num[i];
sort(pm[0] + 1, pm[0] + p[0] + 1);
printf("%.6f\n", Dfs(0));
return 0;
}

bzoj3093: [Fdu校赛2012] A Famous Game

现在有一个袋子,里面装有一些红球和蓝球共n个。红球的个数有0~n共n+1种可能,我们认为在最开始的时候这n+1种情况是等概率的。现在某人从袋子里随机拿出P个球,发现里面有Q个红球。问如果现在再从袋子里拿出一个球,是红球的概率是多少?
0<=Q<=P<n<=10^5

$P(B_{i}|A)=\frac{P(AB_{i})}{P(A)}$据说这叫贝叶斯公式
假设当前有i个红球
$P(A)=\frac{1}{n+1}\sum_{i=0}^{n}\frac{C_{i}^{q}C_{n-i}^{p-q}}{C_{n}^{p}}$
$P(AB_{i})=\frac{1}{n+1}\sum_{i=0}^{n}\frac{C_{i}^{q+1}C_{n-i}^{p-q}}{C_{n}^{p+1}}$这个式子不对,因为有可能前P个里面出现Q+1个球
$P(AB_{i})=P(B_{i}|A)*\frac{i-q}{n-p}$
$P(B_{i}|A)=\frac{\sum_{i=0}^{n}C_{i}^{q}C_{n-i}^{p-q}(i-q)}{\sum_{i=0}^{n}C_{i}^{q}C_{n-i}^{p-q}(n-p)}=\frac{\sum_{i=0}^{n}C_{i}^{q+1}C_{n-i}^{p-q}(q+1)}{\sum_{i=0}^{n}C_{i}^{q}C_{n-i}^{p-q}(n-p)}$
然后有这么个公式
$\sum_{i=0}^{n}C_{i}^{a}C_{n-i}^{b}=C_{n+1}^{a+b+1}$
这个公式可以这么理解:从n+1个数中选a+b+1个数,i相当于枚举第a+1个数。
$P(B_{i}|A)=\frac{C_{n+1}^{p+2}(q+1)}{C_{n+1}^{p+1}(n-p)}=\frac{q+1}{p+2}$


bzoj1989

树上随机选出两条路径,求它们的公共部分的长度的期望。
这种题一般是考虑每条边的贡献吧.然后还是挺好算的(
直接dp出每条边两边的集合的大小,然后就知道覆盖这条边的路径数了,就完了


bzoj2698

考虑每个点被染白的概率就行了


bzoj1426

http://hzwer.com/2860.html
我竟然没想出正解,一开始想的是迭代…


bzoj2318

这道题没想出,看了下提示,发现是迭代n=min(n,1000)就行.
f[i]/g[i] 表示还剩i个石子,Alice 先手/后手赢的概率
我们发现max/min是可以去掉的,因为如果$f[i-1]>g[i-1]$那么Alice和Bob肯定是力争先手,
也就是说$$f[i]=p*g[i]+(1-p)*g[i-1] \ g[i]=q*f[i]+(1-q)*f[i-1]$$
否则的话$p=1-p,q=1-q就ok了$,手动高斯消元一下得$$f_i=\frac{p*g_{i-1}+(1-p)*q*f_{i-1}}{1-(1-p)(1-q)} \ g_i=\frac{q*f_{i-1}+(1-q)*p*g_{i-1}}{1-(1-p)(1-q)}$$
这道题就完了.