这道题是很裸的trie图(AC自动机)
王赟的论文里面讲过一道题,求长度为n的字符串中不出现给定字符串的方案数,跟这道题差不多
这道题dp方程多加一维,f[i][j][k]表示长度为i,trie图位置在j,是否经过了至少一个匹配串的方案数
trie图很久没写了……今天复习了一下……
用的是未改进的trie图,因为字符集比较小……
PS:吐槽这题的数据很水……我在trie图上加边的过程一开始写错了也能AC……
您还没有登录,请您登录后再发表评论
[NOI2003]文本编辑器(Treap) [JSOI2004]平衡点(模拟退火) [JSOI2004]平衡点(正交分解) [NOI2005]维护数列 [POI2007]ZAP-Queries [HAOI2008] 糖果传递 [HAOI2008]圆上的整点.cpp [HNOI2008]GT考试 [HNOI2008]遥远的...
作为一个计算机科学家,JYY有一套黑白色的拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白色子矩形。之后JYY发现,可以通过改变这S块拼图
【故事背景】宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的
最大数 JSOI2010 (BZOJ1012 可提交) 4. 理想的正方形 HAOI2007 (BZOJ1047 可提交) 5. Lineup 排队 USACO2007 (BZOJ1699 可提交) 6. BZOJ2738 矩阵乘法 7. BZOJ2311 花神游历各国 8. BZOJ1878 HH 的项链 9. BZOJ3132...
C++编写最大公约数与最小公倍数,使用函数的调用,可以有其他程序衔接调用
ACM 计算几何 必看 ACM 计算几何 必看 ACM 计算几何 必看
jsoi 论文。。。用单调性优化动态规划。。20字。。。
江苏省2012信息学集训队论文,许昊然(国家队大神)著,数据结构漫谈(148页). 数据结构在序列中的应用,dfs序,树形结构,函数式数据结构,函数式块状链表 , 指纹算法,扩展后缀数组,etc
相关推荐
[NOI2003]文本编辑器(Treap) [JSOI2004]平衡点(模拟退火) [JSOI2004]平衡点(正交分解) [NOI2005]维护数列 [POI2007]ZAP-Queries [HAOI2008] 糖果传递 [HAOI2008]圆上的整点.cpp [HNOI2008]GT考试 [HNOI2008]遥远的...
作为一个计算机科学家,JYY有一套黑白色的拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白色子矩形。之后JYY发现,可以通过改变这S块拼图
【故事背景】宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的
最大数 JSOI2010 (BZOJ1012 可提交) 4. 理想的正方形 HAOI2007 (BZOJ1047 可提交) 5. Lineup 排队 USACO2007 (BZOJ1699 可提交) 6. BZOJ2738 矩阵乘法 7. BZOJ2311 花神游历各国 8. BZOJ1878 HH 的项链 9. BZOJ3132...
C++编写最大公约数与最小公倍数,使用函数的调用,可以有其他程序衔接调用
ACM 计算几何 必看 ACM 计算几何 必看 ACM 计算几何 必看
jsoi 论文。。。用单调性优化动态规划。。20字。。。
江苏省2012信息学集训队论文,许昊然(国家队大神)著,数据结构漫谈(148页). 数据结构在序列中的应用,dfs序,树形结构,函数式数据结构,函数式块状链表 , 指纹算法,扩展后缀数组,etc