BZOJ2553: [BeiJing2011]禁忌
时间： 19:34:10
&&&& 阅读：105
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&
2553: [BeiJing2011]禁忌
Time Limit: 20 Sec&&Memory Limit: 128 MBSec&&Special JudgeSubmit: 203&&Solved: 75[][]
Description
&&&&&& Magic Land上的人们总是提起那个传说：他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后，Koishi恢复了读心的能力&&
如今，在John已经成为传说的时代，再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。
&&&&&& 这次她遇到了Flandre Scarlet&&她拥有可以使用禁忌魔法而不会受到伤害的能力。
&&&&&& 为了说明什么是禁忌魔法及其伤害，引入以下概念：
1．字母集A上的每个非空字符串对应了一个魔法。
其中A是包含了前alphabet个小写字母的集合。
2．有一个集合T，包含了N个字母集A上的字符串
T中的每一串称为一个禁忌串（Taboo string）
3．一个魔法，或等价地，其对应的串s因为包含禁忌而对使用者造成的伤害按以下方式确定：
&& &&&&&&& 把s分割成若干段，考虑其中是禁忌串的段的数目，不同的分割可能会有不同的数目，其最大值就是这个伤害。
由于拥有了读心的能力，Koishi总是随机地使用Flandre Scarlet的魔法，可以确定的是，她的魔法正好对应字母集A上所有长度为len的串。
但是，Flandre Scarlet所使用的一些魔法是带有禁忌的，由于其自身特性，她可以使用禁忌魔法而不受到伤害，而Koishi就不同了。可怜的Koishi每一次使用对方的魔法都面临着受到禁忌伤害的威胁。
&&&&&& 你现在需要计算的是如果Koishi使用对方的每一个魔法的概率是均等的，那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。
第一行包含三个正整数N、len、alphabet。
接下来N行，每行包含一个串Ti，表示禁忌串。
一个非负实数，表示所受到禁忌伤害的期望值。
Sample Input
Sample Output
【样例1解释】
一共有2^4 = 16种不同的魔法。
需要注意的是&aabb&的禁忌伤害是1而不是2。
100%的数据中N & 5，len &109，1 & alphabet & 26。
在所有数据中，有不少于40%的数据中：N = 1。
数据保证每个串Ti的长度不超过15，并且不是空串。
数据保证每个Ti均仅含有前alphabet个小写字母。
数据保证集合T中没有相同的元素，即对任意不同的i和j，有Ti&Tj。
【评分方法】
对于每一组数据，如果没有得到正确的输出（TLE、MLE、RTE、输出格式错误等）得0分。
否则：设你的输出是YourAns，标准输出是StdAns：
记MaxEPS = max(1.0 , StdAns)&10-6
如果|YourAns & StdAns| & MaxEPS则得10分，否则得0分。
即：你的答案需要保证相对误差或绝对误差不超过10-6。
出题人果然丧心病狂卡精度。。。
这题写题解的人好像不多，也许是我太傻叉了，时光机的代码画面太美我都不敢看了。。。
&首先我们先搞清一个问题，如果给定了一个字符串，那么它的伤害指数是多少。
转化一下就变成 在一个数轴上给定若干条线段，请选出最多的线段并且使得这些线段两两交集为空。
然后这就是一个贪心水题，见/zyfzyf/p/4006703.html
我们只要按右端点排序，能取就取。
那假如我们已经构建了一个AC自动机，我们只要走到一个危险节点，就ans++，并且退回到根节点重新开始走。
可以看出，这样正好相当于在模拟上面的贪心过程。
然后我们看看len增加1，我们能干什么
建图如下：
void build()
q.push(1);long double tmp=1.0/k;
while(!q.empty())
int x=q.front();q.pop();
for0(i,k-1)
if(!vis[t[x][i]])vis[t[x][i]]=1,q.push(t[x][i]);
if(v[t[x][i]])
a.d[x][n]+=
a.d[x][1]+=
}else a.d[x][t[x][i]]+=
意思就是我们把所有这样的关系找出来，如果len结束时，我们在x。
那如果t[x][i]是根节点，那我们就有1.0/alp的期望使ans+1，并返回根节点，否则我们有1.0/alp的期望走到t[x][i]。
最后我们求长度为给定是从1走到ans（设置为节点n）的期望次数即可。
然后这个矩阵构建出来我们发现 i到j的期望就等于sigma(i到k的期望*k到j的期望)。
这正好是矩阵乘法！
然后我们就可用快速幂加速了。
注意设置a[n][n]=1
1 #include&cstdio&
3 #include&cstdlib&
5 #include&cmath&
7 #include&cstring&
9 #include&algorithm&
11 #include&iostream&
13 #include&vector&
15 #include&map&
17 #include&set&
19 #include&queue&
21 #include&string&
23 #define inf
25 #define maxn 200+5
27 #define eps 1e-10
29 #define ll long long
31 #define pa pair&int,int&
33 #define for0(i,n) for(int i=0;i&=(n);i++)
35 #define for1(i,n) for(int i=1;i&=(n);i++)
37 #define for2(i,x,y) for(int i=(x);i&=(y);i++)
39 #define for3(i,x,y) for(int i=(x);i&=(y);i--)
41 #define mod
43 using namespace
45 inline int read()
int x=0,f=1;char ch=getchar();
while(ch&‘0‘||ch&‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch&=‘0‘&&ch&=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}
return x*f;
58 int n,m,k,cnt,t[maxn][26],go[maxn];
59 bool v[maxn],vis[maxn];
60 queue&int&q;
61 char s[maxn];
62 struct matrix
long double d[maxn][maxn];
matrix(){memset(d,0,sizeof(d));}
66 }a,b,c;
67 inline void add()
scanf("%s",s+1);int len=strlen(s+1),now=1;
for1(i,len)
int x=s[i]-‘a‘;
if(!t[now][x])t[now][x]=++
now=t[now][x];
78 void bfs()
q.push(1);
while(!q.empty())
int x=q.front(),y,j;q.pop();
v[x]|=v[go[x]];
for0(i,k-1)
while(j&&!t[j][i])j=go[j];
if(t[x][i])
go[y=t[x][i]]=j?t[j][i]:1;
q.push(y);
}else t[x][i]=j?t[j][i]:1;
97 void build()
q.push(1);long double tmp=1.0/k;
while(!q.empty())
int x=q.front();q.pop();
for0(i,k-1)
if(!vis[t[x][i]])vis[t[x][i]]=1,q.push(t[x][i]);
if(v[t[x][i]])
a.d[x][n]+=
a.d[x][1]+=
}else a.d[x][t[x][i]]+=
115 inline matrix operator *(matrix &x,matrix &y)
z.d[i][j]+=x.d[i][l]*y.d[l][j];
124 void ksm(int cs)
for(;cs&&=1,a=a*a)
if(cs&1)b=b*a;
129 void printb()
for1(i,n)for1(j,n)cout&&i&&‘ ‘&&j&&‘ ‘&&b.d[i][j]&&
133 void printa()
for1(i,n)for1(j,n)cout&&i&&‘ ‘&&j&&‘ ‘&&a.d[i][j]&&
138 int main()
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();k=read();cnt=1;
for1(i,n)add();
for1(i,n)b.d[i][i]=1;
a.d[n][n]=1;
printf("%.7f\n",(double)b.d[1][n]);
&真是一道综合性的难题+好题！标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：/zyfzyf/p/4153860.html
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！Notice:1：4月2日，4月3日是省队十连测第四轮的两场测试，时间为早上八点到下午一点，请各位准时参加!
2:十连测后，将推出月赛，欢迎到时参加！
Ratio1Hello the cruel world.58.668%2Goodbye the cruel world.45.961%3Thanks to the cruel world.27.310%4我微笑不代表我快乐--本ID不用于测速,仅参与排名,谢谢!72.461%5我微笑不代表我快乐--本ID既用于测速,又参与排名,谢谢!53.566%6艰难困苦 玉汝于成 | AFO47.660%7石家庄二中耿明灏61.108%8up and down！||AFO27.630%9AFO25.021%10岁月静好92.031%11将醒，择日而泣43.389%12丶神27.673%13?? ?? ??44.024%14我微笑不代表我快乐--本ID仅用于测速,不参与排名,谢谢!38.521%15蒟蒻2.065.295%16そんなキミだから、恋をした53.741%17人生如梦亦如幻 朝如晨露暮如霞50.166%18AFO41.025%19要是挂了省选，就没法。。？？29.573%20どこまでもゆくよ　一人でもゆくよ37.482%2186.895%22AFO64.547%23AFO30.893%24泉岭精神不朽 汉中诸球永生 %lxxxxxxxxxxxxxxxxxxxxxxxxxx神犇84.687%25AFO63.799%26我是遥遥，我要超过Claris84.459%27AFO44.228%28...89.401%29AFO68.697%30省赛完挂，OI退役|| up! up! up!34.741%31Too young too simple,sometimes naive.46.853%32ただもう一度 逢いに行きたい あなたの笑顏が見たくて27.784%33AFO40.172%34将狼踩尽21.963%35……78.390%36在dos系统诞生以前,帮助Koishi与其姐姐Satori最终战平是最短路问题吗？89.971%37说着说着就真的AFO了，再见OI，墓地一样的第一页27.233%38AFO35.421%39AFO50.493%40AFO37.239%41啦啦啦 我是萌萌哒的zhanghanchong O(∩_∩)O~ http://blog.csdn.net/u48.518%42...43.097%43too naive43.465%44用吉司机的题把吉司机挤出第一页---http://blog.csdn.net/neither_nor26.015%45我们抛弃了一切功名与梦想，只留下记忆为伴了。40.301%46远。31.388%47?( ? )?→QwQ41.015%48.....62.076%49AFO40.082%50我终将在众目睽睽下展翅高飞40.822%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Based on opensource project .2553: [BeiJing2011]禁忌
Time Limit:&20 Sec&&Memory Limit:&128 MBSec&&Special JudgeSubmit:&595&&Solved:&231[][][]
Description
&&&&&&&Magic Land上的人们总是提起那个传说：他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后，Koishi恢复了读心的能力……
如今，在John已经成为传说的时代，再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。
&&&&&&&这次她遇到了Flandre Scarlet——她拥有可以使用禁忌魔法而不会受到伤害的能力。
&&&&&&&为了说明什么是禁忌魔法及其伤害，引入以下概念：
1．字母集A上的每个非空字符串对应了一个魔法。
其中A是包含了前alphabet个小写字母的集合。
2．有一个集合T，包含了N个字母集A上的字符串
T中的每一串称为一个禁忌串（Taboo string）
3．一个魔法，或等价地，其对应的串s因为包含禁忌而对使用者造成的伤害按以下方式确定：
&&&&&&&&&&&把s分割成若干段，考虑其中是禁忌串的段的数目，不同的分割可能会有不同的数目，其最大值就是这个伤害。
由于拥有了读心的能力，Koishi总是随机地使用Flandre Scarlet的魔法，可以确定的是，她的魔法正好对应字母集A上所有长度为len的串。
但是，Flandre Scarlet所使用的一些魔法是带有禁忌的，由于其自身特性，她可以使用禁忌魔法而不受到伤害，而Koishi就不同了。可怜的Koishi每一次使用对方的魔法都面临着受到禁忌伤害的威胁。
你现在需要计算的是如果Koishi使用对方的每一个魔法的概率是均等的，那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。
第一行包含三个正整数N、len、alphabet。
接下来N行，每行包含一个串Ti，表示禁忌串。
一个非负实数，表示所受到禁忌伤害的期望值。
Sample Input
Sample Output
这是一道神题，出题人卡精度什么的就不说了。
首先把模式串建成AC自动机（或trie图），然后考虑在AC自动机上的转移。
对于每一步转移，都有两种情况：
1、子结点没被标记（即不是模式串的结尾单词），有1/alphabet的期望转移到这个子结点。
2、子结点被标记，有1/alphabet的期望值转移到根，并且用一个新结点记录答案。
这样我们可以考虑构造一个矩阵a[i][j]，记录下来结点之间的转移关系。
然后矩阵自乘m次得到的矩阵ans，ans[0][cnt+1]就是答案。
解释一下：对于从i结点转移到j结点，存在一个结点k，使得从i转移到k，然后再转移到j，这就是矩阵乘法的意义。
看了zyf的代码，学到了一种写矩阵乘法的好方法：把矩阵存成结构体，然后定义一种矩阵乘运算，很效率。
调试的时候遇到了一个问题，这题必须用long double,然而long double数组开到了417*417就会出现很奇怪的现象（读者可以自行尝试），只能开到416*416.
具体见代码：
1 #include&iostream&
2 #include&cstdio&
3 #include&cstring&
4 #include&cstdlib&
5 #include&ctime&
6 #include&cmath&
7 #include&algorithm&
8 using namespace
9 #define MAXN 205
<span style="color: # struct node{long double p[MAXN][MAXN];node(){memset(p,<span style="color: #,sizeof(p));}}a,
<span style="color: # int n,m,K,cnt,end[MAXN],q[MAXN],fail[MAXN],vis[MAXN],tr[MAXN*<span style="color: #][<span style="color: #];
<span style="color: # char ch[MAXN];
<span style="color: # inline int read()
<span style="color: # {
<span style="color: #
int x=<span style="color: #,f=<span style="color: #;
char ch=getchar();
<span style="color: #
while(!isdigit(ch))
{if(ch=='-')
f=-<span style="color: #;
ch=getchar();}
<span style="color: #
while(isdigit(ch))
{x=x*<span style="color: #+ch-'<span style="color: #';
ch=getchar();}
<span style="color: #
return x*f;
<span style="color: # }
<span style="color: # inline node operator *(node &x,node &y)//定义矩阵乘运算
<span style="color: # {
<span style="color: #
<span style="color: #
for(int i=<span style="color: #;i&=cnt+<span style="color: #;i++)
<span style="color: #
for(int j=<span style="color: #;j&=cnt+<span style="color: #;j++)
<span style="color: #
for(int k=<span style="color: #;k&=cnt+<span style="color: #;k++)
<span style="color: #
z.p[i][j]+=x.p[i][k]*y.p[k][j];
<span style="color: #
<span style="color: # }
<span style="color: # void insert()
<span style="color: # {
<span style="color: #
int now=<span style="color: #,len=strlen(ch+<span style="color: #);
<span style="color: #
for(int i=<span style="color: #;i&=i++)
<span style="color: #
<span style="color: #
if(!tr[now][ch[i]-'a'])
tr[now][ch[i]-'a']=++
<span style="color: #
now=tr[now][ch[i]-'a'];
<span style="color: #
<span style="color: #
end[now]=<span style="color: #;
<span style="color: # }
<span style="color: # void build()
<span style="color: # {
<span style="color: #
int head=<span style="color: #,tail=<span style="color: #;
<span style="color: #
for(int i=<span style="color: #;i&K;i++) if(tr[<span style="color: #][i]) q[++tail]=tr[<span style="color: #][i];
<span style="color: #
while(++head&=tail)
<span style="color: #
<span style="color: #
int x=q[head];
<span style="color: #
for(int i=<span style="color: #;i&K;i++)
<span style="color: #
<span style="color: #
if(!tr[x][i])
tr[x][i]=tr[fail[x]][i];
<span style="color: #
else {fail[tr[x][i]]=tr[fail[x]][i];
q[++tail]=tr[x][i];}
<span style="color: #
<span style="color: #
<span style="color: # }
<span style="color: # void get()
<span style="color: # {
<span style="color: #
int head=<span style="color: #,tail=<span style="color: #; long double chty=(long double)<span style="color: #.0/K;//期望常数
<span style="color: #
q[<span style="color: #]=<span style="color: #; vis[<span style="color: #]=<span style="color: #;
<span style="color: #
while(++head&=tail)
<span style="color: #
<span style="color: #
int x=q[head];
<span style="color: #
for(int i=<span style="color: #;i&K;i++)
<span style="color: #
<span style="color: #
if(!vis[tr[x][i]])
vis[tr[x][i]]=<span style="color: #,q[++tail]=tr[x][i];
<span style="color: #
if(end[tr[x][i]])
a.p[x][cnt+<span style="color: #]+=chty,a.p[x][<span style="color: #]+=
<span style="color: #
else a.p[x][tr[x][i]]+=
<span style="color: #
<span style="color: #
<span style="color: #
a.p[cnt+<span style="color: #][cnt+<span style="color: #]=<span style="color: #;
<span style="color: # }
<span style="color: # int main()
<span style="color: # {
<span style="color: #
//freopen("cin.in","r",stdin);
<span style="color: #
//freopen("cout.out","w",stdout);
<span style="color: #
<span style="color: #
for(int i=<span style="color: #;i&=n;i++)
{scanf("%s",ch+<span style="color: #);
insert();}
<span style="color: #
<span style="color: #
<span style="color: #
for(int i=<span style="color: #;i&=cnt+<span style="color: #;i++)
ans.p[i][i]=<span style="color: #;
<span style="color: #
for(;m;m&&=<span style="color: #,a=a*a)
if(m&<span style="color: #) ans=ans*a;
<span style="color: #
printf("%.7f\n",(double)ans.p[<span style="color: #][cnt+<span style="color: #]);
<span style="color: #
return <span style="color: #;
<span style="color: # }
阅读(...) 评论()