hdu 2222 题目链接 题意：给出n个模式串，一个文本串，问文本串中出现了多少各模式串。 思路：ac自动机裸题。代码风格来自bin神。静态数组的写法。 需要理解 在build fail的时候，先单独处理root的必要性。 /* *********************************************** Author :111qqz Created Time :2016年08月16日 星期二 06时00分48秒 File Name :code/hdu/2222.cpp ************************************************ */ #include …

突然感觉。。。 我这种几乎没有恋爱经验的人。。。 感觉被妹子随便用点手段就能收了啊orz 想想真是可怕。。。 别问我为什么突然有这种的感慨。。。 吓傻了。。。。 还是好好写代码比较靠谱。

老规矩，先放资料： 参考资料1 参考资料2 参考资料3 （其实这些资料我都没怎么看。。。。因为感觉。。。理解起来非常容易的样子orz） 我的理解：感觉这东西如果明白了kmp和trie，理解起来就完全没难度。。。 感觉就是在trie上做kmp...？ nxt数组换个名字叫fail。。。。其实是一样的东西吧。。。？ 来来来，先干一波题再回来总结。。。 感觉暴力匹配相对于kmp（都是线性单模式串），就好像trie相对于ac自动机（都是树上多模式串） 另一个方向：暴力相对于trie，（都是暴力）就好像kmp相对于ac自动机（都是经过失配优化） ac自动机的题目里这么多和dp结合在一起让我怎么做啊orz... 以及感觉。。。ac自动机的水平 …

poj 2001 题目链接 题意：给出n个字符串的表，问每个字符串的简化表示。简化表示的要求是，以该字符串的最短的而且不能产生歧义的前缀来表示。 思路：字典树，多一个cnt属性，每次insert的时候，路过的每个节点的cnt++ find的时候从root往下扫。。遇到的cnt为1的节点结尾的字符串。。就是该单词的唯一表示。。。 按照这个思路写了一发。。。1A好开心哈哈哈 /* *********************************************** Author :111qqz Created Time :2016年08月16日 星期二 02时55分22秒 File Name …

poj 3630 题目链接 题意：给出n个字符串，问是否满足所有的字符串都不以其他的字符串为前缀。 思路：字典树，先建树，然后每次查找的之前先删掉自己，找完以后再加回来。 以及这题动态建艹不过。。。学习了一下静态建树的写法。。。第一次写静态的写法。。。可以当做模板用。。。 /* *********************************************** Author :111qqz Created Time :2016年08月16日 星期二 00时46分23秒 File Name :code/poj/3630.cpp ************************************************ …

hdu 1247 题目链接 题意：给出n个字符串的单词表，输出所有的字符串a，满足字符串a是由n中另外两个字符串拼接成的。 思路：字典树。。其实我一开始想出了正解。。。。就是分割一个单词然后分别在trie上查找。。。但是由于题目坑爹得没给单词的长度这个数据范围。。并不是很敢写2333。。。看了下题解发现就是这么做。。。然后写了下1A。。。 不给数据范围玩个鸟啊。。。 /* *********************************************** Author :111qqz Created Time :2016年08月16日 星期二 00时08分01秒 File Name :code/hdu/1247.cpp …

hdu 5536 题目链接 题意：给出n个数，然后问最大的(a[i]+a[j])^a[k] (i,j,k互不相同) 思路：异或和最大很容易想到字典树。。但是如何保证i,j,k互不相同这里没有想明白。。。。。我的想法是加一个标记代表之前的id，但是我加的标记是只有在叶子节点上才有的。。。也就是会出现走到了最后一步才发现这个节点是不能走的情况。。。 正确的做法是，加一个cnt标记。 每次插入的时候，这个数从根节点到叶子节点每个节点的cnt都+1 删除的时候做就是每个节点的cnt都-1. 这样子每次Find的时候只走cnt>0的点。。 这种做法的正确性基与： 两个不同的数。。一定有至少一位的二进制数不同。。。保证了当只出现过一次的 …

hdu 4825 题目链接 题意：给定n个数，然后给出m个询问，每组询问一个数x，问n中的数y使得x和y的异或和最大。 思路：字典树。。把每个数转化成二进制，注意补全前导0，使得所有数都有相同的位数。 如果想要异或和最大，那么每一位尽可能都是1. 所以做法是，先构建字典树，然后每次find的时候，尽可能按照和当前寻找的数的位相反的位的方向走（如果有的话） 比如当前位是1，那我就往0的方向走。 需要注意的是，多组数据，每次要重新初始化一遍。 做法是 在struct 中重新 root = new Node() 一下。。这样就重新调用了Node中初始化用的构造函数。 /* …

hdu 1251 题目链接 题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。 思路：trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。？ 以及动态开辟内存记得free...？ /* *********************************************** Author :111qqz Created Time :2016年08月14日 星期日 19时58分41秒 File Name :code/hdu/1251.cpp ************************************************ …

hdu 5833 题目链接 题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。 思路： 完全平方数就是要求每个质因子的指数是偶数次。 列方程组，a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子，建立异或方程组，要求因子个数为偶数，即异或为0 然后得到自由元的个数为num,答案为2^num-1 (减去空集) #include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include …