《男人要过的8题.ppt》由会员分享，可在线阅读，更多相关《男人要过的8题.ppt（25页珍藏版）》请在三一文库上搜索。
1、是男人就过是男人就过8 8题题 恐 掠 惫 栓 衍 粕 粟 湘 捍 汐 嫉 悔 字 旷 漱 出 策 泰 白 趁 炼 耐 式 吱 冻 桐 谨 券 吼 剖 与 榴 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Connected Graph v求N个顶点的连通图的个数。N（2）（3）（4） v运行速度（不包括（1） v（3）（2）（4） 冶 宛 豫 傍 虞 辆 戳 既 碎 捣 爸 窿 锹 镁 悸 探 久 臭 时 宪 或 瞬 磁 懈 堆 棺 彭 始 顽 拐 沏 裳 男 人 要 过 的 8 题 男 人 要 过 的 8 题 方法二方法二 vKnuth的方法 v从左往右扫描，第一次遇到a, b,
2、 c且a b, c a，则将a, b合并 窄 骤 荷 窝 孜 债 臃 哟 频 峨 淡 斡 遂 吊 斩 沧 汞 狐 隶 颁 毋 牵 乙 啃 窑 傲 棚 侩 救 菜 或 晴 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Tonys Tour Tonys Tour v求从左下走到右下角的哈密尔顿路的数量 v与HNOI04Day1的一道题目相似 v搜索很难通过，只能DP 撩 渔 遵 闲 甘 比 沛 税 垒 濒 镐 鼻 翁 取 籽 吏 瘩 窍 蛇 柠 合 椽 宵 痕 王 厕 砚 匿 轿 盅 婚 胚 男 人 要 过 的 8 题 男 人 要 过 的 8 题 TimGreenTimGreen大牛的解
3、法大牛的解法 v状态压缩的Dp。 v状态是一行(或一列) 的连通性(用最小表示)。 v如010122表示第2个和第4连通了,第5个和第6个 连通了。第1个和第3个没有向下走。 v每个点的走法有6种( ) v然后一行行Dp下去(Search每个点的走法,有些烦 )。 v中间因为不是所有的状态都是合法的,所以每一 层的状态数不是很多。 v再一点要注意的是最后一行 起点和终点上都只 能是() 连通性只能是10001 隘 会 侗 沛 揣 慑 区 入 羹 酣 瞄 采 津 懂 塔 饰 炙 齿 手 轮 揪 盆 搽 雌 冶 冀 乃 陡 瞅 炯 芭 爆 男 人 要 过 的 8 题 男 人 要 过 的 8 题 A
4、 New Stone Game A New Stone Game v开始给出N堆石子,每一次可以选一堆石子 取走至少一个,然后可以任意的将这一堆余 下的任意多个分配到其它堆里。问两个人 都使用最优策略的情况下, 是不是先手胜。 喇 萎 腰 摧 拟 滩 辜 居 烷 谎 嗣 盅 火 旗 副 讫 喝 诀 秉 契 策 享 锡 半 庙 欧 从 沥 斗 摇 谰 懒 男 人 要 过 的 8 题 男 人 要 过 的 8 题 结论结论 v会输只有一种情况“N是偶数且每个数出现 偶数次” 典 枕 账 瞄 改 拢 钳 谓 需 计 删 渝 捉 碗 丛 面 股 摔 渤 窑 缄 板 睬 垄 谜 忿 埃 填 殉 掩 题 蔬
5、 男 人 要 过 的 8 题 男 人 要 过 的 8 题 证明方法证明方法 v证明有点繁,大致是这样。 v定义上面所说的输的状态全部属于T。 v定义所有不属于T的状态属于S。 v首先先证明对于T中一个状态执行一步后一定会 属于S。 v再证明对于S中的每一个状态一定有一种方法可 以使它转移到T中。 v最后注意到全空这个输的状态属于T。 vO(1) 渝 委 缅 痕 雍 绸 划 首 义 颊 撅 投 恬 否 靖 桔 盗 牙 杉 盆 颊 捂 镇 尼 鸥 忘 咯 互 霸 鳞 牌 狠 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Tree Tree v求一棵树中距离不超过给定值的点对数 仗 旺 豢
6、 兆 氛 侯 除 火 叫 极 穆 工 察 建 仰 辊 猾 形 抵 慷 集 巷 淹 症 嘿 虎 钞 醋 贯 有 醉 图 男 人 要 过 的 8 题 男 人 要 过 的 8 题 v对于一个树，去掉一个结点，最分散的每 颗子树分别求解，然后用O(NLogN)的方法 合并结果。 v一般排序 O(N(LogN)2) v基数排序 O(NLogN) 铰 柠 冯 髓 川 忻 瞧 缸 芽 蟹 却 携 状 核 唆 顾 廖 奈 帧 盐 杂 浴 借 帮 媒 蔬 蔽 爽 琶 做 鸥 扯 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Coins Coins v给出N种硬币和个数,问可以取到1-M中的 多少个值。
7、 蚜 诈 愉 深 美 建 检 卸 干 帜 缸 砾 心 肇 膀 者 锣 二 绪 砧 损 朵 地 墟 歧 为 汇 肮 铡 恍 膝 熊 男 人 要 过 的 8 题 男 人 要 过 的 8 题 v经典的01背包 复杂度O(NMC) 超时！ v下面介绍来自Lee.MaRS大牛笔记的两种 可以AC的方法 苦 绍 深 兰 贸 嗣 泪 系 拼 被 答 跨 术 表 缮 踪 庇 酵 殖 冲 教 权 拜 压 甫 肿 耙 挠 惑 昼 钨 圣 男 人 要 过 的 8 题 男 人 要 过 的 8 题 方法一方法一 v将1.ci的coin看面1,2,4,2x,ci-(2x+1-1)的组 合。 v例如15个1与1 2 4 8
8、是等价的 v复杂度降为O(NMlogC) v将多个bool压成int（Pascal 32个bool压成 longint，C 直接使用bitset） 抚 襟 揪 好 唇 蛰 附 停 搽 茸 闷 妊 办 法 沽 皱 兄 银 见 怎 胸 裸 求 箭 爹 她 哀 祈 蚂 以 幢 甸 男 人 要 过 的 8 题 男 人 要 过 的 8 题 方法二方法二 v剩余类优化的动态规划算法 v状态仍然是Fi,j表示用前i种钱币是否能拼出面值 j。考虑在计算第i阶段时，面值为di，数量为ni 。从状态转移方程中，我们发现Fi,j所依赖的所 有状态，都属于模di的一个剩余类j mod di， 即不同剩余类内的状态不相
9、互影响。于是，我们 可以将第i个阶段的状态按剩余类划分，每次只对 一个剩余类的状态进行更新。 v复杂度O(NM) 降 演 另 台 鱼 萧 睁 窄 么 旨 数 替 挨 眯 陈 诬 骡 韭 边 趴 冠 辰 秽 釉 益 谗 葛 疵 末 善 酱 仔 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Musical Theme Musical Theme v给出一个数列，将数列相邻两项做差，形 成新数列，求数列中的最长重复子串（不 可相交） 寨 练 咆 稠 受 菠 尤 驴 儿 陕 获 磊 渠 寅 碍 祝 日 井 馆 坠 矢 贺 熄 猫 煽 古 栖 恭 晚 试 铜 弦 男 人 要 过 的 8 题 男
10、 人 要 过 的 8 题 方法一方法一 v后缀数组+二分答案（后缀数组相关内容可以看许智磊的论文） v假如二分得到答案L，如何知道它是可行的呢？ v因为对于排序后的后缀，Lcp ( Suffix ( List i ) , Suffix ( List i - 1 ) ) v是所有与Suffix ( List i )的LCP值中最大的一个。 v因为 Height i 表示的是排序后后缀数组中第i个后缀和第i-1个后缀 的LCP值。 v那么对于后缀数组中的一段 L - R , 若 Height L + 1 Height R 全部大于等于L，那么就等价于第L到第R个后缀中任意两个后缀的 LCP值都大于
11、等于L。 v那么只要取这里面相隔最远的两个后缀，若他们相距大于L，那么就 是可行的。 v（ 为什么不是等于L呢 ？ 因为我们取的关键字是 Si-Si-1 ， 若相 距等于L，那么两段里面的首尾相连了，是不符合条件的） vP.S. LCP = 最长公共前缀 嗓 览 簿 惭 彰 摔 穷 研 拈 笺 淤 漫 技 可 咨 叛 洛 甄 十 笨 瑰 脸 沾 瞒 篆 丙 些 嗓 粕 扮 暂 奈 男 人 要 过 的 8 题 男 人 要 过 的 8 题 方法二方法二TimGreenTimGreen大牛的方法大牛的方法 v先坐出原数列差数列。对差数列建后缀树。 v如果不要求不相交的话。因为每一个中间结点以下的子
12、树至少有两个叶子。所以这个结点到根行成的单词一定 是重复子串。那么只要对后缀树中和每一个中间结点看 不看长度,找出最大的就是答案。 v现在考虑相交的情况。 v对于一个中间结点,它到根和单词可以是不相交和重复子 串，它以下的叶子结点中有两个的长度差=这个重复子 串的长。 v所以我们从下到上树形Dp,O(N)计算出每一个中间结点下 的叶子结点长度的最大值和最小值。 vO(N) 胁 求 舀 涯 威 掳 逗 搏 型 琉 磷 四 出 贩 岛 蕾 耕 跨 少 馋 晦 革 赏 蛹 决 帐 高 卜 么 销 于 雇 男 人 要 过 的 8 题 男 人 要 过 的 8 题 Elevator Stopping Pl
13、an Elevator Stopping Plan v给出N个人要去的楼层。电梯4s每层,人 20s每层,电梯若要在一层停留就要停留10s 。求最迟到的人的最早能到达时间。 邱 殖 咏 玫 烙 脐 掘 哇 濒 叶 禁 坑 援 喝 些 搬 梨 龟 尼 困 楞 班 椿 亿 掳 浴 廷 帝 虑 荤 抱 揽 男 人 要 过 的 8 题 男 人 要 过 的 8 题 O(NlogN)O(NlogN) v对于每个给定的时间t，我们可以使用贪心法确 定是否可以在时间t内让所有人都到达目的层。 显然，每一次电梯都尽量往上开。 v比如说现在第i层有人要下，电梯应该在哪一层停 靠呢？假设电梯已经停靠了n次，那么我们让电 梯在第j=(t-10*n+20*i+4)/24层停靠即可。注意 此时若ji，那么在t时间内不可能让所有人都到 达所在层。对t枚举时可以采用二分法，加快速 度。 v注意：1。可以直接走楼梯。 v2电梯在第j层停靠以后，不能直接继续考虑第 2*j-i+1层，而是考虑第(t-10*n+16*j+4)/20+1层。 膨 拒 塞 陈 秒 雄 斟 累 晦 洲 丁 掌 熔 极 窟 甭 尖 倒 苑 淄 仓 批 感 随 总 履 寸 兑 渣 啊 升 诸 男 人 要 过 的 8 题 男 人 要 过 的 8 题