111qqz

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[]，这次已删。

poj 2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。 具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 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最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点）