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.循环展开
#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
",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倍
#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
",ans[i][j]);
}