题意:给你一个序列,让你去建立一个排序二叉树,然后遍历一遍,偶数是0,奇数是1,把走过的所有的数记录下来,求给你的01串和你得到的匹配次数

思路:开始写的时候,直接就去按照正常的建立去建了。平均复杂度是 nlogn。但是树如果退化的话,直接就成了n^2(一条链),就肯定超时。。

其实在建立的时候,只要找到前面的节点中大于当前节点的最小值,和小于当前节点的最大值,一定是插在两者中的一个。并且只有一个。知道这个之后

这个题建立的复杂度就没问题了,但是如果在遍历的时候,直接去搜。。还会爆栈啊,扩栈都不行。必须得自己写。。也就是把递归改成循环。

这个地方弄完之后,就比较简单了。直接KMP就行了。

还有一点。。G++是真坑,又卡内存又卡时间的。以后只用C++啊

 

Codeforces Round #299 (Div. 1)B. Tavas and Malekas(kmp)

非常好的kmp题。 题意:给定原字符串的长度 n,和一个数字 m,给定一子串 s。然后输入 m个数字。 代表 s 在原串中出现的位置。 求满足题意的原串的个数。 &nb...

阅读全文

Number Sequence (KMP)

纯 KMP。。 #include <vector> #include <list> #include <map> #include <string> #include &l...

阅读全文

Codeforces Round #269 (Div. 2) D. MUH and Cube Walls(KMP)

KMP 算法。。 没什么好说的。 直接上模板吧。 学习参考了 : http://blog.csdn.net/v_july_v/article/details/7041827   ...

阅读全文

欢迎留言

*