杨俊 二分策略在信息学竞赛中的应用.pptVIP

WinterCamp 2005 二分策略在信息学竞赛中的应用 华东师大二附中 杨俊 二分策略 来源 一个很简单的想法——在最坏情况下排除尽可能多的干扰，以尽可能快地求得目标 效率 高！对信息的充分利用，尽可能去除冗余 ，减少了不必要计算 应用 广！ 三种应用类型 类型一：二分查找 ——应用于一般有序序列 类型二：二分枚举 ——应用于退化了的有序序列 类型三：二分有哪些信誉好的足球投注网站 ——应用于无序序列 类型一：二分查找 ——应用于一般有序序列 申明：“有序序列”，仅包含两层意思： 第一，它是一个序列，一维的 第二，该序列是有序的，即序列中的任意两个元 素都是可以比较的，也就是拥有我们平时 所说的全序关系 类型一：二分查找 ——应用于一般有序序列 二分查找的一般实现过程： （1）确定查找范围 （2）选择基准元素 （3）关键字比较，确定更精确的范围 （4）判断结果，如不够精确，转至（2） 例一：顺序统计问题 [问题描述] 给定一个由n个不同的数组成的集合S，求其中第i小的元素。例如： S={ 3, 7, 2, 6, 8, 1, 5 }，i=4 Answer=5 问题的一般解法 二分查找的过程： （1）确定待查找元素在S中 （2）在n个元素中随机取出一个记为x，将x作基准 （3）设S中比元素x小的有p个 （4）如果找出x，输出；否则转至（2） 因为x是随机选出的，由简单的概率分析，可得算法的复杂度期望值为O(n)。 小结 举这个例子，是想说明两点： 第一，二分查找 == logn 第二，二分查找 == 平均 类型二：二分枚举 ——应用于退化了的有序序列 与类型一中的二分查找相比，最大的区别在于这里的二分在判断选择哪一个部分递归调用时没有了比较运算*。 例二：BTP职业网球赛 [问题描述] 初步分析 由于N很大，猜想可以通过贪心方法解决。 K+1?1 K+2?2 … … 2K?K 3K+1?2K+1 … … … … 初步分析 但我们很容易找到反例，例如：N=8, K=2 但最优解为6。 解决方法：枚举！ 性质：隐含的有序性 如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。 证明： 情况一：Y被Z≠X击败 性质：隐含的有序性 如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。 证明： 情况二：Y被X击败 问题的解决 于是，我们可以二分枚举获胜的X。 知道了X，能否很快构造出对战方式？ 可以证明这样贪心是正确的。 如果利用静态排序二叉树，整个问题可以在O(Nlog2N)时间完成。 小结 算法的根本—— 在一个隐含的退化了的有序序列中进行二 分查找 0 0 0 0 0 0 0 0 1 1 1 1 1 1 XAns X≥Ans 我们所寻找的—— 两种值的分界点。 小结 应用这类二分枚举的最优性问题近来很是热门（如NOI2003树的划分），而且这类试题很容易诱导选手直接采用动态规划或是贪心算法，而走入死胡同。 所以，今后我们在考虑最优性问题时，应当注意问题是否隐含了一个有序的01序列，它是否可以用二分枚举将最优性问题转化为可行性问题。切记！“退一步海阔天空”。 类型三：二分有哪些信誉好的足球投注网站 ——应用于无序序列 例三：推销员的旅行 [问题转述] 这是一个交互式问题： 在一个未知的竞赛图（即有N顶点，两点间恰只含一条边的有向图）中，通过不断询问任意两点之间边的方向，寻找一条哈密尔顿路。目标是询问次数尽可能少。 思考 . . . 初步分析 为了避免询问的盲目性，我们尝试使用增量法逐步扩展序列。 我们先任意询问两个点 不妨设询问结果是1到2有边，于是，我们就得到一条长度为1的线路。 初步分析 假设我们已设计了一条含有前i个点、长度为i-1的线路A1?A2?…?Ai，我们希望再加入点i+1，将其变成长度为i的线路。 进一步分析 这样的询问会不会问到底也没法插入i+1？ 不会！因为i+1有边到Ai。 由此，我们得到了一种询问方法，但最坏情况下总的询问次数可能是O(N2)的。 二分有哪些信誉好的足球投注网站的使用 由于对每个点Ak(1≤k≤i)，要么Ak?i+1，要么i+1?Ak。且已知A1?i+1，i+1?Ai。因此，我们可以用二分有哪些信誉好的足球投注网站来寻找Ak，使i+1可以插入Ak与Ak+1之间。 这样，我们所需要的询问次数仅为O(nlogn)。 小结 算法的根本—— 在一个无序的01序列中进行二分查找 0 0 1 0 1 1 1 0 0 1 1 1 我们所寻找的—— 一个特殊的子串‘01’