清北学堂2012国庆NOIP课件——模型构建与全面分析试题.ppt

模型构建与全面分析试题 清华大学汪一宁antoniowyn OI中常用的数学模型 最小割最大流 最小费用流 匹配2 SATNIM游戏与SG函数Polya原理差分约束系统分数规划 思考方式一 思考方式二 速度限制 经典试题 一个城市 N个路口 M条道路每条道路可能有一个速度上限v 也可能没有 通过一条有速度限制的道路 驾驶员按照速度限制行驶 通过一条没有速度限制的道路 驾驶员按照原速行驶 求两个路口之间的最快驾驶方案 给定初速 N 200 v 500 知识补充 点边拆分 图论建模试题中时常需要对题面中给的 点 或者 边 在真正的模型中进行拆分 常见的情况有将一个顶点拆分为多个 以提供顶点之外的信息 例如到达这个顶点时的速度 价格 等等将一个顶点拆分为两个 以提供对经过这个顶点的网络流量的限制 常用于网络流试题中 将一条边拆分成多条 如用来实现凸函数最小费用流 解题思路 路口 顶点道路 边最快路径 最短路径如何处理无限速边 将每个顶点按照到达这个路口时的速度拆开 n v 有限速边 限速为v n v n v 无限速边 n v 翻硬币游戏 经典试题 有N枚硬币一字排开 有的正面朝上 有的反面朝上 两个玩家轮流操作 对每一次操作 该玩家先将一枚正面朝上的硬币翻转为反面朝上 然后 可选地 将该硬币左边的一枚硬币翻转状态 第一个不能操作的玩家输掉游戏 知识补充 NIM游戏 NIM游戏是一种经典的组合策略游戏 N堆石子 两个玩家轮流操作 每次可以从一堆石子中取出任意数量的石子 无法操作者失败 结论 所有堆中石子数的异或和不为0时先手胜 否则后手胜 将一个新游戏划归为NIM游戏是常见的解题策略 但更本质的方法是使用SG函数 解题思路 试题气息 NIM和问题每一枚正面朝上的硬币代表一堆石子 石子数量就是这枚硬币从左往右数的位置 玩家的操作 1 将一堆石子取光 2 从一堆石子中取出一部分 3 先从一堆石子中取出一部分 再从两堆石子中取出同样多的石子 点集最大斜率 经典试题 给出平面上N个点 求一条直线穿过其中至少两个点 并且该直线有最大的斜率 知识补充 分数规划 为求f x g x 的最大值先二分比值f x g x 设其为r然后判断是否存在x 使得f x rg x 解题思路 试题气息 求解一个分式函数最值 分数规划二分答案斜率k枚举每个点 x y 在判断是否存在 x y 使得Y y k x x 也就是y kx y kx也就是求y kx 的最大值 变换序列 NOI2009 定义距离函数D x y min x y N x y 找到一个排列a0 a1 aN 1 使得对所有i D i ai di 其中d0 dN 1为给定值 如果有多个解 输出字典序最小的 N 10 000 知识补充 2SAT问题 由N个布尔变量组成个公式 formula f 如果可以写成这样的形式 F t1 t2 tn且每个ti可以写成这样的形式 Ti x1Vnotx3V V not xm则称判定f是否可被满足的问题为m SAT问题 其中每一个ti称为一个clause 每一个xi 包含它之前出现的可选的非号 称为一个literal 2 SAT问题 F x1Vnotx2 x3Vx1 notx2Vnotx3 算法 图论模型 Nx1 Nx2 x2 x1 Nx3 x1 Nx1 x3 时间复杂度 基于BFS的实现 O nm 基于强联通分量的实现 O n m 注意 几乎所有其他的布尔表达式可满足问题都是NP Complete 知识补充 图匹配 图匹配一般图的最大匹配 复杂 二分图的最大匹配 匈牙利算法从一个未匹配的顶点开始 以BFS法寻找交错路 若交错路终止于另一个未匹配顶点 则修改交错路上所有匹配之后匹配容量 1若不存在交错路 则已经找到最大匹配 时间复杂度 O nm 解题思路 每个ai可以有两种选择 2 SATAi的两种不同选择代表一个变量的真假赋值 根据排列的性质 规定一些变量不能同时取一组赋值 问题 clauses的数目是不受限制的 最多可有n2个clauses 若用强连通分量算法 在保证字典序最小的前提下 时间复杂度将达到O n3 解题思路 每个ai只能取唯一值 匹配优势1 二分图中的边数为2n 远少于2 SAT模型中的clauses数目优势2 匈牙利算法中 改变一条匹配边 只需要O m 的时间就可以完成重新匹配的过程 全面分析试题 挖掘隐藏在试题描述背后的信息 对输入结构的限制 树 DAG 二分图 对输入规模的限制对解答结构的限制 红黑树计数 原创 红黑树是这样的排序二叉树 根节点和所有叶节点是黑色的 红色节点的孩子节点是黑色的 从任意节点到期每个叶子的所有路径上包含相同数目的黑节点 给出N 元素的数目 求有多少种不同的红黑树 假设元素各不相同 N 1000 解题思路 动态规划算法F n color dist 表示n个点的红黑树数目 并规定根节点颜色为color 叶子路径上黑节点数目为dist转移 枚举左子树所包含的点数复杂度O n3 是这样么 知识补充 所有规模为O logn 或更小的参数 严格平衡树的高度树链剖分算法中链的个数 NOI2008 按秩合并的检索树高度一个排列中上升子序列的期望长度随机点集的凸包上的点数 这个好像不是logn 但也很小 宁夏 原创试题 解题思路 要我们优化的是一个什么样的函数 怎么去掉讨厌的绝对值符号 在分类讨论之后 有没有更快的方法计算出每一个系数 KingdomPartitioning NEERC2007 有N个王国 每个王国有自己感兴趣的区域 由m个不想交的圆组成 不同王国的感兴趣区域可以重叠 给每个王国分配一个凸多边形 使得这个凸多边形中该王国感兴趣的区域的面积不少于它所感兴趣区域的总面积的1 N 给每个王国分配的凸多边形彼此不能相交 解题思路 用什么办法限制变化多端的凸多边形 试试狭长矩形纵坐标包含所有的圆 只考