1444: [Jsoi2009]有趣的游戏
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1800 Solved: 645
[Submit][Status][Discuss]
Description
Input
注意 是0<=P, n , l, m≤ 10.
Output
Sample Input
input 1
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
Sample Output
output 1
0.25
0.50
0.25
output 2
0.31
0.33
0.37
0.25
0.50
0.25
output 2
0.31
0.33
0.37
HINT
建个AC自动机之后，直接搞出转移的矩阵然后直接高斯消元即可。(既然是套路题我就不多说了2333)
#include<bits/stdc++.h>#define ll long longusing namespace std;#define D doubleconst int maxn=205;const D eps=1e-9;int ch[maxn][27],n,m,l,cnt,X,Y;int f[maxn],rot=0,dy[27];D a[maxn][maxn],p[27];char s[37];bool islef[maxn];inline int Id(char x){ return x-‘A‘+1;}inline void Ins(int x){int now=rot;for(int i=1,C;i<=l;i++){C=Id(s[i]);if(!ch[now][C]) ch[now][C]=++cnt;now=ch[now][C]; ???}dy[x]=now,islef[now]=1;}inline void getfail(){queue<int> q;for(int i=1;i<=m;i++) if(ch[rot][i]){ f[ch[rot][i]]=0,q.push(ch[rot][i]);}int x,v;while(!q.empty()){x=q.front(),q.pop();for(int i=1;i<=m;i++){v=ch[x][i];if(!v){ ch[x][i]=ch[f[x]][i]; continue;}q.push(v);f[v]=ch[f[x]][i];}}}inline void build(){a[0][cnt+1]=1;for(int i=0;i<=cnt;i++){a[i][i]=1;if(!islef[i]) for(int j=1;j<=m;j++) a[ch[i][j]][i]-=p[j];}/*for(int i=0;i<=cnt;i++){for(int j=0;j<=cnt+1;j++) printf("%.2lf ",a[i][j]);puts("");}*/}inline void xy(){for(int i=0;i<=cnt;i++){int tmp=i;for(int j=i+1;j<=cnt;j++) if(a[j][i]>a[tmp][i]) tmp=j;if(tmp>i) for(int k=cnt+1;k>=i;k--) swap(a[i][k],a[tmp][k]);for(int j=i+1;j<=cnt;j++) if(fabs(a[j][i])>eps){D o=a[j][i]/a[i][i];for(int k=cnt+1;k>=i;k--) a[j][k]-=a[i][k]*o;}}for(int i=cnt;i;i--){for(int j=i+1;j<=cnt;j++) a[i][cnt+1]-=a[i][j]*a[j][cnt+1];a[i][cnt+1]/=a[i][i];}}inline void solve(){getfail();build();xy();}int main(){scanf("%d%d%d",&n,&l,&m);for(int i=1;i<=m;i++) scanf("%d%d",&X,&Y),p[i]=X/(D)Y;for(int i=1;i<=n;i++){scanf("%s",s+1);Ins(i);}solve();for(int i=1;i<=n;i++) printf("%.2lf\n",a[dy[i]][cnt+1]);return 0;}
[JSOI2009] 有趣的游戏
原文地址：https://www.cnblogs.com/JYYHH/p/9063099.html