壊すとword│E-olv

menu icon

BZOJ1444 [JSOI2009]有趣的游戏

2015.02.04 11:28 Wed| 2 visits oi_2015| 2015_刷题日常| Text

Solution

联想到神奇的 Penney’s game：

一个公平的硬币，被两个无聊的小孩连续抛掷，直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者，第一个小孩胜利，后者第二个小孩胜利。问谁的胜率更大。答案是前者胜率是后者的三倍！

参见 matrix67 大大的博客

这道题是一道神奇的在 AC 自动机上的概率 DP。假设到达第 i 个非根结点的概率为 $P_i$，则 $P_i$ 的值为所有能转移到节点 i 的节点选到的概率 * 选到 i 表示的字母的概率。特别地，一个节点不能由某个人的胜利状态转移到（因为转移到上面的时候游戏已经结束）。上面列出的方程组与所有人胜利概率之和为 1 这一条件连立，高斯消元解出这一方程组即可。

注意构造矩阵的时候绝对不能偷懒 T^T 在这里 WA 好久…… 为什么这里写的错到离谱，运行时间还和 AC 时间一样 T^T

还有高斯消元得到的答案可能会出现 -0.0，输出的时候要特判。C++ 里面的 -0 机制真是神奇~

Code

#include <bits/stdc++.h>
using namespace std;

#define N 12
#define S 105
#define strn *str - 'A'

int n, l, m, s, d[N];
char str[N]; long double p[N], mat[S][S];

struct trie_node
{
    int id; trie_node *son[10], *fail, *last; bool flag;
    trie_node() {}
    trie_node(int _id) : id(_id), son(), fail(), last(), flag() {}
    void *operator new(size_t);
}nodes[S];
void *trie_node::operator new(size_t)
{
    return nodes[s] = trie_node(s), &nodes[s++];
}

struct Aho_Corasick_automaton
{
    typedef trie_node node;
    node *root;
    Aho_Corasick_automaton() { root = new node(); }

    void insert(char *str)
    {
        node *p = root;
        while (*str)
        {
            if (p->son[strn] == NULL)
                p->son[strn] = new node();
            p = p->son[strn]; ++str;
        }
        p->flag = true;
    }

    void build_AC_Automaton()
    {
        queue<node*> q;
        root->fail = root;
        for (int i = 0; i < m; ++i)
            if (root->son[i] == NULL) root->son[i] = root;
            else q.push(root->son[i]), root->son[i]->fail = root;
        while (!q.empty())
        {
            node *t = q.front(); q.pop();
            for (int i = 0; i < m; ++i)
            {
                if (t->son[i] == NULL)
                    t->son[i] = t->fail->son[i];
                else
                    q.push(t->son[i]), t->son[i]->fail = t->fail->son[i];
            }
        }
    }

    void build_matrix(long double mat[S][S])
    {
        for (int i = 0; i < s; ++i)
        {
            if (i) mat[i][i] = -1;
            if (!nodes[i].flag)
                for (int j = 0; j < m; ++j)
                    mat[nodes[i].son[j]->id][i] += p[j];
        }
        for (int i = 0; i < s; ++i)
            mat[0][i] = nodes[i].flag;
        mat[0][s] = 1;
    }
};

Aho_Corasick_automaton ac;

void gauss(int n, long double mat[S][S])
{
    for (int i = 0; i < n; ++i)
    {
        int t = i;
        for (int j = i + 1; j < n; ++j)
            if (fabs(mat[j][i]) > fabs(mat[t][i]))
                t = j;
        if (t != i)
            for (int j = 0; j <= n; ++j)
                swap(mat[i][j], mat[t][j]);
        for (int j = i + 1; j < n; ++j)
        {
            double t = mat[j][i] / mat[i][i];
            for (int k = 0; k <= n; ++k)
                mat[j][k] -= mat[i][k] * t;
        }
    }
    for (int i = n - 1; i >= 0; --i)
    {
        mat[i][n] /= mat[i][i]; mat[i][i] = 1;
        for (int j = i - 1; j >= 0; --j)
            mat[j][n] -= mat[j][i] * mat[i][n], mat[j][i] = 0;
    }
}

int main()
{
    cin >> n >> l >> m;
    for (int x, y, i = 0; i < m; ++i)
    {
        cin >> x >> y, p[i] = y ? 1.0 * x / y : 0;
        if (y == 0) while (1) {}
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        ac.insert(str); d[i] = s - 1;
    }
    ac.build_AC_Automaton();
    ac.build_matrix(mat);
    gauss(s, mat);
    cout << fixed << setprecision(2);
    for (int i = 1; i <= n; ++i)
    {
        if(mat[d[i]][s] > 0)
            cout << mat[d[i]][s] << endl;
        else cout << 0.00 << endl;
    }
}
Newer