首页 > 代码库 > hdu 5955 Guessing the Dice Roll 【AC自动机+高斯消元】
hdu 5955 Guessing the Dice Roll 【AC自动机+高斯消元】
hdu 5955 Guessing the Dice Roll 【AC自动机+高斯消元】
题意：给出 n≤10 个长为 L≤10 的串，每次丢一个骰子，先出现的串赢，问获胜概率。
题解：裸的AC自动机，求匹配到终止结点的概率，用 高斯消元？一开始不知道怎么建方程组，直接举个例子吧：
Input:
1
2 2
1 1
2 1
图解：
x0原本概率就是1，然后还要加上其他结点走向它的概率，，这样最后算下来是大于1的，现在还是觉得怪怪的。。。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 #define CLR(a,b) memset((a),(b),sizeof((a))) 6 using namespace std; 7 const int N = 105; 8 const int M = 6; 9 int equ, var; 10 double a[N][N]; 11 double x[N]; 12 void Gauss() { 13 int i, j, k; 14 int max_r; 15 int col; 16 for(col = 0, k = 0; k < equ && col < var; ++k, ++col) { 17 max_r = k; 18 for(i = k+1; i < equ; ++i) 19 if(fabs(a[i][col]) > fabs(a[max_r][col])) 20 max_r = i; 21 if(max_r != k) { 22 for(j = k; j < var; ++j) 23 swap(a[k][j], a[max_r][j]); 24 swap(x[k], x[max_r]); 25 } 26 x[k] /= a[k][col]; 27 for(j = col+1; j < var; ++j) 28 a[k][j] /= a[k][col]; 29 a[k][col] = 1; 30 for(i = 0; i < equ; ++i) { 31 if(i != k) { 32 x[i] -= x[k] * a[i][col]; 33 for(j = col+1; j < var; ++j) 34 a[i][j] -= a[k][j] * a[i][col]; 35 a[i][col] = 0; 36 } 37 } 38 } 39 } 40 int mk[N]; 41 struct Trie { 42 int next[N][M], fail[N], tag[N]; 43 int root, L; 44 int newnode() { 45 for(int i = 0;i < M;i++) 46 next[L][i] = -1; 47 tag[L++] = 0; 48 return L-1; 49 } 50 void init() { L = 0; root = newnode(); } 51 void Insert(int buf[], int len, int id) { 52 int u = root; 53 for(int i = 0; i < len; i++) { 54 if(next[u][buf[i]] == -1) 55 next[u][buf[i]] = newnode(); 56 u = next[u][buf[i]]; 57 } 58 tag[u] = 1; 59 mk[id] = u; 60 } 61 void build() { 62 queue<int> Q; 63 fail[root] = root; 64 for(int i = 0; i < M; i++) { 65 if(next[root][i] == -1) 66 next[root][i] = root; 67 else { 68 fail[next[root][i]] = root; 69 Q.push(next[root][i]); 70 } 71 } 72 while( !Q.empty() ) { 73 int u = Q.front(); 74 Q.pop(); 75 for(int i = 0; i < M; i++) { 76 int &v = next[u][i]; 77 if(v == -1) 78 v = next[fail[u]][i]; 79 else { 80 Q.push(v); 81 fail[v] = next[fail[u]][i]; 82 } 83 } 84 } 85 } 86 void query(int n) { 87 int i , j; 88 CLR(a, 0); CLR(x, 0); 89 equ = var = L; 90 for(i = 0; i < L; ++i) a[i][i] = -1.0; 91 x[0] = -1.0; 92 for(i = 0; i < L; ++i) { 93 for(j = 0; j < M; ++j) { 94 if(next[i][j] != -1 && tag[i]==0) 95 a[next[i][j]][i] += 1.0/6; 96 } 97 } 98 Gauss(); 99 for(i = 0; i < n-1; ++i)100 printf("%.6f ", x[mk[i]]);101 printf("%.6f\n", x[mk[n-1]]);102 }103 };104 Trie ac;105 int main() {106 int T, n, m;107 int A[15];108 scanf("%d",&T);109 while( T-- ) {110 scanf("%d%d", &n, &m);111 ac.init();112 for(int i = 0; i < n; i++) {113 for(int j = 0; j < m; ++j) {114 scanf("%d", &A[j]);115 A[j]--; //0~5116 }117 ac.Insert(A, m, i);118 }119 ac.build();120 ac.query(n);121 }122 return 0;123 }
hdu 5955 Guessing the Dice Roll 【AC自动机+高斯消元】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。