- 浏览: 389298 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
/* AC自动机,增设虚拟节点,求长度为n的字符串中包含至少k个给出的关键字的字符串的个数,结果模MOD。 增设虚拟节点的目的是为了方便状态转移。 dp转移实际上是在安全图上进行的! */ #include <cstdio> #include <cstring> #include <map> using namespace std; const int N= 55*20; //节点个数的最大值 const int S=4; //不同的字符 个数 const int MOD=20090717; const int LEN=1005; //n的最大值 struct node{ node *sons[S], *fail; int id; //id是节点的标号 bool flag; //标记该节点是否是安全的 }nodes[N], *root; int cnt; //cnt是树中节点的 个数 node *que[N]; int n, m, k; int dp[2][N]; map<char, int> mci; map<int, char> mic; char str[LEN]; void init(){ mci['A']=0; mic[0]='A'; mci['G']=1; mic[1]='G'; mci['C']=2; mic[2]='C'; mci['T']=3; mic[3]='T'; } void clear(){ cnt=0; root=NULL; } node* newNode(){ node* ans=&nodes[cnt]; memset(ans->sons, 0, S*sizeof(node*)); ans->fail=NULL; ans->id=cnt++; ans->flag=true; return ans; } int hash(char ch){ //字符的哈希函数,根据不同的需要而定 return mci[ch]; } //j表示当前关键字的标号 void insert(node*& root, char* str){ node* t=root; int i, k; for(i=0; str[i]; i++){ if(t->sons[k=hash(str[i])]==NULL){ t->sons[k] = newNode(); } t=t->sons[k]; } t->flag=false; } //在某些时候还需要吧root的S个儿子节点中为空赋值为root(所谓的虚拟节点,树中的 其他节点也可以 //添加类似的虚拟节点) void getFail(node*& root){ int l, r, i; node *t; l=r=0; root->fail=root; //这样可以保证每个节点的fail指针都是非空的 for(que[r++]=root; l!=r; ){ t=que[l++]; for(i=0; i<S; i++){ if(t->sons[i]){ que[r++]=t->sons[i]; if(t==root){ t->sons[i]->fail=t; }else{ t->sons[i]->fail=t->fail->sons[i]; } if(!t->sons[i]->fail->flag){ t->sons[i]->flag=false; } }else{ //增设虚拟节点 if(t==root) t->sons[i]=t; else t->sons[i]=t->fail->sons[i]; } } } } bool input(){ int n; scanf("%d", &n); if(n==0)return false; int i; char s[25]; clear(); root=newNode(); for(i=0; i<n; i++){ scanf("%s", s); insert(root, s); } return true; } int ca=0; void solve(){ getFail(root); int u, v, i, j, k, nxt, tmp; for(i=0; i<cnt; i++){ dp[0][i]=-1; } dp[0][0]=0; scanf("%s", str); for(u=0, i=0; str[i]; i++){ v=u^1; for(j=0; j<cnt; j++){ dp[v][j]=-1; } for(j=0; j<cnt; j++){ if(dp[u][j]==-1) continue; for(k=0; k<S; k++){ if(!nodes[nxt=nodes[j].sons[k]->id].flag) continue; tmp = dp[u][j]; if(str[i]!=mic[k]){ tmp++; } if(dp[v][nxt]==-1 || dp[v][nxt]>tmp){ dp[v][nxt]=tmp; } } } /* *这里dp[v][k]表示长度为字符串str的前i个字符组成的子串走到节点k需要改变的最少次数, *这个走到节点k可以这样来理解,该子串的后面部分等于节点k代表的字符串!例如子串为abbc, *节点k代表的字符串是bb,那么该子串走到节点k的时候就成了abbb了,所以就容易理解为什么 *会有下面这一句了,因为要把最后一个字符c变成b! *if(str[i]!=mic[k]){ tmp++; } */ u=v; } int ans=-1; for(j=0; j<cnt; j++){ if(!nodes[j].flag) continue; if(dp[u][j]!=-1 && (ans==-1 || ans>dp[u][j])){ ans=dp[u][j]; } } printf("Case %d: %d\n", ++ca, ans); } int main(){ //freopen("in.txt", "r", stdin); init(); while(input()) solve(); return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1111算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 924算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 935/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1040/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1417source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 902source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2435const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1196枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1041source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 920source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 961求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 870/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1320/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 951/* * AC自动机,每个节点 添加一个d表示节点代 ... -
hdu2825
2011-11-04 11:53 996/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 1023/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 929/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3358/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 863source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 948//半平面交+多边形和圆的交的面积 #include ...
相关推荐
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...
标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...
poj dna sorting 问题,研究的ac coderrrrrrr
简单的字符串操作和求逆序对数,是程设poj习题
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告