COCI20122013 Contest#5 F

不知道题解在写什么.jpg

Part1 : Naive的dp

令$dp_{i,a,b,j}$表示当前时刻$i$，两队比分为$a,b$，球在$j$手上的概率

转移非常简单就不说了，单次转移为$O(n)$，复杂度为$O(n^2r^2T)$

在优秀卡常+O2下跑进700ms

优化的话:
1.float

2.分小块加速

3.循环展开

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
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef float db;
#define reg register
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int INF=1e9+10;
const db eps=1e-12;

int n,R,T;
db dp[510][11][11][210],p[410],sz[410],ans[11][11];
struct Edge{
	int to,nxt;
} e[80000];
int head[410],ecnt;
void AddEdge(int u,int v) {
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}
int E[410][410],G[410][410]; 
const int D=5;
db tmp[210][1<<D];

int main(){
	n=rd(),R=rd(),T=rd();
	int m=(n*2+D-1)/D;
	rep(i,1,n*2) {
		scanf("%f",&p[i]);
		int e=rd(),f=rd();
		sz[i]=e+f+1;
		rep(j,1,e) {
			int x=rd();
			if(i>n) x+=n;
			E[i][x]=1;
		}
		rep(j,1,f) {
			int x=rd();
			if(i<=n) x+=n;
			E[i][x]=1;
		}
		rep(j,1,m) {
			int f=(j-1)*D+1;
			rep(k,0,D-1) G[i][j]|=E[i][f+k]<<k;
			if(G[i][j]) AddEdge(i,j);
		}
	}
	dp[0][0][0][1]=1;
	for(reg int i=0;i<=T;++i) {
		for(reg int a=0;a<=R;++a) {
			for(reg int b=0;b<=R;++b) {
				for(reg int j=1;j<=n*2;++j) if(dp[i][a][b][j]>eps) {
					if(a==R || b==R || i==T) { ans[a][b]+=dp[i][a][b][j]; continue; }
					db t=dp[i][a][b][j]/sz[j];
					for(reg int k=1;k<=m;k+=4) {
						tmp[k][G[j][k]]+=t;
						tmp[k+1][G[j][k+1]]+=t;
						tmp[k+2][G[j][k+2]]+=t;
						tmp[k+3][G[j][k+3]]+=t;
					}
					if(j<=n) {
						dp[i+1][a][b][n+1]+=t*(1-p[j]);
						dp[i+1][a+1][b][n+1]+=t*p[j];
					} else {
						dp[i+1][a][b][1]+=t*(1-p[j]);
						dp[i+1][a][b+1][1]+=t*p[j];
					}
				}
				for(reg int j=1;j<=m;++j) {
					int f=(j-1)*D+1;
					rep(k,1,(1<<D)-1) {
						(k&1) &&  (dp[i+1][a][b][f]+=tmp[j][k]);
						(k&2) &&  (dp[i+1][a][b][f+1]+=tmp[j][k]);
						(k&4) &&  (dp[i+1][a][b][f+2]+=tmp[j][k]);
						(k&8) &&  (dp[i+1][a][b][f+3]+=tmp[j][k]);
						(k&16) &&  (dp[i+1][a][b][f+4]+=tmp[j][k]);
						tmp[j][k]=0;
					}
				}
			}
		}
	}
	rep(i,0,R) rep(j,0,R) if(i!=R || j!=R) printf("%.10f\n",ans[i][j]);
}

Part2: 状态割裂

定义每个球进的时间为关键点，我们发现关键点的状态非常单一，只有两种

一个合法的转移序列可以被分为若干关键点的段以及最后一段到达$T$之后停止转移

考虑预处理两个关键点之间的转移概率

令$g_{a,b,i}$为当球在$a$队一号队员时，$i$次后$b$队进球的概率

可以枚举$a$，类似上面的$dp$，去掉比分的一维即可

预处理复杂度为$O(Tn^2)$

然后$dp$时直接枚举两个关键点转移，令

$h_{i,a,b,j}$时刻$i$比分为$a,b$，球在$j$队一号队员手上的概率

转移分两种

1.枚举下一个在$T$以内的关键点转移

复杂度为$O(T)$

2.考虑在$T$以内的时间不再出现进球了

需要预处理出当球在$i$队手上时，$j$次内出现进球的概率$s_{i,j}$，这个直接由$g$数组累前缀和即可

$dp$关键点的复杂度为$O(T^2r^2)$

大概比上面代码快4-5倍

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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef float db;
#define reg register
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int INF=1e9+10;
const db eps=1e-12;

int n,R,T;
struct Edge{
    int to,nxt;
} e[80000];
int head[410],ecnt;
void AddEdge(int u,int v) {
    e[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
}
db p[410],sz[410],ans[11][11],f[510][210],g[2][2][510],s[2][510];
// g[i][j][k] 在i拿球的情况下，j在第k次进球了
db h[510][11][11][2];

int main(){
    n=rd(),R=rd(),T=rd();
    rep(i,1,n*2) {
        scanf("%f",&p[i]);
        int e=rd(),f=rd();
        sz[i]=e+f+1;
        rep(j,1,e) {
            int x=rd();
            if(i>n) x+=n;
            AddEdge(i,x);
        }
        rep(j,1,f) {
            int x=rd();
            if(i<=n) x+=n;
            AddEdge(i,x);
        }
    }
    rep(d,0,1) {
        f[0][d*n+1]=1;
        rep(i,0,T) {
            rep(j,1,n*2) if(f[i][j]>eps) {
                db t=f[i][j]/sz[j];
                for(reg int k=head[j];k;k=e[k].nxt) f[i+1][e[k].to]+=t;
                f[i+1][j>n?1:n+1]+=t*(1-p[j]);
                g[d][j>n][i+1]+=t*p[j];
                f[i][j]=0;
            }
        }
        rep(i,0,T) {
            s[d][i]=g[d][0][i]+g[d][1][i];
            if(i) s[d][i]+=s[d][i-1];
        }
    }
    h[0][0][0][0]=1;
    rep(i,0,T) {
        rep(a,0,R) rep(b,0,R) rep(j,0,1) if(h[i][a][b][j]>eps) {
            if(a==R || b==R || i==T){ ans[a][b]+=h[i][a][b][j]; continue; }
            rep(k,1,T-i) {
                // 能在结束前产生一次进球
                h[i+k][a+1][b][1]+=h[i][a][b][j]*g[j][0][k];
                h[i+k][a][b+1][0]+=h[i][a][b][j]*g[j][1][k];
            }
            ans[a][b]+=h[i][a][b][j]*(1-s[j][T-i]);
        }
    }
    rep(i,0,R) rep(j,0,R) if(i<R || j<R) printf("%.10f\n",ans[i][j]);
}