男人要过的8题.ppt
《男人要过的8题.ppt》由会员分享,可在线阅读,更多相关《男人要过的8题.ppt(25页珍藏版)》请在三一文库上搜索。
1、是男人就过8题,Connected Graph,求N个顶点的连通图的个数。N=50,每个顶点看成是不同的。 方法是显然要Dp了。,方法一,Sx, y表示一个已连通的x个点的团和y个孤立点组成连通图的方案数。 FN = S1, N - 1; 对Sx, y用记忆化搜索。转移时枚举有几个y直接连向x。 只是跑的太慢最多只能打表交了 O(N3*高精),方法二,记FN就是答案,GN是2(N*(N-1)/2)-FN; 我们这么计算GN。枚举和第一个点连通的有多少个点,余下的点任意。 所以SumC(i-1,N-1)*Fi*2(N-j)*(N-j-1)/2),i=1N-1 O(N2*高精),An old St
2、one Game,经典的石子合并问题 每次合并代价为两堆石子数的和 求总代价的最小值 单纯贪心的反例:5 3 4 5,方法一,圆方贪心 开始认为是N个圆。 每次合并两个和最小的且中间没有圆形物品的物品,变成一个方的物品。 合并所有相邻的方。 全局用Winner Tree取最小(Winner Tree的相关内容可以看黄劲松的论文),合并相邻方所采用的数据结构,(1)fib堆 O(NLogN) (可以参考龙凡的ppt) (2)二项堆 O(NLogN) (3)左偏树 O(NLogN) (可以参考黄源河的ppt) (4)普通堆+启发式合并 O(N(LogN)2),比较,编程复杂度(1)(2)(3)(4
3、) 运行速度(不包括(1) (3)(2)(4),方法二,Knuth的方法 从左往右扫描,第一次遇到a, b, c且a b, c a,则将a, b合并,Tonys Tour,求从左下走到右下角的哈密尔顿路的数量 与HNOI04Day1的一道题目相似 搜索很难通过,只能DP,TimGreen大牛的解法,状态压缩的Dp。 状态是一行(或一列) 的连通性(用最小表示)。 如010122表示第2个和第4连通了,第5个和第6个连通了。第1个和第3个没有向下走。 每个点的走法有6种( ) 然后一行行Dp下去(Search每个点的走法,有些烦)。 中间因为不是所有的状态都是合法的,所以每一层的状态数不是很多。
4、 再一点要注意的是最后一行 起点和终点上都只能是() 连通性只能是10001,A New Stone Game,开始给出N堆石子,每一次可以选一堆石子取走至少一个,然后可以任意的将这一堆余下的任意多个分配到其它堆里。问两个人都使用最优策略的情况下, 是不是先手胜。,结论,会输只有一种情况“N是偶数且每个数出现偶数次”,证明方法,证明有点繁,大致是这样。 定义上面所说的输的状态全部属于T。 定义所有不属于T的状态属于S。 首先先证明对于T中一个状态执行一步后一定会属于S。 再证明对于S中的每一个状态一定有一种方法可以使它转移到T中。 最后注意到全空这个输的状态属于T。 O(1),Tree,求一棵
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 男人
链接地址:https://www.31doc.com/p-3067263.html