poj 2185 题目链接 题意：给出一个字符矩形，问一个面积最小的矩形，覆盖掉整个矩形。大概就是二维的最小覆盖子串。 思路：对于每一行做最小覆盖子串，然后求lcm，每一列也是如此。最后记得判断不能超过原有的n,m。 /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 23时46分47秒 File Name :code/poj/2185.cpp ************************************************ */ #include <cstdio> …

参考资料（本文大部分是参考这篇博客，附带一些证明步骤的解释） 首先明确一些概念： 最小覆盖子串：对于某个字符串s，它的最小覆盖子串指的是长度最小的子串p，p满足通过自身的多次连接得到q，最后能够使s成为q的子串。 比如： 对于s="abcab"，它的最小覆盖子串p="abc"，因为p通过在它后面再接上一个p（即重叠0个字符），可以得到q="abcabc"，此时s是q的子串。 对于s="ababab"，它的最小覆盖子串为p="ab"。 pre[i]（或next[i]）的实质是串str[1..i]的最长且小于i的“相等前、后缀”分别 …

poj 2752题目链接 题意：求出所有的前缀和后缀相同的子串的长度。 思路:求出nxt函数，观察发现，从从len递归向前就是答案。 /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 21时05分52秒 File Name :code/poj/2752.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu1686 题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap. 思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置....所以有的教程管这个叫失配函数吧，也不是很难理解的样子。 学会kmp之后的第一道kmp，嘿嘿嘿（是的，poj2406的时候我并不会kmp 2333) /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 20时02分33秒 File Name …

其实一个妹子身上，最让人着迷的，是对生活的态度吧。 ** 过了好久我终于领悟到这点。**

20170801update:当时竟然没有强调next函数的含义？ next[i]的含义是,i之前的整个前缀中，最长的该前缀的前缀和后缀相同的长度。 看图： KMP感觉是我学到现在最难懂的一个算法了QAQ 为什么你们都那么强啊，看几个小时就看懂了... 先放一波我觉得值得看的资料： kmp算法讲解（配图比较全....） kmp学习资料2 说下我对kmp算法的理解： 理解kmp算法大概分成两个部分。 一部分是理解一个naive的kmp算法，可以叫"fast slide" algorithm 思想大概就是，当mismatch发生时，我们并不是一无所有，而是知道在mismatch发生前所匹配的字符的信息的。 然后知 …

题目链接 傻逼模拟。。读完题就ac了。。。 /* *********************************************** Author :111qqz Created Time :2016年08月07日 星期日 18时04分18秒 File Name :code/whust2016/#1/D.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> …

题目链接 其实就是括号匹配的模型。。用栈即可。。被我写挂好几发。。该死该死。。。 /* *********************************************** Author :111qqz Created Time :2016年08月07日 星期日 17时34分13秒 File Name :code/whust2016/#1/HH.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

hdu 3415 题意：给出n个整数，是一个环（也就是a[n]右边是a[1]）求一段长度不超过k的数使得和最大，问最大和是多少并给出这段数的位置。 思路：为了处理环，先把n个数复制一下就好，然后求前缀和sum[i] 由于区间[l,r]的和可以用前缀和表示为sum[r]-sum[l-1] 因此在区间长度小于等于k的前提下，我要求sum[r]-sum[l-1]的最大值，如果我们考虑把端点r固定，那么就是要求[l-1,r-1]中的sum的最小值。 因此我们考虑用单调队列来维护sum[i-k]到sum[i-1]的最小值。 我们的做法是：枚举区间右端点i，同时用单调队列维护i之前的k个数[i-k,i-1]的最小值。 由于要求“If there …

ural 1126 题意：n个数，求从第k个元素开始，求每k个元素的最大值（一共求n-k+1次） 思路：单调队列。 单调队列学习链接 其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333 说下我的理解： 单调队列的尾端（就是后进入元素的那一端）其实和单调栈类似。 首端加了个元素期限的概念，不断删除“过期”的元素。 所谓过期的元素，对于这道题来说，当我往前移动到第k+1个元素的时候，第1个元素就是过期了的元素，堆答案不会再有贡献。 理论上单调队列中的元素是<元素的期限，元素>的二元组。 而一般元素的"期限"是由下标的位置决定的，而得到下标就可以知道元素。 所以我们实际操 …