hdu1686

题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap.

思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置....所以有的教程管这个叫失配函数吧，也不是很难理解的样子。

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

20170801update:当时竟然没有强调next函数的含义？

next[i]的含义是,i之前的整个前缀中，最长的该前缀的前缀和后缀相同的长度。

题目链接 傻逼模拟。。读完题就ac了。。。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月07日 星期日 18时04分18秒
  4File Name :code/whust2016/#1/D.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9 …

题目链接

其实就是括号匹配的模型。。用栈即可。。被我写挂好几发。。该死该死。。。

/* ***********************************************
Author :111qqz
Created Time :2016年08月07日 星期日 17时34分13秒
File Name :code/whust2016/#1/HH.cpp
************************************************ */

1#include <cstdio>
2#include <cstring>
3#include <iostream>

 1 …

hdu 3415 题意：给出n个整数，是一个环（也就是a[n]右边是a[1]）求一段长度不超过k的数使得和最大，问最大和是多少并给出这段数的位置。

思路：为了处理环，先把n个数复制一下就好，然后求前缀和sum[i]

ural 1126 题意：n个数，求从第k个元素开始，求每k个元素的最大值（一共求n-k+1次） 思路：单调队列。 单调队列学习链接 其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333

hdu 1559

题意：给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。

思路：二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。

poj 3494

题意：给出一个n*m个0-1图，求最大的全部由1组成的矩阵。

思路：同poj 1964,一共做n+2×m次单调栈。。。数组开小re一发。。某处stk忘记清空re 1发。。。智力-2.。。3A

poj 2796

题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

现在求value的最大值，并且输出得到这个最大值的区间。