注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2327(hnoi2011) XOR和路径  

2013-02-21 21:54:31|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

总算来写题解了……

hnoi都做到2006了,我的题解进度才2011

现在2006被那个鬼潘多拉的盒子给卡题意了!!看不懂题目怎么破啊!!

其实我个人觉得我的hnoi刷题的过程中还是糟蹋了好多题的。各种看题解,还有几道纠结的要死。

写题解也是在巩固吧。

所以希望我题解中的问题都能被指出。

其实这段时间看了这么多题解,怎么说呢……网上那些大神写题解对我的帮助真的很大啊,如果没有的话我肯定做不下去。

前人的事业需要后人来继承…………

 

关于这道题必须得有一定的做概率期望题的基础。

在概率期望题的递推中,有个极其坑爹的地方就是尼玛要倒着设状态啊!!

 

这题我们要按位来做,就是对每一位做一次,弄30次高斯消元。因为求期望值的公式经过一些乘法分配律之后就会变成sigma{p(期望值的第i位为1)*2^i}了

在此抄一下skyfisherman大神的题解

 t[i]表示的是i的出度

对于(i,j)在当前枚举位为1的,x[j]对x[i]的贡献为(1-x[j])/t[i]

对于(i,j)在当前枚举位为0的,x[j]对x[i]的贡献为x[j]/t[i]

为什么是t[i]而不是t[j]呢?因为我们状态是倒着设的

这样就有n个方程了,但事实上必然有一个方程是没用的(会被其他的给消掉)

因为没有初值啊。

初值是x[n]=0,拿这个再列个方程就可以高斯消元了

我概率期望的经验还很不足,讲的好纠结的……其实自己也好纠结的

关键是这个倒着设真纠结……

就这样吧

 

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 110
#define MAXM 20010
#define eps 1e-13
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)  return 0;
    return p>eps?1:-1;
}
double E,a[MAXN][MAXN],b[MAXN],x[MAXN];
int degree[MAXN],n;
int tot,to[MAXM],next[MAXM],value[MAXM],start[MAXN];
void make(int a,int b,int c){  tot++,to[tot]=b,value[tot]=c,next[tot]=start[a],start[a]=tot,degree[a]++;  }
int get(int n,int k){  return n>>k&1;  }
void read()
{
    int m;
    scanf("%d %d",&n,&m);
    for(int i=1,a,b,c;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        make(a,b,c);
        if(a!=b)  make(b,a,c);
    }
}
void Make_Matrix(int k)
{
    for(int i=1;i<=n;i++)
    {
        b[i]=0;
        for(int j=1;j<=n;j++)
            a[i][j]=0;
    }
    for(int i=1;i<n;i++)
    {
        a[i][i]=1;
        for(int j=start[i];j;j=next[j])
        {
            if(get(value[j],k))  a[i][to[j]]=a[i][to[j]]+1.0/degree[i],b[i]=b[i]+1.0/degree[i];
            else  a[i][to[j]]=a[i][to[j]]-1.0/degree[i];
        }
    }
    a[n][n]=1;
}
void Gauss()
{
    for(int i=1,j;i<=n;i++)
    {
        for(j=i;!dcmp(a[j][i]);j++);
        for(int k=i;k<=n;k++)
            swap(a[i][k],a[j][k]);
        swap(b[i],b[j]);
        for(int j=i+1;j<=n;j++)
            if(dcmp(a[j][i]))
            {
                double p=a[i][i]/a[j][i];
                for(int k=i;k<=n;k++)
                    a[j][k]=a[i][k]-a[j][k]*p;
                b[j]=b[i]-b[j]*p;
            }
    }
    for(int i=n;i>=1;i--)
    {
        x[i]=b[i];
        for(int j=i+1;j<=n;j++)
            x[i]=x[i]-x[j]*a[i][j];
        x[i]/=a[i][i];
    }
}
double work(int k)
{
    Make_Matrix(k);
    Gauss();
    return x[1];
}
int main()
{
    read();
    for(int i=0;i<30;i++)
        E=E+(work(i)*(1<<i));
    printf("%.3lf\n",E);
    return 0;
}


  评论这张
 
阅读(729)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017