BZOJ 1212 HNOI 2004 L语言 Trie树

题目大意:给出一些单词,和一些句子,当且仅当句子可以分割成的子串都可以被词典翻译,就说明这个子串是可以被翻译的。求最长的可以被翻译的前缀长度。

思路:利用Trie树来刷数组,能够刷到的最长的地方就是这个串最长可以翻译到的地方。

PS:在BZOJ上Trie居然比AC自动机快,我的渣代码都刷到第一篇了。。。

CODE:

#include #include #include #include using namespace std; struct Trie{ Trie *son[27]; bool end; Trie() { memset(son,NULL,sizeof(son)); end = false; } }*root = new Trie(); int words,cnt; char s[1 son[*s - 'a'] == NULL) now->son[*s - 'a'] = new Trie(); now = now->son[*s - 'a']; ++s; } now->end = true; } inline void Ask(char *s,int i) { Trie *now = root; int t = 0; while(*s != '') { if(now->son[*s - 'a'] == NULL) return ; now = now->son[*s - 'a']; ++s; ++t; if(now->end) f[i + t] = true; } if(now->end) f[i + t] = true; } inline int Work() { memset(f,false,sizeof(f)); f[0] = true; int re = 0,length = strlen(s + 1); for(int i = 0; i > words >> cnt; for(int i = 1; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:codeforces 486C Palindrome Transformation 贪心求构造回文
下一篇:C++ Primer(第五版)读书笔记 & 习题解答 --- Chapter 2
相关文章

C语言:超越C++下一代C++ —C++/CLI简

在C++语言中,关于内联函数(inline)的入

C++:最强大的.NET语言之可访问性

C++:最强大的.NET语言之装箱

C++:最强大的.NET语言之内存与资源

C++:最强大的.NET语言之对象构造

【CC++语言入门篇】-- 文件操作

C++语言之深入浅出的介绍

【CC++语言入门篇】-- 位运算

【CC++语言入门篇】--序言

图文推荐
BZOJ 1212 HNOI 2004 L语言 Trie树
ZOJ 3640 Help Me
BZOJ 1212 HNOI 2004 L语言 Trie树
CF 518C(Anya and
BZOJ 1212 HNOI 2004 L语言 Trie树
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-08 人气:5
本文关键词:
分享到:

相关文章

  • BZOJ 1212 HNOI2004 L语言 AC自动机(Trie树)+动态规划 2013-05-24

    题目大意:给定一个单词表和m个字符串 问每个字符串的最长的前缀,满足这个前缀可以拆分成一些字符串 使这些字符串都在单词表中出现过 再也不敢看错数据范围了……一道明明用Trie树能解决的问题居然被我写了AC自动机…… 将单词表中的单词全都插入AC自动机 每个单词所在的节点记录这个单词的长度 然后对于每个字符串 用f[i]表示长度为i的前缀是否能拆分成单词表中的单词 跑AC自动机 对于每个匹配的节点 从这个节点开始到根的fail路径上的所有len f[i]|=f[i-len] 找到最大的为1的f[i

  • BZOJ 3144 HNOI 2013 切糕 最小割 2012-11-27

    题目大意:给出一个三维的点阵,没个点都有可能被切割,代价就是这个点的权值。相邻的切割点的高度差不能超过D,问最小的花费使得上下分开。 思路:很裸的最小割模型,很神的建图。 S->第一层的点,f:INF 所有点->它下面的点,f:INF 一个点的入->一个点的出,f:val[i] (i,j,k) - > (i - d,j,k),f:INF 最下面一层的点->T:f:INF 然后跑最小割就是答案。 为什么见:http://www.cnblogs.com/zyfzyf/p

  • BZOJ 1997 HNOI 2010 Planar 2-SAT 2013-05-22

    题目大意:给出一个无向图,保证这个图有哈密顿回路,求这个图是不是平面图。 思路:平面图的判定条件之一:如果边数大于点数*3+6那么这个图一定不是平面图。这算是一个强剪枝吧。 我们把图中哈密顿回路的这个环上的边去掉,就变成了判定边能否不想交的2-SAT问题,POJ好像有一个原题来着。建图方法我就不说了,相信大家看到2-SAT就知道怎么写了。 CODE: #include #include #include #include #define MAX 10010 using namespace std

  • BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并 2015-02-17

    题目大意:给出一串颜色,有两种操作,1.询问有多少块颜色。2.将一种颜色改变成另一种颜色。 思路:好像和染色什么的比较像,但是看了题解之后发现完全不是那么回事。 对于每一种颜色维护一个链表,然后在修改颜色的时候,暴力修改一种颜色成为另一种颜色,用启发式合并可以保证复杂度不超过O(nlogn)。但是由于是启发式合并,有可能导致你就改了反了颜色,这个时候记录一个映射,然后把修改错的记录下来。各种信息仔细讨论一下。。。 CODE: #include #include #include #include

  • BZOJ 1009 HNOI 2008 GT考试 AC自动机+矩阵乘法 2013-02-02

    题目大意:给出一个不能出现的字符串,问长度为k的字符串有多少种。 思路:用给定串建立一个AC自动机(或者KMP随便了),然后跑矩阵乘法就行了。 CODE: #include #include #include #include #include using namespace std; int k,length,p; char s[MAX]; int son[MAX][MAX],cnt; bool end[MAX]; void Insert() { int now = 0; for(int i

  • BZOJ 1011 HNOI2008 遥远的行星 递推 2012-06-12

    题目大意:给定一条直线上的一些行星,按照题目要求计算,求每个点所受重力 我没有在标题上写”乱搞“的原因是我看了题解一堆说乱搞的0.0 然后我就真乱搞了0.0 每个点只计算临近的1000个,结果狂WA不止。。。 乱搞肯定过不去 不用想了 其实说是递推比较合适 详细题解见http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7 我不累述了 #include #include #include #include #define M 10010

  • BZOJ 3218 a + b Problem 可持久化线段树+最小割 2012-07-04

    题目大意:。。。自己看 从源点出发,分别向汇点连两条流量为a和b的边,跑最大流即是a+b。 代码: #include #include #include #include #define M 10 #define S 1 #define T 2 #define INF 0x3f3f3f3f using namespace std; struct abcd{ int to,f,next; }table[100]; int head[M],tot=1; void Add(int x,int y,in

  • BZOJ 2165 大楼 倍增Floyd 2014-06-05

    题目大意:给出一个有向图,问总路径长度>=k最少需要经过多少边。 思路:记录几个辅助数组,f[p][i][j]表示走2^p步时最长的路径是多少。g[i][j]表示目前从i到j最长路是多长。 f的dp方程是f[p][i][j] = max(f[p][i][j],f[i - 1][i][j] = f[i - 1][j][k]); 然后在处理g数组的时候当从1开始的最长路大于等于k的时候就直接break掉,这个时候不计入总答案,否则计入总答案。 这样就处理出了总长度 CODE: #include

  • BZOJ 1190 HNOI2007 梦幻岛宝珠 动态规划 2015-01-17

    题目大意:01背包,其中weight 直接背包肯定TLE+MLE 考虑到每个weight都能写成a*2^b的形式,显然我们要按照b分层来进行背包 令f[i][j]表示有j*2^i+(w&(1 首先每层内部先做一个01背包 然后层与层之间再转移 从大到小枚举j 转移方程为f[i][j]=max{f[i][j],f[i][j-k]+f[i-1][min(k*2+((w>>i-1)&1),1000)]} 这个是怎么来的呢?我们首先枚举j,然后枚举同一层花销的空间j-k,那么

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.057 (s). 10 q(s)