BUPT2017 wintertraining(15) #5B

HDU - 4936

2014 Multi-University Training Contest 7 F

题意

直接看官方的题意和题解吧(来自:2014年多校的题解博客)。

题解

官方的不够细,我再梳理一下吧。

预处理:

首先dfs出所有可能的联通块状态,这个状态只考虑共几个联通块,每个联通块里几个岛,不考虑是哪些岛。然后对每个状态hash一下,编个号。根据我们dfs的顺序,1号状态是全部独立,cnt号状态是全部联通。

\(mg[i][x][y]\)为合并i状态的第x和第y个联通块得到的状态编号,可以求出来。

dp

我用\(dp[i][j]\)保存第i号状态,人在第j个岛上,到达目标的期望步数。

那么\(dp[1][1]\)就是答案,\(dp[cnt][i]\)都是0。

然后两种转移就是

1. 状态不变,i状态的j岛转移到v岛

步数就是\(dp[i][v]+1\)。

到达v岛的概率是\(\frac 1 {s_j}\)

如果产生了彩虹(p[j]),那么必须是连接同一联通块的岛。

a[i]是第i个联通块的岛的数量,\(C_{a[i]}^2\)种方案是不改变状态的,总方案是\(C_{n}^{2}\),于是彩虹连接同一联通块的概率就是\(\frac {\sum {a[i]*(a[i]-1)}}{n*(n-1)}\)。

否则不产生彩虹(1-p[j]),状态一定不变。

2. 状态改变,i状态的j岛转移到k状态的v岛

步数是\(dp[k][v]+1\)。

把步数乘上对应概率加起来就是期望值。

高斯消元

然后我们列出了这样的式子

\[dp[i][j]=\sum_{v\in s[j]}[(dp[i][v]+1)\cdot 概率]+\sum_{v\in s[j]}[(dp[k][v]+1)\cdot 概率]
\]

变形一下就是

\[dp[i][j]-\sum_{v\in s[j]} dp[i][v]\cdot\frac 1 {s_j} \cdot \left[p[j]\cdot \frac {\sum {a[i]\cdot (a[i]-1)}}{n\cdot(n-1)}+(1-p[j])\right]\\
=1+\sum_{\substack{v \in s[j]\\k=mg[i][x][y]}} dp[k][v]\cdot\frac 1 {s_j} \cdot \frac{a[x]\cdot a[y]}{(n\cdot (n-1)/2)}
\]

右边的dp是已经求得的,所以是个常数。左边的dp[i][j]作为未知数,j从1到n有n个这样的方程,n个未知数,可以高斯消元来求解。

ps. 这次的sb错,调了好一会儿:直接把整型数相乘然后去除以浮点数。另外这题好难啊,我想了很久,最后还是看官方题解加上看别人代码理解才写出来。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define N 22
#define M 1000007
using namespace std;
int cas,t,n,cnt,a[N];
int f[M+1],mg[700][N][N];
//f[code]:code对应的状态
//mg[s][x][y]:状态s的第x和第y个合并后的状态
double p[N],dp[700][N],g[N][N];
//dp[st][i],当前状态st,人在第i个岛上,到达目标状态的期望值
vector<int>s[N]; struct sta{
int a[N],tot;
}st[700]; int code(sta t){
int b=t.tot;
for(int i=1;i<=t.tot;i++)
b=(b*233%M+t.a[i])%M; //hash
return b;
}
void dfs(int d,int k,int sum){
if(sum==n){
sta &t=st[++cnt];
t.tot=d-1;
for(int i=1;i<d;i++)
t.a[i]=a[i];
f[code(t)]=cnt;
return;
}
for(int i=k;i<=n-sum;i++)
dfs(d+1,a[d]=i,sum+i);
}
int merge(sta t,int x,int y){
t.a[x]+=t.a[y];
swap(t.a[y],t.a[t.tot--]);
sort(t.a+1,t.a+t.tot+1);
return f[code(t)];
} void pre(){
//求出所有可能的状态并hash处理,求出合并两个联通块后对应的状态
cnt=0;
dfs(1,1,0);
for(int i=1;i<=cnt;i++)
for(int x=1;x<st[i].tot;x++)
for(int y=x+1;y<=st[i].tot;y++)
mg[i][x][y]=merge(st[i],x,y);
}
void gauss(double x[]){
for(int i=1;i<=n;i++){
int r=i;
while(!g[r][i]&&r<=n)r++;
if(r>n)return;
swap(g[r],g[i]);
for(int j=i+1;j<=n;j++){
double t=g[j][i]/g[r][i];
for(int k=1;k<=n+1;k++)
g[j][k]-=t*g[r][k];
}
}
for(int i=n;i;i--)if(g[i][i]){//注意判断
x[i]=g[i][n+1]/g[i][i];
for(int j=1;j<i;j++)
g[j][n+1]-=g[j][i]*x[i];
}
}
void work(){
memset(dp,0,sizeof dp);
for(int i=cnt-1;i>=1;i--){
memset(g,0,sizeof g);
for(int j=1;j<=n;j++){
double b=1;
for(int x=1;x<st[i].tot;x++)
for(int y=x+1;y<=st[i].tot;y++){
int k=mg[i][x][y];
double ps=p[j]*st[i].a[x]*st[i].a[y]/(n*(n-1)/2)/s[j].size();
for(int u=0;u<s[j].size();u++){
int v=s[j][u];
b+=dp[k][v]*ps;
}
}
g[j][j]=1;
g[j][n+1]=b;
double ps=0;
for(int x=1;x<=st[i].tot;x++)
ps+=st[i].a[x]*(st[i].a[x]-1);//连接同一联通块的岛的彩虹个数*2
ps/=n*(n-1);//除以 2*总的彩虹个数(n*(n-1)/2)
ps=(ps*p[j]+1-p[j])/s[j].size();
for(int u=0;u<s[j].size();u++){
int v=s[j][u];
g[j][v]-=ps;
}
}
gauss(dp[i]);
}
}
int main() {
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&p[i]),s[i].clear();
for(int i=1,t,v;i<=n;i++){
scanf("%d",&t);
while(t--){
scanf("%d",&v);
s[i].push_back(v);
}
}
pre();
work();
printf("Case #%d: %f\n",++cas,dp[1][1]);
}
return 0;
}

最新文章

  1. MongoDB 安装和可视化工具
  2. Win7---------专区
  3. freemarker:简介
  4. android 模拟器
  5. ASP.NET服务器端执行耗时操作的工作记录
  6. WindowsForm通过字符串名称实例化控件
  7. Android集成支付宝接口 实现在线支付
  8. php中使用linux命令四大步骤
  9. POJ 1847 Tram dij
  10. phpcms 标签解析
  11. 【手机安全卫士01】项目Splash页面的开发与设计
  12. DeDeCMS中如何实现下拉菜单
  13. H5 Canvas vs. SVG
  14. Java:函数
  15. c/c++(hiredis)异步调用redis【转】
  16. 史上最全office2016 激活码
  17. css——rgba()和opacity的区别
  18. build.xml编译报错Specified VM install not found: type Standard VM, name jdk1.7.0_45
  19. shiro--认证部分
  20. VSTO:使用C#开发Excel、Word【12】

热门文章

  1. Literal 字面值 字面量 的理解
  2. url 传递中文参数乱码问题的终极解决方法。
  3. c# 获取文件本身的哈希值
  4. 基于uFUN开发板的心率计(二)动态阈值算法获取心率值
  5. MySQL高可用方案MHA在线切换的步骤及原理
  6. bootstrapTable使用场景及方式
  7. 如何在css中设置按钮button中包含图片文字对齐方式
  8. 个人博客作业_week3
  9. Daily Scrum NO.10
  10. let命令和块级作用域