WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
HDU 5955:Guessing the Dice Roll
HDU 5955:Guessing the Dice Roll

题目大意

n个人,每个人一个长度为l,元素范围为[1, 6]的序列。
持续抛掷一个骰子,会得到一个随机序列,如果随机序列中出现了某个人的序列,那么那个人就胜利了。
现在问,每个人胜利的概率是多少

题解

首先用AC自动机将所有人的字符串扔进去,进行匹配,扔骰子的过程就是一个序列匹配的过程。
AC自动机上的每一个节点就是一个状态,有对应的概率,所有状态之间构成一个方程组。我们只需要对它消元即可。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

namespace ACMachine{
    const int MAXN=1e7+50;
    const int KIND=10;
    struct Tree{
        int siz;
        int ch[KIND], fail;
    };
    Tree tree[MAXN];
    int nume, root;

    inline int newNode(){
        int x=++nume;
        for (int i=0; i<KIND; i++) tree[x].ch[i]=0;
        tree[x].siz=tree[x].fail=0;
        return x;
    }

    inline void init(){
        nume=0;
        root=newNode();
    }

    int insert(int x, char str[]){
        int c, len=strlen(str);
        for (int i=0; i<len; i++){
            c=str[i]-'0';
            if (tree[x].ch[c]==0) tree[x].ch[c]=newNode();
            x=tree[x].ch[c];
        }
        tree[x].siz++;
        return x;
    }

    queue<int> que;
    void build(int x){
        while(!que.empty()) que.pop(); que.push(x);
        while(!que.empty()){
            x=que.front(); que.pop();
            for (int c=0; c<KIND; c++){
                int now=tree[x].ch[c];
                if (now){
                    if (x==root) tree[now].fail=root; else{
                        int p=tree[x].fail;
                        while(p){
                            if (tree[p].ch[c]){
                                tree[now].fail=tree[p].ch[c];
                                break;
                            }
                            p=tree[p].fail;
                        }
                        if (!p) tree[now].fail=root;
                    }
                    que.push(now);
                }
            }
        }
    }

    int query(int x, char str[]){
        int ret=0, len=strlen(str);
        for (int i=0; i<len; i++){
            int c=str[i]-'0';
            while(!tree[x].ch[c] && x!=root) x=tree[x].fail;
            x=tree[x].ch[c];
            if (x==0) x=root;

            int now=x;
            while(now!=root){
                if (tree[now].siz>=0){
                    ret+=tree[x].siz;
                    tree[x].siz=-1;
                }else break;
                now=tree[now].fail;
            }
        }
        return ret;
    }
}

namespace Gauss{
    const int MAXN=500+50;
    const double EPS=1e-8;
    int equ, var;
    double matrix[MAXN][MAXN];
    double value[MAXN];
    void init(){ memset(matrix, 0, sizeof(matrix)); }

    void print(){
        printf("-----------------------\n");
        for (int i=0; i<equ; i++){
            for (int j=0; j<=var; j++){
                printf("%.2f ", matrix[i][j]);
            }
            printf("\n");
        }
    }

    int gauss(){
        for (int k=0, col=0; k<equ && col<var; k++, col++){
            int max_r=k;
            for (int i=k+1; i<equ; i++) if (fabs(matrix[i][col])>fabs(matrix[max_r][col])) max_r=i;
            if (fabs(matrix[max_r][col])<EPS) return false;
            for (int j=col; j<=var; j++) swap(matrix[k][j], matrix[max_r][j]);
            for (int j=col+1; j<=var; j++) matrix[k][j]/=matrix[k][col];
            matrix[k][col]=1;
            for (int i=0; i<equ; i++){
                if (i==k) continue;
                for (int j=col+1; j<=var; j++) matrix[i][j]-=matrix[k][j]*matrix[i][col];
                matrix[i][col]=0;
            }
            //print();
        }
        for (int i=0; i<equ; i++) value[i]=matrix[i][var];
        return true;
    }
}

int n, l;
char str[15];
int idx[15];
inline void solve(int T){
    scanf("%d%d", &n, &l);
    ACMachine::init();
    for (int i=0; i<n; i++){
        for (int j=0, x; j<l; j++) scanf("%d", &x), str[j]=x+'0'; str[l]=0;
        idx[i]=ACMachine::insert(ACMachine::root, str);
    }
    ACMachine::build(ACMachine::root);

    Gauss::init();
    int siz=ACMachine::nume;
    Gauss::equ=Gauss::var=siz;
    for(int i=0; i<siz; i++) Gauss::matrix[i][i]=-1;
    Gauss::matrix[0][siz]=-1;
    for (int i=0; i<siz; i++){
        if (ACMachine::tree[i+1].siz>0) continue;
        for (int c=1; c<=6; c++){
            int x=i+1, v=ACMachine::tree[x].ch[c];
            if (v==0){
                while(!ACMachine::tree[x].ch[c] && x!=ACMachine::root) x=ACMachine::tree[x].fail;
                v=ACMachine::tree[x].ch[c];
                if (v==0) v=ACMachine::root;
            }
            Gauss::matrix[v-1][i]+=1.0/6.0;
        }
    }
    //Gauss::print();
    Gauss::gauss();

    for (int i=0; i<n; i++) {
        if (i>0) printf(" ");
        printf("%.6f", Gauss::value[idx[i]-1]);
    }
    printf("\n");
}

int main(){
    //freopen("in.txt", "r", stdin);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

HDU 5955:Guessing the Dice Roll
题目大意 有$n$个人,每个人一个长度为$l$,元素范围为$[1, 6]$的序列。 持续抛掷一个骰子,会得到一个随机序列,如果随机序列中出现了某个人的序列,那么那个人就胜利了。 现在问,每个…
扫描二维码继续阅读
2018-10-11
<--! http2https -->