poj 2082 题目链接

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

poj 1964

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

poj 3250

题意：

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

poj 2559

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

题目链接

题意：定义一个函数F．．

For exampe: _F_(_babbabbababbab_, _babb_) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

  * 

(1, 4)

  * 

(4, 7)

  * 

(9, 12)

  * 

(1, 4), (4, 7)

  * 

(4, 7), (9, 12)

  * 

(1, 4), (4, 7), (9, 12)

erfen

poj 2406

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

思路:论文题.

转载论文中的题解:

做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n) …

题目连接

题意：求所有不同的子串个数。

思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月02日 星期二 18时32分28秒
  4File Name :code/spoj/subst1.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring> …

hdu5787

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

思路:数位dp,dp[i][k1][k2][k3][k4]表示长度为i,前1位是k1,前2位是k2,前3位是k3,前4位是k4的方案数. 注意不允许前导0.2A

题目链接

题意：给出一个字符串，问所有不同的字串的个数。

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

poj3261

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

思路：后缀数组，然后再次用到了根据height数组对后缀进行分组的套路…二分判定合法性，对于当前的最长长度x,分组使得每组中的height[i]都大于等于x,所不同的是，判定变成了存在一个组，后缀的个数至少为k个（因为这样，就可以对于大于等于k个的后缀，同时取前x长度，得到的就是出现了至少k次且长度为x的前缀）1A,蛤蛤蛤

poj 1743

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

思路：求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。

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

思路：依然是后缀数组，在更新长度 的时候记录起始位置即可，1A。以及，发现多开了一个完全没有必要的数组w[],这次已删。

poj2774

题意：给出两个字符串，问最长的公共连续字串。

思路：后缀数组模板题。

具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 dc3算法的论文：SuffixArrays_dc3 这里不谈具体的后缀数组的学习内容，说说大概的学习过程。

hdu1280

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

思路：由于数据有限，想到计数排序。。。以及，m个可能刚好某个数据没有全部输出，要在while里判断一下。。

原文链接：链接

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

1874: [BeiJing2009 WinterCamp]取石子游戏

Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 726  Solved: 296 [Submit][Status][Discuss]

Description

小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。

cf429 b 题目链接 题意：

n*m个格子，每个格子有一个人value a[i][j]>0，连个人，一个从左上角到右下角，每次只能向下或者向右移动，一个从左下到右上，每次只能向上或者向右移动，现在要求两个人恰好相遇一次，相遇点的a不算数，问在满足这样的条件下使得两个人的a最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点）

hdu 2050题目链接

题意：n条折线。。最多能把平面分成几部分。。 思路：联想到m条直线，最多能把平面分成m*(m+1)/2+1部分。。

画图发现。。。 f[2*n-1]==g[n]。。

hdu 2049 题目链接 题意：n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子，不能重复，问恰好有m个汉子选错妹子的可能的方案数。

思路：从n个中选n-m个，然后做剩余m个错排即可。

。。。重新编译一次就可以了。。。orz