资源描述：
《楼天成男人必做八题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、做男人不容易系列:是男人就过8题--LouTiancheng题PKU1737-1744部分引用TimGreen大牛去年的pptConnectedGraph求N个顶点的连通图的个数。N<=50,每个顶点看成是不同的。方法是显然要Dp了。方法一S[x,y]表示一个已连通的x个点的团和y个孤立点组成连通图的方案数。F[N]=S[1,N-1];对S[x,y]用记忆化搜索。转移时枚举有几个y直接连向x。只是跑的太慢最多只能打表交了....O(N^3*高精)方法二记F[N]就是答案,G[N]是2^(N*(N-1)/2)-F[N];我们这么计算G[N]。枚举和第一个点连通的有多少个点
2、,余下的点任意。所以Sum{C(i-1,N-1)*F[i]*2^((N-j)*(N-j-1)/2),i=1…N-1}O(N^2*高精)AnoldStoneGame经典的石子合并问题每次合并代价为两堆石子数的和求总代价的最小值单纯贪心的反例：5345方法一圆方贪心开始认为是N个圆。每次合并两个和最小的且中间没有圆形物品的物品，变成一个方的物品。合并所有相邻的方。全局用WinnerTree取最小（WinnerTree的相关内容可以看黄劲松的论文）合并相邻方所采用的数据结构（1）fib堆O(NLogN)（可以参考龙凡的ppt）（2）二项堆O(NLogN)（3）左偏树O(NLo
3、gN)（可以参考黄源河的ppt）（4）普通堆+启发式合并O(N(LogN)^2)比较编程复杂度（1）>（2）>（3）>（4）运行速度（不包括（1））（3）>（2）>（4）方法二Knuth的方法从左往右扫描，第一次遇到a,b,c且a>b,c>a，则将a,b合并Tony'sTour求从左下走到右下角的哈密尔顿路的数量与HNOI04－Day1的一道题目相似搜索很难通过，只能DPTimGreen大牛的解法状态压缩的Dp。状态是一行(或一列)的连通性(用最小表示)。如010122表示第2个和第4连通了,第5个和第6个连通了。第1个和第3个没有向下走。每个点的走法有6种(─│┐┌└
4、┘)然后一行行Dp下去(Search每个点的走法,有些烦)。中间因为不是所有的状态都是合法的,所以每一层的状态数不是很多。再一点要注意的是最后一行 起点和终点上都只能是(─│)连通性只能是10..001ANewStoneGame开始给出N堆石子,每一次可以选一堆石子取走至少一个,然后可以任意的将这一堆余下的任意多个分配到其它堆里。问两个人都使用最优策略的情况下,是不是先手胜。结论会输只有一种情况“N是偶数且每个数出现偶数次”证明方法证明有点繁,大致是这样。定义上面所说的输的状态全部属于T。定义所有不属于T的状态属于S。首先先证明对于T中一个状态执行一步后一定会属于S。再
5、证明对于S中的每一个状态一定有一种方法可以使它转移到T中。最后注意到全空这个输的状态属于T。O(1)Tree求一棵树中距离不超过给定值的点对数对于一个树，去掉一个结点，最分散的每颗子树分别求解，然后用O(NLogN)的方法合并结果。一般排序O(N(LogN)2)基数排序O(NLogN)Coins给出N种硬币和个数,问可以取到1->M中的多少个值。经典的01背包复杂度O(NMC)超时！下面介绍来自Lee.MaRS大牛笔记的两种可以AC的方法方法一将1...ci的coin看面1,2,4,..2x,ci-(2x+1-1)的组合。例如15个1与1248是等价的复杂度降为O(NM
6、logC)将多个bool压成int（Pascal32个bool压成longint，C＋＋直接使用bitset）方法二剩余类优化的动态规划算法状态仍然是F[i,j]表示用前i种钱币是否能拼出面值j。考虑在计算第i阶段时，面值为d[i]，数量为n[i]。从状态转移方程中，我们发现F[i,j]所依赖的所有状态，都属于模d[i]的一个剩余类[jmodd[i]]，即不同剩余类内的状态不相互影响。于是，我们可以将第i个阶段的状态按剩余类划分，每次只对一个剩余类的状态进行更新。复杂度O(NM)MusicalTheme给出一个数列，将数列相邻两项做差，形成新数列，求数列中的最长重复子串
7、（不可相交）方法一后缀数组+二分答案（后缀数组相关内容可以看许智磊的论文）假如二分得到答案L，如何知道它是可行的呢？因为对于排序后的后缀，Lcp(Suffix(List[i]),Suffix(List[i-1]))是所有与Suffix(List[i])的LCP值中最大的一个。因为Height[i]表示的是排序后后缀数组中第i个后缀和第i-1个后缀的LCP值。那么对于后缀数组中的一段L-R,若Height[L+1]~Height[R]全部大于等于L，那么就等价于第L到第R个后缀中任意两个后缀的LCP值都大于等于L。那么只要取这里面相隔最远的
