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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj3530【SDOI2014】数数解题报告  

2014-04-14 20:32:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目链接

由于刚刚加上题目,所以题目描述什么的全是空白= =,题目描述及测试数据传送门

可以先看看弱化版:bzoj1030

话说这题居然是我AC自动机的第一题,噗……

特别感谢hzw大神提供帮助

众所周知,AC自动机可以用来在一个母串里面查找很多个子串,然后这题要求的是这些子串都没出现过、都差不多的对吧

然后我们对这些一大堆的子串都建自动机

我们设dp[i][j]表示跑到了第i位,目前在自动机的标号为j的点上……

然后我们尝试在后面加0~9,如果加上后在自动机里,则跑到那个位置,否则沿着fail指针往回跑,直到跑到有的地方。

(Q:如果一直没有怎么办?A:给root虚设上0~9所有的点)

于是大致的算法就出来了,然后我们就写啊写……

等会!

我们这样只求出来n=10的整数倍-1的情况= =,对于有n有限定的东西怎么办呢?

我们可以再增加一维,表示这个是被限制了还是没有被限制,显然,每一位只有一种被限制的情况,那就是到该位为止全是满的。

所以不增加复杂度……

然后呢,这样可以拿到80分。

为什么丢了两个点?因为我们没有考虑前导0!

我们考虑一下前面的过程,我们是高位补0的……15会被当做0015处理。所以会被015匹配= =

所以呢……我们不得不再增加一维= =,表示到这里还有没有数字= =,当然,这维只会出现在0或00这样的地方= =,所以算复杂度时直接被无视了……也许常数什么的影响都比它们大= =

PS:为什么我算来算去复杂度就是会T的?然后bzoj上居然跑的比本机还快= =,难道是开了o2的缘故?

tag:修正一个bug:

for (int i=acam.root;i<=acam.tot;i++)

{

    int tmp=i;

    bool bo=true;

    while (tmp!=acam.root)

    {

        tmp=t[tmp].fail;

        if (t[tmp].num) {bo=false;break;}

    }

    if (!bo) t[i].num=1;

}

这里是不能被注释掉的,否则会答案错误(尽管这题数据弱没体现出来)

代码极渣,请轻喷


#include<cstdio>
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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