锐客网

  1. 首页 > it技术 > >

online|hdu5955Guessing the Dice Roll

数学字符串HDUAC自动机onlinejudge期望

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5955
题意：有一个6面的骰子，有n个人每个人猜了一个长度为l的序列，不停的掷骰子直到满足一个人的序列则那个人获胜，求每个人获胜的概率。
分析：因为是一些序列之间状态概率的转变，很容易想到AC自动机的fail树的转换，我们从fail树上确定了各个状态的转变概率就可以得到一个方程组，然后高斯消元求出各个节点的概率就行了。细节：1，叶子节点不需要转变。2，根节点为概率1。3，非叶子节点到根的概率*根到第一层节点的概率要记得处理。
代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef double db; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; const db eps=1e-6; const int N=110; const int M=1e5+10; const ll MOD=1000000007; const int mod=1000000007; const int MAX=1000000010; const double pi=acos(-1.0); int d[N],ans[12]; struct trie { int sz,val[N],fail[N],tr[N][6]; void trie_clear() { sz=0; memset(tr,0,sizeof(tr)); memset(val,0,sizeof(val)); memset(fail,0,sizeof(fail)); } int trie_insert(int *ch) { int w=0; while (*ch!=-1&&tr[w][*ch]) w=tr[w][*ch],ch++; while (*ch!=-1) tr[w][*ch]=++sz,ch++,w=sz; val[w]=1; return w; } void trie_build() { queueQ; for (int i=0; i<6; i++) if (tr[0][i]) Q.push(tr[0][i]); while (!Q.empty()) { int now=Q.front(); Q.pop(); if (val[now]) continue ; for (int i=0; i<6; i++) if (tr[now][i]) { fail[tr[now][i]]=tr[fail[now]][i]; Q.push(tr[now][i]); } else tr[now][i]=tr[fail[now]][i]; } } }AC; db p[N][N]; int gauss(int n) { int i,j,k,mxi; db h; for (i=1; i<=n; i++) { mxi=i; for (j=i; j<=n; j++) if (fabs(p[j][i])>fabs(p[mxi][i])) mxi=j; if (fabs(p[mxi][i])



    推荐阅读


    上一篇：online|hdu1816Get Luffy Out *

    下一篇：三种鼠标经过图片变动效果（透明度、灰白、缩放）