【Hdu6389】Go to school

Source

hdu的输入可能和代码不同
然后被卡精了并没有ac
Hdu6389

Hint

请先思考后再展开

$E(x)=\int_{1}^{mx} P(x \leq t) dt$
然后对于n个[0,R]的随机变量, $E(min x)=后面那个的积=\frac{R}{n+1}$

然后直接搞的话会有个min,比较麻烦
把所有船按照Li从小到大排序,然后分情况讨论一下

Solution

请先思考后再展开

考虑第一个在T之前的船i
第一部分, $L_i \leq T$
那么前面的就是钦定不出现, $\prod 1-\frac{min(T,L_i)}{m}$
然后后面的设有k个在T前出现
$P=1-\frac{L_i}{m},C_{n-i}^k P^k (1-P)^{n-i-k} \frac{L_i}{k+2}$

第二部分, $L_i>T$
类似,不细说

第三部分,所有人都在T后面
很简单

50pt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n=qread(),m=qread(),q=qread(),a=qread(),b=qread();
for(int i=1;i<=n;i++) L[i]=qread();sort(L+1,L+n+1);
while(q--)
{
int T=qread();
pre[0]=1;for(int i=1;i<=n;i++) pre[i]=pre[i-1]*(m-min(T,L[i]))/m;
double ans=(double)(T+b)*pre[n];
for(int i=1;i<=n;i++)
{
if(L[i]<=T)
{
double P=(double)L[i]/m;
for(int k=0;k<=n-i;k++) ans+=C[n-i][k]*pow(P,k+1)*pow(1-P,n-i-k)*L[i]/(k+2)*pre[i-1];
}
else
{
double P=(double)T/m;
for(int k=0;k<=n-i;k++) ans+=C[n-i][k]*pow(P,k+1)*pow(1-P,n-i-k)*T/(k+2)*pre[i-1];
}
}
printf("%.5Lf\n",ans+a*(1-pre[n]));
}

然后第一部分优化掉k,第二部分优化掉i即可
时间复杂度 $O(n^2+qn)$

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//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>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(ll &x,const ll y) {x=x>y?x:y;}
void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=1e3+10;
const ll MOD=998244353;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int L[MAX_N];
double C[MAX_N][MAX_N],pre[MAX_N],pre2[MAX_N],f[MAX_N];
void main()
{
C[0][0]=1;for(int i=1;i<MAX_N;i++){C[i][0]=1;for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];}
int n=qread(),q=qread(),m=qread(),a=qread(),b=qread();
for(int i=1;i<=n;i++) L[i]=qread();sort(L+1,L+n+1);
for(int i=1;i<=n;i++)
{
double P=(double)L[i]/m;
for(int k=0;k<=n-i;k++) f[i]+=C[n-i][k]*pow(P,k+1)*pow(1-P,n-i-k)*L[i]/(k+2);
}
while(q--)
{
int T=qread();
pre[0]=1;for(int i=1;i<=n;i++) pre[i]=pre[i-1]*(m-min(T,L[i]))/m;
pre2[0]=1;for(int i=1;i<=n;i++) pre2[i]=pre2[i-1]+pre[i];
double ans=(T+b)*pre[n]+a*(1-pre[n]);
int pos=0;while(pos+1<=n and L[pos+1]<=T) pos++;
for(int i=1;i<=pos;i++) ans+=f[i]*pre[i-1];
double P=(double)T/m;
for(int k=1;k<=n-pos;k++) ans+=C[n-pos][k]*pow(P,k)*pow(1-P,n-pos-k)*T/(k+1)*pre[pos];
printf("%.6Lf\n",ans);
}
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

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