Posts

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

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

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

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

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

poj 2082 题目链接 题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。

poj 1964 题意：n*m 的 maze，由 ‘R’ 和 ‘F’ 组成，现在要求找到面积最大的矩形，使得矩形中所有格子都是 ‘F’。

poj 3250 题意： n头牛排成一列，第n只牛在最前面，第1只牛在最后面。第i只牛能看到的牛的个数是，它前面的且没有被其他牛遮挡的牛的个数，遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。

poj 2559 题意：给定从左到右多个矩形，已知这此矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，求该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。

题目链接 题意：定义一个函数 F。 For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12)

poj 2406 题意：给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值

题目连接 题意：求所有不同的子串个数。 思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A

hdu5787 题意：给出l,r,k求区间[l,r]中满足任意相邻k个数字都不相同的数的个数.

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串。假设字符串的长度为 n，那么长度为 1 的子串有 n 个，为 2 的有 n-1 个……为 n 的有 1 个，一共就是 n*(n+1)/2 个，但是实际上会有重复的。

poj3261 题意：给一个字符串，要求找出至少出现k次的最长重复子串…

poj 1743 题意：n 个数字（1..88）表示的音符，问最长的连续两段长度至少为 5 的变化相同的音符段的长度。

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么）

poj 2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。

hdu1280 题意：给出n(3000)个数，两两求和，输出最大的m(5000)个和。

原文链接：链接 讲了后缀数组的概念，然后从最暴力的 O(nnlogn) 的复杂度（O(n) 用来比较字符串，O(nlogn) 是排序的复杂度）逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇 The Skew Algorithm 的论文。