【JLOI2012】时间流逝

Source and Judge

JLOI2012
luogu3251

Record

1h

Analysis

请先思考后再展开

这题感觉挺妙的,当然也可能很套路?
注意到题目有个很显眼的性质,就是只能获得更小的值
这就像个字典树什么的,总之就是一棵树
$f(x)=1+pp \cdot f(fa)+\frac{1-pp}{tot} \sum f(son)$
然后在树上,高斯消元可以做到线性,抓住唯一父亲这个特征,手动迭代
具体而言就是把每个f(x)表示为 $k \cdot f(fa)+b$ ,这个显然是可以实现的
记 $A=\frac{1-pp}{tot}$
$f(x)=\frac{pp}{1-A \cdot \sum kson} f(fa)+\frac{1+A \cdot \sum bson}{1-A \cdot \sum kson}$
每个状态用mi和sum表示,然后每个节点只存储k和b,答案为根节点的b(注意在根时pp=0)

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
47
48
49
50
51
52
53
54
55
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
#define pr pair<double,double>
#define FR first
#define SE second
#define MP make_pair
pr operator + (pr a,pr b) {return MP(a.FR+b.FR,a.SE+b.SE);}
double pp;int T;
int a[100];
pr dfs(int mi,int sum)
{
if(sum>T) return MP(0,0);
pr now=MP(0,0);
for(int i=1;i<=mi;i++) now=now+dfs(i,sum+a[i]);
if(sum==0) pp=0;
double A=(1.0-pp)/mi;
return MP(pp/(1-A*now.FR),(1+A*now.SE)/(1-A*now.FR));
}
void main()
{
while(1)
{
int n;if(scanf("%lf%d%d",&pp,&T,&n)==EOF) break;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
pr ans=dfs(n,0);
printf("%.3lf\n",ans.SE);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ada4.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%