注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2553][BeiJing2011]禁忌  

2014-09-11 21:45:36|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2553: [BeiJing2011]禁忌

AC自动机+矩阵乘法

在这里仰慕随便虐自动机题的GTY神犇Orz

感谢指导

按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int LEN = 1e5+100;
const int HN = 1e5+100;
const int N = 15*5+5;
int al,n,length;
struct Node{
Node(){end=fail=0;memset(ch,0,sizeof(ch));}
bool end;int id;
Node *ch[26],*fail;
}house[N];int hn;
Node *newNode(){if(hn < N)return &house[hn++]; return new Node();}
queue <Node*>dui;
//typedef long double Matrix[20][20];
struct Matrix{
long double a[N][N];
int n,m;
Matrix(int nn,int mm):n(nn),m(mm){memset(a,0,sizeof(a));}
void set1(){*this = Matrix(n,m);for(int i=1;i<=n;i++)a[i][i]=1;}
};
inline Matrix operator * (Matrix &A,Matrix &B){//A.m == B.n
if(A.m!=B.n)cerr << "ERROR" << endl;
Matrix C(A.n,B.m);
for(int i=1;i<=C.n;i++)
for(int j=1;j<=C.m;j++)
for(int k=1;k<=A.m;k++)
C.a[i][j] += A.a[i][k]*B.a[k][j];
return C;
}
Matrix pow(Matrix a,int k){
Matrix re(a.n,a.n);re.set1();
for(;k;k/=2,a=a*a)
if(k&1) re=re*a;
return re;
}
struct AC{
Node *ROOT;int size;
AC(){ROOT = newNode();ROOT->id=size=1;ROOT->fail = ROOT;}
void insert(const char str[]){
Node *r = ROOT;
int len = strlen(str);
for(int i=0;i<len;i++){
if(!r->ch[str[i]-'a'])(r->ch[str[i]-'a'] = newNode())->id = ++size;
r=r->ch[str[i]-'a'];
}r->end=1;
}
void makefail(){
for(int i=0;i<al;i++)
if(ROOT->ch[i])dui.push(ROOT->ch[i]),ROOT->ch[i]->fail = ROOT;
else ROOT->ch[i] = ROOT;
while(!dui.empty()){
Node *r = dui.front();dui.pop();
for(int i=0;i<al;i++)
if(r->ch[i]){
Node *l = r->fail;
for(;l!=ROOT&&l->ch[i]==ROOT;)l=l->fail;
r->ch[i]->fail = l->ch[i];
if (r->fail->end) r->end = 1;
dui.push(r->ch[i]);
}else r->ch[i] = r->fail->ch[i];
}
}
}ac;
short v[N];
void scans(char a[]){
char cc=' ';int len=0;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
while(!(cc==' '||cc=='\r'||cc=='\n')){
a[len ++] = cc;
cc=getchar();
}a[len] = 0;
}
int main(){
int i,j,ansid;char str[LEN];
scanf("%d%d%d",&n,&length,&al);
for(int i=1;i<=n;i++){
scans(str);
ac.insert(str);
}
ac.makefail();ansid = ac.size+1;
//Make Marix
Matrix zh(ac.size+1,ac.size+1),ans(ac.size+1,1);
ans.a[1][1]=1;
dui.push(ac.ROOT);
v[ac.ROOT->id] = 1;
long double once = 1.0/al;
while(!dui.empty()){
Node *r = dui.front();dui.pop();
if(r->end)continue;
for(i=0;i<al;i++){
if(!v[r->ch[i]->id])v[r->ch[i]->id]=1,dui.push(r->ch[i]);
if(r->ch[i]->end){
zh.a[ac.ROOT->id][r->id] += once;
zh.a[ansid][r->id] += once;
}
else
zh.a[r->ch[i]->id][r->id] += once;
}
}
zh.a[ansid][ansid] = 1;
zh = pow(zh,length);
ans = zh*ans;
printf("%.7lf\n",(double)ans.a[ansid][1]);
return 0;
}

题解:

AC自动机上DP记录每个的概率,如果到达一个末尾节点就把概率*1加到ans里(期望值),并且返回自动机的根节点

这么转移的时计算的禁忌伤害一定是最优的(自己想想为什么)

因为位数特别大(1e5)并且每次转移都是固定的所以需要矩阵乘法加速

细节:

1.if (r->fail->end) r->end = 1; 注意makefail里的这句,没加是错误的,但是也能A= =||

2.据说(?)卡精度要用long double

  评论这张
 
阅读(57)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017