楼天成男人必做八题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,做男人不容易系列,:,是男人就过,8,题,-,LouTiancheng,题,PKU 1737-1744,部分引用,TimGreen,大牛去年的,ppt,Connected Graph,求,N,个顶点的连通图的个数。,N,（,2,）,（,3,）,（,4,）,运行速度（不包括（,1,）,（,3,）,（,2,）,（,4,）,方法二,Knuth,的方法,从左往右扫描，第一次遇到,a,b,c,且,a b,c a,，则将,a,b,合并,Tonys Tour,求从左下走到右下角的哈密尔顿路的数量,与,HNOI04,Day1,的一道题目相似,搜索很难通过，只能,DP,TimGreen,大牛的解法,状态压缩的,Dp,。,状态是一行,(,或一列,),的连通性,(,用最小表示,),。,如,010122,表示第,2,个和第,4,连通了,第,5,个和第,6,个连通了。第,1,个和第,3,个没有向下走。,每个点的走法有,6,种,(),然后一行行,Dp,下去,(Search,每个点的走法,有些烦,),。,中间因为不是所有的状态都是合法的,所以每一层的状态数不是很多。,再一点要注意的是最后一行起点和终点上都只能是,(),连通性只能是,10.001,A New Stone Game,开始给出,N,堆石子,每一次可以选一堆石子取走至少一个,然后可以任意的将这一堆余下的任意多个分配到其它堆里。问两个人都使用最优策略的情况下,是不是先手胜。,结论,会输只有一种情况“,N,是偶数且每个数出现偶数次”,证明方法,证明有点繁,大致是这样。,定义上面所说的输的状态全部属于,T,。,定义所有不属于,T,的状态属于,S,。,首先先证明对于,T,中一个状态执行一步后一定会属于,S,。,再证明对于,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,.2,x,ci-(2,x+1,-1),的组合。,例如,15,个,1,与,1 2 4 8,是等价的,复杂度降为,O(NMlogC,),将多个,bool,压成,int,（,Pascal 32,个,bool,压成,longint,，,C,直接使用,bitset,）,方法二,剩余类优化的动态规划算法,状态仍然是,Fi,j,表示用前,i,种钱币是否能拼出面值,j,。考虑在计算第,i,阶段时，面值为,di,，数量为,ni,。从状态转移方程中，我们发现,Fi,j,所依赖的所有状态，都属于模,di,的一个剩余类,j mod,di,，即不同剩余类内的状态不相互影响。于是，我们可以将第,i,个阶段的状态按剩余类划分，每次只对一个剩余类的状态进行更新。,复杂度,O(NM),Musical Theme,给出一个数列，将数列相邻两项做差，形成新数列，求数列中的最长重复子串（不可相交）,方法一,后缀数组,+,二分答案（后缀数组相关内容可以看许智磊的论文）,假如二分得到答案,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,。,那么只要取这里面相隔最远的两个后缀，若他们相距大于,L,，那么就是可行的。,（为什么不是等于,L,呢？因为我们取的关键字是,Si-Si-1,，若相距等于,L,，那么两段里面的首尾相连了，是不符合条件的）,P.S.LCP=,最长公共前缀,方法二,TimGreen,大牛的方法,先坐出原数列差数列。对差数列建后缀树。,如果不要求不相交的话。因为每一个中间结点以下的子树至少有两个叶子。所以这个结点到根行成的单词一定是重复子串。那么只要对后缀树中和每一个中间结点看不看长度,找出最大的就是答案。,现在考虑相交的情况。,对于一个中间结点,它到根和单词可以是不相交和重复子串，它以下的叶子结点中有两个的长度差,=,这个重复子串的长。,所以我们从下到上树形,Dp,O(N,),计算出每一个中间结点下的叶子结点长度的最大值和最小值。,O(N),Elevator Stopping Plan,给出,N,个人要去的楼层。电梯,4s,每层,人,20s,每层,电梯若要在一层停留就要停留,10s,。求最迟到的人的最早能到达时间。,O(NlogN,),对于每个给定的时间,t,，我们可以使用贪心法确定是否可以在时间,t,内让所有人都到达目的层。显然，每一次电梯都尽量往上开。,比如说现在第,i,层有人要下，电梯应该在哪一层停靠呢？假设电梯已经停靠了,n,次，那么我们让电梯在第,j=(t-10*n+20*i+4)/24,层停靠即可。注意此时若,ji,，那么在,t,时间内不可能让所有人都到达所在层。对,t,枚举时可以采用二分法，加快速度。,注意：,1,。可以直接走楼梯。,2,电梯在第,j,层停靠以后，不能直接继续考虑第,2*j-i+1,层，而是考虑第,(t-10*n+16*j+4)/20+1,层。,