1444: [Jsoi2009]有趣的游戏

时间：2021-05-23 20:43:52

1444: [Jsoi2009]有趣的游戏

链接

分析：

　　如果一个点回到0号点，那么会使0号点的概率增加，而0号点的概率本来是1，不能增加，所以这题用期望做。

　　设$x_i$表示经过i的期望次数，然后初始可以知道$x_0=0$，又因为末尾节点只会经过一次，所以末尾节点的概率就是期望。

　　然后建出AC自动机，高斯消元。

　　参考sengxian

代码：

Gauss

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

const double eps = 1e-;

int ch[N][], val[N], fail[N], id[N], q[N], Index;

int n, L, m;

char s[N];

double A[N][N], p[N];

void Insert(int x) {

    int now = ;

    for (int i = ; i < L; ++i) {

        int c = s[i] - 'A';

        if (!ch[now][c]) ch[now][c] = ++Index;

        now = ch[now][c];

    }

    val[now] = , id[x] = now;

}

void bfs() {

    int L = , R = ;

    for (int c = ; c < m; ++c) if (ch[][c]) q[++R] = ch[][c];

    while (L <= R) {

        int u = q[L ++];

        for (int c = ; c < m; ++c) {

            int v = ch[u][c];

            if (!v) ch[u][c] = ch[fail[u]][c];

            else {

                fail[v] = ch[fail[u]][c];

                val[v] |= val[fail[v]];

                q[++R] = v;

            }

        }

    }

}

bool Gauss(int n) {

    for (int k = ; k <= n; ++k) {

        int r = k;

        for (int i = k + ; i <= n; ++i) if (A[i][k] > A[r][k]) r = k;

        if (r != k) for (int j = ; j <= n + ; ++j) swap(A[r][j], A[k][j]);

        for (int i = k + ; i <= n; ++i) {

            if (fabs(A[i][k]) > eps) {

                double t = A[i][k] / A[k][k];

                for (int j = ; j <= n + ; ++j) A[i][j] -= A[k][j] * t;

            }

        }

    }

    for (int i = n; i >= ; --i) {

        for (int j = i + ; j <= n; ++j) A[i][n + ] -= A[j][n + ] * A[i][j];

        A[i][n + ] /= A[i][i];

    }

    return ;

}

int main() {

    n = read(), L = read(), m = read();

    for (int i = ; i < m; ++i) {

        int u = read(), v = read();

        p[i] = 1.0 * u / v;

    }

    int cnt = ;

    for (int i = ; i < n; ++i) {

        scanf("%s", s);

        for (int j = ; j < L; ++j)

            if (p[s[j] - 'A'] <= eps) { cnt ++; break; }

        Insert(i);

    }

    if (cnt == n) {

        for (int i = ; i <= n; ++i) puts("0.00"); return ;

    }

    bfs();

    A[][Index + ] = -;

    for (int i = ; i <= Index; ++i) {

        A[i][i] = -1.0;

        if (val[i]) continue;

        for (int c = ; c < m; ++c) A[ch[i][c]][i] += p[c];

    }

    Gauss(Index);

    for (int i = ; i < n; ++i) {

        double p = A[id[i]][Index + ];

        if (fabs(p) <= eps) puts("0.00");

        else printf("%.2lf\n", p);

    }

    return ;

}

迭代+矩阵

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

struct Node {

    double a[N][N];

    Node() { memset(a, , sizeof(a)); }

} A;

int ch[N][], val[N], fail[N], id[N], q[N], Index;

int n, L, m;

char s[N];

double p[N];

Node operator * (const Node &A,const Node &B) {

    Node C;

    for (int k = ; k <= Index; ++k)

        for (int i = ; i <= Index; ++i)

            for (int j = ; j <= Index; ++j)

                C.a[i][j] += A.a[i][k] * B.a[k][j];

    return C;

}

void Insert(int x) {

    int now = ;

    for (int i = ; i < L; ++i) {

        int c = s[i] - 'A';

        if (!ch[now][c]) ch[now][c] = ++Index;

        now = ch[now][c];

    }

    val[now] = , id[x] = now;

}

void bfs() {

    int L = , R = ;

    for (int c = ; c < m; ++c) if (ch[][c]) q[++R] = ch[][c];

    while (L <= R) {

        int u = q[L ++];

        for (int c = ; c < m; ++c) {

            int v = ch[u][c];

            if (!v) ch[u][c] = ch[fail[u]][c];

            else {

                fail[v] = ch[fail[u]][c];

                val[v] |= val[fail[v]];

                q[++R] = v;

            }

        }

    }

}

int main() {

    n = read(), L = read(), m = read();

    for (int i = ; i < m; ++i) {

        int u = read(), v = read();

        p[i] = 1.0 * u / v;

    }

    for (int i = ; i < n; ++i) {

        scanf("%s", s);

        Insert(i);

    }

    bfs();

    for (int i = ; i <= Index; ++i) {

        if (val[i]) A.a[i][i] = ;

        else for (int c = ; c < m; ++c) A.a[i][ch[i][c]] += p[c];

    }

    for (int i = ; i <= ; ++i) A = A * A;

    for (int i = ; i < n; ++i) printf("%.2lf\n", A.a[][id[i]]);

    return ;

}

相关文章