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

ydc的博客

 
 
 

日志

 
 

bzoj 2108 语音识别  

2014-01-16 08:33:30|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
感觉是wc最水的一题了
不知道为何通过人数如此少?
兴许是卡题意的原因……

没什么特别好说的……
第一二问,我当然知道后缀数组能做拉……反正不会TLE所以我写的二分+hash
第三四问则是dp和输方案问题

先做第一二问
首先看到K,M很小
所以可以想到……枚举小串,枚举原串的第i位判断从这出发能够匹配
如果当前位相同二分+hash找到下一个不同的,否则暴力……由于k<=20,所以最多暴力二十次
然后让人吐血的事情出现了!!
当我打下前两行的那句话的一瞬间——复杂度是O(nmk*log n)的啊啊!!
好吧我相信正解还是要后缀数组的
二分加hash我也不知道为什么能过

后缀数组能做到O(1)查询lcp,所以一二问复杂度是O(nmk)了

接下来是三四问,看到m<=20有木有状压dp的欲望呢?
其实完全不搭边……

在做一二问的时候预处理match[i][j]表示识别单词i以j为末尾的最靠后的开头
dp[i][j]表示到了第i位,最后一个识别的字是j的最长距离
将dp[i-1][j]与dp[match[j][i]][k]+1中取最小……dp[match[j][i]][k]+1可以O(1)得到
第三问就解决了
第四问看起来是很常规的询问,但是dp[i][j]的转移中有不填的转移……这就让方案很容易重复了
纠结了一阵子之后,突然发现一个贪心性质:如果match[j][i]!=-1的话……最优方案一定可以不是dp[i-1][j]!
于是第四问也解决了……只能感慨“区间图是弦图弦图是完美图”的性质真的是贪心党杀人越货之神器阿
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define mod 1000003
#define base 1000000007
#define maxm 25
using namespace std;
typedef unsigned long long ULL;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
int match[maxm][maxn];
int cnt[maxm];
int n,m,lim;
int a[maxn],word[maxm][maxn],len[maxm];
ULL power[maxn],hash[maxn],hashword[maxm][maxn];
void read()
{
Read(n),Read(m),Read(lim);
power[0]=1;
for(int i=1;i<=n;++i)
power[i]=power[i-1]*base;
for(int i=1;i<=n;++i)
{
Read(a[i]);
hash[i]=hash[i-1]*base+a[i];
}
for(int i=1;i<=m;++i)
{
Read(len[i]);
for(int j=1;j<=len[i];++j)
{
Read(word[i][j]);
hashword[i][j]=hashword[i][j-1]*base+word[i][j];
}
}
}
ULL gethash(int L,int R)
{
return hash[R]-hash[L-1]*power[R-L+1];
}
ULL gethash(int p,int L,int R)
{
return hashword[p][R]-hashword[p][L-1]*power[R-L+1];
}
void check(int p,int L)
{
int differ=0,i=1,st=L;
while(differ<=lim&&i<=len[p]&&L<=n)
{
if(word[p][i]!=a[L])
++L,++differ;
else
{
int l=1,r=min(n-L+1,len[p]-i+1);
while(l<r)
{
int mid=(l+r)>>1;
gethash(L,L+mid)==gethash(p,i,i+mid)?l=mid+1:r=mid;
}
i+=l,L+=l;
}
}
if(i<=len[p])
return ;
--L;
int t=min(n-L+1,lim-differ+1);
cnt[p]=cnt[p]+min(n-L+1,lim-differ+1);
for(int j=1;j<=t;++j)
match[p][L+j-1]=st;
}
void add(int &a,int b)
{
a+=b;
if(a>=mod)
a-=mod;
}
bool use[maxn][maxm];
int sum[maxn][maxm],dp[maxn][maxm],maxv[maxn];
int pre[maxn][maxm];
int calc(int n,int p)
{
n=pre[n][p];
if(use[n][p])
return sum[n][p];
if(dp[n][p]==1)
return 1;
use[n][p]=true;
int i=match[p][n]-1;
for(int j=1;j<=m;++j)
if(dp[n][p]==dp[i][j]+1)
add(sum[n][p],calc(i,j));
return sum[n][p];
}
void work()
{
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
match[i][j]=-1;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
check(i,j);
int s1=0,s2=0;
for(int i=1;i<=m;++i)
s1=s1+(cnt[i]!=0),s2+=cnt[i];
printf("%d %d\n",s1,s2);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
dp[i][j]=dp[i-1][j],pre[i][j]=pre[i-1][j];
if(match[j][i]!=-1)
dp[i][j]=maxv[match[j][i]-1]+1,pre[i][j]=i;
maxv[i]=max(maxv[i],dp[i][j]);
}
int ans=0;
for(int i=1;i<=m;++i)
if(dp[n][i]==maxv[n])
add(ans,calc(n,i));
if(maxv[n]==0)
ans=1;
printf("%d %d\n",maxv[n],ans);
}
int main()
{
read();
work();
return 0;
}


  评论这张
 
阅读(405)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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