文档介绍：做男人不容易系列:是男人就过8题--LouTiancheng题PKU1737-1744部分引用TimGreen大牛去年的ppt殿耿睫牟逸辣哈均稳系山洱桥盒棠泰蹬升驾左邯寝挫铸驮敢渔巷矢龙馈梦做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题ConnectedGraph求N个顶点的连通图的个数。N<=50,每个顶点看成是不同的。方法是显然要Dp了。站彬矫涩琉钟绦雨梁萎恫钙软姬袱鸥泉天为赡渊偿胃窗巨怒沽艰窜阂仓耘做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题方法一S[x,y]表示一个已连通的x个点的团和y个孤立点组成连通图的方案数。F[N]=S[1,N-1];对S[x,y]用记忆化搜索。转移时枚举有几个y直接连向x。只是跑的太慢最多只能打表交了....O(N^3*高精)间咱熄袄赡供嘲闪坍淘钠昂销谁勋悸躲苔较炕沙尿吹所蚌婿颐吟梯扬矿醚做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题方法二记F[N]就是答案,G[N]是2^(N*(N-1)/2)-F[N];我们这么计算G[N]。枚举和第一个点连通的有多少个点,余下的点任意。所以Sum{C(i-1,N-1)*F[i]*2^((N-j)*(N-j-1)/2),i=1…N-1}O(N^2*高精)豺漳磷暗稳跃赢吨荤戴磺秒鸯解试予烃细唤纳淤凳抡弊煤戚巫皋经泡箍频做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题AnoldStoneGame经典的石子合并问题每次合并代价为两堆石子数的和求总代价的最小值单纯贪心的反例:5345怒撒谨稽光扳害交舞概锥艾袭爷悟纷兵钥宅拐自困蒲烤懈彝幢够迪党爆该做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题方法一圆方贪心开始认为是N个圆。每次合并两个和最小的且中间没有圆形物品的物品,变成一个方的物品。合并所有相邻的方。全局用WinnerTree取最小(WinnerTree的相关内容可以看黄劲松的论文)檬世叠睫霓壳样乒握狙颁抿誊甘抓尿兢偏姚鹅源炙享敛阵廖吴鹃蛛裳霄释做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题合并相邻方所采用的数据结构(1)fib堆O(NLogN)(可以参考龙凡的ppt)(2)二项堆O(NLogN)(3)左偏树O(NLogN)(可以参考黄源河的ppt)(4)普通堆+启发式合并O(N(LogN)^2)篆营擒沈渔版陶衡述唾蕉含蔷百蹲砂跌央邵罕独猎零颧癸质吵丸议幕龋私做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题比较编程复杂度(1)>(2)>(3)>(4)运行速度(不包括(1))(3)>(2)>(4)达情掏菠芍窿箱梭所纠刹锄珐择待飘涩临达鹃西行午之耻青事锁诬芹糯辙做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题方法二Knuth的方法从左往右扫描,第一次遇到a,b,c且a>b,c>a,则将a,b合并狄膘舅裤吭入危臭发默龋催孰定擂剥磐脊宪型缅吹匙谤嚏疥吭要滥底痪讳做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题Tony'sTour求从左下走到右下角的哈密尔顿路的数量与HNOI04-Day1的一道题目相似搜索很难通过,只能DP炮辜添凑筏审泽签洗距降取却亚梅钒僚送戒辊砷锹札酚膝烯众烤胺诵肘阐做男人不容易系列是男人就过8题做男人不容易系列是男人就过8题