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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3530][Sdoi2014]数数  

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

  下载LOFTER 我的照片书  |

3530: [Sdoi2014]数数

依旧是ac自动机上dp

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

GTY神犇省选时当场A掉这题

然后我交到BZOJ还WA了一次QAQ

因为全程指针所以f值是用节点来存的。。

看起来有点蛋疼(在意细节的都是笨蛋=w=)

按照惯例题解在代码下方

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 2000+10;
const int LEN = 1500+10;
const int MOD = 1e9+7;
struct Node{
Node(){}
int id,f[2][3],v[2][3];bool end;
short d;
Node *ch[10],*fail;
}house[LEN];int hn;
Node *newNode(){if(hn < LEN){return &house[hn++];}return new Node();}
queue <Node *>dui;
struct AC{
Node *ROOT;
int size;
AC(){ROOT = newNode();ROOT->fail = ROOT;}
void insert(const char str[]){
int len = strlen(str);
Node *r = ROOT;
for(int i=0;i<len;i++){
int c = str[i]-'0';
if(!r->ch[c]){r->ch[c] = newNode();r->id = ++size;r->ch[c]->d = c;}
r = r->ch[c];
}r->end = 1;
}
void makefail(){
for(int i=0;i<10;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<10;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;
int scans(char a[]){
char cc=' ';int len=0;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
while('0'<=cc&&cc<='9'){
a[len++] = cc;
cc=getchar();
}a[len] = 0;
return len;
}
struct state{
state(){r=0;}
state(Node *rr,short ii,short t):r(rr),i(ii),type(t){}
Node *r;int i;short type;
};
queue <state>que;
int n,m,ans;
short numb[N];
int main(){
int i,j;char str[LEN];
//freopen("input.txt","r",stdin);
numb[0]=scans(str);
for(i=0;i<numb[0];i++)numb[i+1] = str[i]-'0';
scanf("%d",&m);
for(i=1;i<=m;i++){
scans(str);
ac.insert(str);
}ac.makefail();
que.push(state(ac.ROOT,0,1));
ac.ROOT->f[0][1] = 1;
ac.ROOT->v[0][1] = 0;
while(!que.empty()){
state now = que.front(),next;que.pop();
if(now.i == numb[0]){
ans += now.r->f[now.i%2][now.type];
if(ans >= MOD) ans-=MOD;
continue;
}
Node *r = now.r;
for(int i=0;i<10;i++){
if(now.type==1&&i>numb[now.i+1])break;
next = state(r->ch[i],now.i+1,0);
if(now.type==1&&i==numb[now.i+1])next.type =1;
//N的开头不可能为0
if((now.i==0&&i==0)||(now.type==2&&i==0))next.type = 2,next.r = ac.ROOT;
if(next.type!=2&&r->ch[i]->end)continue;
//goto next
int &nowf=next.r->f[next.i%2][next.type];
if(next.r->v[next.i%2][next.type] != next.i){
next.r->v[next.i%2][next.type] = next.i;
nowf = 0;
que.push(next);
}
nowf += r->f[now.i%2][now.type];
if(nowf >= MOD)nowf -= MOD;
}
}
printf("%d\n",ans-1);
return 0;
}

题解:

很明确是AC自动机上DP,如果到单词结尾就不进行转移

但是这里有一个限制是上限N,所以多开一个状态记录此时是否是上限(数位DP思想)

细节:

例如当N = 111,00∈S,001这个数是合法的

所以为了判断这个需要多开一维(其实也不用,是我嫌分开写比较麻烦)记录当前是否全是0(数位DP常见问题)

如果全是0的话不仅到单词末尾节点要转移,而且每次都要转移到根节点  <=(我就是因为这里WA了)

  评论这张
 
阅读(532)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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