当前位置:首页 >> 学科竞赛 >> 清北学堂2012国庆NOIP课件——试题选讲

清北学堂2012国庆NOIP课件——试题选讲


清华大学 交叉信息研究院 吴翼

?

?

要求 S[1…N] ? (0…0) 限制
? S[1…k-1]为0,S[k]为1,可以改变S[k+1]的状态

?

要求步数

?

如何分析?
? 类似Hanoi To

wer问题的逆向思考

?

从后向前考虑最后一个1何时发生变化?
? S[1…N]?(0…011)?(0…010)?(000…0)

?

分阶段考虑
? S[1…N-1]?(0…01) 一个规模为N-1的子问题 ? S[N]?0 一次简单移动 ? (0…010)?(0…0) 规模为N-1的另一个子问题

?

两个问题
? F[N] 表示 S[1…N] 变成 (0…01)的步数 ? G[N] 表示 (0…01) 变成 (0…0)的步数

?

考虑 F[N]
? S[N]=1? ? S[N]=0? N-1的子问题:S[1…N-1]?(0…01)?(0…0) ? F[N-1]+1+G[N-1]

?

考虑 G[N]
? (0…01)?(0…11)?(0…10)?(0…00) ? N-1的子问题: (0…00)?(0…01) ? N-1的子问题:G[N-1]

?

?

新的问题: T[N] (0…00)?(0...01) 考虑 T[N]
? (0…00)?(0…10)?(0…11)?(0…01) ? 类比 G[N]: T[N]=G[N]

?

综合:
? ? ? ? G[N]=2G[N-1]+1=2N-1 if S[N]=0: F[N]=F[N-1]+1+G[N-1] If S[N]=1: ? Similar Subproblem

?

归纳如何思考递推类问题?状态表示?

?

?
?

N个点的树上有K个蚂蚁,H个瓢虫 每次蚂蚁向瓢虫移动 模拟蚂蚁的移动 相当于H个测试点,每个测试点需要尽量快的模拟 蚂蚁的移动

?

?
?

Bottleneck: 不能朴素的一步一步模拟 Key Problem: 蚂蚁需要最终自己在哪里

?

?
?

一个很自然的过程,结合生活直觉 Basic Problem: 每次哪些蚂蚁会移动? 何时会停止移动?
? Key Point: 看到有人挡道就会停止

?

Note: 总是距离最近的蚂蚁进行移动
? 如果除去KP,如何计算?

?

考虑KP
? 必要条件:最后有蚂蚁留下的点上一定是距离最近的蚂蚁 ? 深入:怎样的结点最后没有蚂蚁留下? ? 从顶向下考虑问题!

?

程序实现

?

反质数定义:A是反质数当且仅当其约数个数多余 任意一个比A小的整数的约数个数 求比N小的反质数 N<=2 * 109

?

?

?

规模很大?
? 直觉:反质数是很少的

?

如何成为反质数?
? 如何计算约数个数? ? A=P1a1P2a2… div(A)=(a1+1)*(a2+2)*… ? Div(A)与a1,a2…的顺序无关,与P1,P2…无关!

?

结论
? 目标:div(A)不变,A尽量小 ? 必要条件:P1,P2…尽量小,a1,a2…递减

?

搜索
? 规模?

?

?

给一个随机数生成算法,生成N个空间的点 求最近点对

?

Note: 点的分布是随机的
? Why? ? 其实也没那么“随机”……

?

Simple Solution:搜索剪枝
? Possible way: 按照x排序,挑一些求出较优解,只挑x差 不超出当前最优解的点作为候选检查 ? ? 同样适用于平面最近点对

?

从平面最近点对谈起?

?

?

利用随机的性质处理平面最近点对 一个利用均匀分布的思路
? 将平面均匀分割成一些小方块,每个小方块里应该点很少 ? 一个分割的方法:√N * √N ? Why?

?

如果一个小方块内至少有两个点,那么最优点对要 么在一个块内,要么在相邻块内
? Why? ? 如何保证? ? 推广?

?

不考虑随机性?

?

一个经典的分治算法
? 分治算法的基本框架:类比快速排序,归并排序 ? 先分,再合并

?

如何应用到最近点对问题
? 分割点集——easy ? 合并——How? 问题是否简化?

?

难点:一个点在左半平面,一个点在右半平面
? 这样的情况会出现很多么? ? Why? ? 如何分析?

?

平面最近点对的分治算法
? 考虑点集S ? 按照x坐标将S分割为S1和S2,并分别递归处理,综合两 部分的解,得到当前最优解ans ? 取出距离分割线x坐标差不超过ans的点,按照y排序 ? 对于每个点,向后检查8个点,并更新ans

?

为什么是8?
? 不放心怎么办?

?

拓展?
? D维空间? ? 复杂度的增长?

?

?

给一棵带权树 求树上最长带权路径

?

考虑一般的最长路径问题
? 动态规划算法? ? 树上DP一个可以拓展的小trick——if we have time

?

可否套用原有模型?
? Why?

?

XOR的性质
? 可加性 ? (A+C)+(B+C)=(A+B)

?

如何应用到树上?
? 如何计算树上两点间xor距离? ? 一些对比——可加性是重要的!Max?

?

算法:
? 任意选根,找出任意点u距离跟的xor距离D[u] ? x到y距离即为:D[x] xor D[y] ? 目标:对于任意D[x],找出xor值最大的D[y]

?

如何找出Xor最大的?
? ? ? ? 位运算的特点:按位从高到低考虑 最高位是否存能为1?这些被选里面能否第二位也计算得1? 如何组织数据? 一个按字符查找串的数据结构:Trie

?

拓展和启发?
? 给定A1…AN,求一个子集使得XOR最大 ? 图上两点最大xor路径?

?

?
?

给定4×7的棋盘,其中有一些给定位置的是山峰 将1~N*M的数字填入棋盘 求满足给定山峰位置限制的方案数

?

搜索的可行性
? 搜索的最坏情况是(NM)! ? 可行的剪枝:考虑山峰位置 ? Key Point: 山峰周围的一圈位置

?

? ?

Idea: 确定山峰周围的一圈位置放什么,然后其余 位置只要算阶乘就可以 Problem: 可能出现多余的山峰? Relaxation: 容斥原理
? 恰好k个位置是山峰?Σ至少某些位置是山峰 ? 复杂度?

? ?

我们并不需要知道山峰周围到底放了什么数,只要 保证比山峰小 如何保证? Note
? 从大到小顺次放置! ? Relaxation: 周围比山峰小?山峰放的时候周围还没放 ? 山峰放置之前,山峰周围的格子一定是空的,不能放数 ? 山峰放置之后,山峰周围的格子没有任何限制

?

?

Key Point: 每一个山峰是否放置
? 顺次放置:放没有限制的地方,还是放置一个山峰

?

新的搜索方法:2选1 O(2N)
? 如何记数?

?

更直接的方法——动态规划(记忆化搜索)
? 需要的信息1:从大到小放置了多少个数 ? 需要的信息2:每一个山峰是否被放置 ? 状态:F(k,S),表示已经放置了k个数,集合S中的山峰已 经被放置

? ? ?

程序实现与细节? 计算量? 如何从搜索,思考发现本质?与动态规划的联系?

?

?

?

给定一个N个格子的圆盘,以及上面已经写好的N 个数字 一共进行K次操作,每次操作,每一个格子上的数 字更新为与其距离不超过d的格子上的数的和 问最后每一个格子上的数字的值

?

?
? ? ? ? ?

一个直接而朴素的迭代过程 E.G. d = 1 N = 4 F’[1]=F[1]+F[2] +F[4] F’[2]=F[1]+F[2]+F[3] F’[3]= F[2]+F[3]+F[4] F’[4]=F[1] +F[3]+F[4] 写成矩阵形式
? 什么是矩阵?

?

矩阵简单介绍
? 表示线性映射,线性代数的重要概念 ? 可以用作递推运算的表示 ? 满足结合律 (AB)C=A(BC)

? ?

目标:F’=AkF 如何计算Ak?
? ? ? ? 对于一个整数如何计算幂次? Pow(a,n)=pow(a,n/2)2 *a if a is odd 一个简单的非递归写法 求出n的2进制表示,不断平方a,按照2进制表示将a的2 整次幂累乘到答案

?

复杂度分析
? 矩阵乘法的复杂度 O(N3) 总复杂度 O(N3log k)

?

矩阵的性质——循环矩阵
? 每一行一定是循环等价的! ? 只要知道一行的信息 ? 可以恢复整个矩阵的信息 O(N2)

?

一个直观的理解
? 快速幂:倍增的计算F’ ? 线性性:F’[k]=Σ ai * F[i] ? 对称性:F’[k+d]= Σ ai * F[i+d]

?

推广?

?

?

?

?

简单起见我们把每个数字都减一并简化题意如下 给定两个非负数列A和B,每次可以从数列尾部连续 取非空的若干个数 假设A取出的数的和是K1,B是K2,那么得分就是 K1*K2 要求把A和B同时取空,并且使得总得分最小

?

最基本的动态规划算法
? F[i][j]表示A还剩前i个数,B还剩前j个数能取得的最小分数 ? F[i][j]=min{F[x][y]+(S[i]-S[x])(S[j]-S[y])}

?

直接的优化
? (a+b)(c+d)>ac+bd ? 每次一定对于某数列,我们只取一个数 ? 复杂度 O(N3)

?

简化一下递推式:我们以枚举x为例
? F[i][j]=min{F[x][j-1]+(S[i]-S[x])A[j]} ? F[i][j]=S[i]A[j]+min{F[x][j-1]-A[j]S[x]} ? Simplified: G[i]=V[i]+min{G[x]-S[x]*const}

?

一个单调性的结论
? ? ? ? 设Index[i][j]表示F[i][j]对应的x 单调性:index[i][j]>=index[i-1][j] Why? 能猜么?

?

数学上的理由!
? G[i]=V[i]+min{G[x]-S[x]*const} ? KP: Min{G[x]-S[x]*const | x < i} ? G[x]-S[x]*const ? 一次函数,于x=const出的值

?

结论
? Index[i][j]=index[i-1][j] or i ? 推广??Const与i有关?

?

?

给定N个正方形,依次按照与x轴45度角向左平移 到不能移动为止 问最后哪些正方形可以被从上到下看见

?

N<=50

?

规模很小,简单的模拟 具体的问题:
? 怎样可以被看见? ? 考虑两个正方形,右侧的正方形可以移动到什么位置?

?

?

简单说一些实数的问题
? 实数的表示 ? 为什么要eps? ? 根号是怎么计算的?

?

?
?

给定若干形如Si(x)=ax2+bx+c的二次函数 F(x)=max{Si(x)} 求min{F(x)}

?

?

Problem: 连续函数 直观的思想:数形结合
? F(x)一定是由若干段二次函数拼接而成,每一段一定属于 某一个二次函数 ? 对于每一个二次函数,求出所有交点,分段,判断每一段 是否在F(x)上 ? 复杂度 O(N3) ? 求交点并分段的意义?——离散化

?

推广:连续曲线的一般性处理方法
? 多边形,圆,求并的轮廓,面积

?

求min的一般性放缩方法
? 二分答案:对于假设的答案y,判断是否不超过最小值 ? 和容斥原理的类比?

?

?

问题:假设答案是y,是否小于最小值? 观察F(x)函数的性质
? 最大?存在 ? 对于任何一个点x,都存在一个i,满足Si(x)>=y

?

如何实现?
? 离散化?求交点? ? 可行:对于一个二次函数与水平直线求交点 ? 每一个二次函数至多在两个x的区间上方位于直线之上

?

区间求并
? 将2次函数映射到一个直线上 ? 1维区间上求并 ? 如果所有区间可以覆盖整个实数区间,则说明y不超过当 前最小值

? ?

如何实现? 细节的处理
? 实数如何二分? ? 实数边界的处理?负无穷? ? 2次函数退化成1次函数

?

二分的推广?EG. 最小比率生成树

?

?
? ? ? ?

N个依次排列的怪兽,血量依次为mi 可以发射火力为p的火球攻击第i个怪兽 i左侧的怪兽j会受到溅射伤害 伤害为 max{0, p-(i-j)*(i-j)} 可以发射k次火球 问最少p需要多少才能够消灭所有怪兽

?

又一个最小值问题
? 可否套用二分方法?Why?

?

?

问题:假设当前的火力为p,判断是否可以杀死所 有怪兽 Key Point: 溅射只能向左溅射
? 那最右边的怪兽呢? ? 次右边的怪兽呢?

?

一个贪心的想法
? 朴素模拟的时间复杂度O(N2) ? 总复杂度 O(N2LogC) 如何快速模拟?

?

求[x,y]之间“杠杆数”的个数

?

Bottleneck: 每次向左计算溅射伤害
? 能否“积累传递的伤害” ? 目标:只向左移动,依次考虑每一个怪兽

?

考虑溅射函数的性质
? ? ? ? ? ? ? 二次函数! F(j)=max{0, p-(i-j)*(i-j)} F(j)=max{0,p-i2+2ij-j2} 二次函数的叠加?二次函数 Note: 0的问题? 维护二次函数,计算出每一个二次函数在什么位置消除 实现细节?数据结构?

?

区间可减性!
? F[x,y]=F[1,y]-F[1,x-1] ? 不可减? ? 思考题:Super Lucky Number
? 如果一个数只有4或者7组成,称为Lucky Number ? 给定区间[x,y] ? 如果一个[x,y]中的Lucky number 按照数位翻转后还是在 [x,y]中,那么就是Super Lucky Number ? 求Super Lucky Number 个数 ? 难度较大,欢迎思考 ?

?

分析杠杆数的特点
? 多个杠杆怎么办么? ? 很幸运你不需要考虑这个问题 ? ? 为什么?

?

新的问题
? ? ? ? 枚举杠杆的位置 求[1,x]中,以第k位为杠杆的,杠杆数的个数 一旦杠杆确定,每一个位置的权重就确定了 求(a1,a2,…)<=x,满足a1w1+a2w2+…=0

?

经典的计数问题

?

动态规划
? Note 1:需要记录信息判断数是否比x小 ? Note 2:需要记录休息判断带权和是否为0 ? Note 3:从高到低依次考虑

?

设立状态
? F[i][S][c] 表示当前填写到第i位,和为S,前i位与x比较的 大小情况(小于或者等于) ? 信息是否足够?C为什么不可能是大于?

?

如何转移
? 向后更新! ? 记忆化搜索

?

实现细节
? 记忆化搜索与递推的区别 ? 记忆化搜索与搜索的联系

?

?

时间复杂度? 一个简单的拓展
? LIS-k Number ? 对于一个数,如果存在一段长度至少为k的连续的不下降 数字,则称这个数是LIS-k Number ? 给定[X,Y],去区间内LIA-k Number的个数


更多相关文档:

清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告

清北学堂2012国庆NOIP模拟试题清北学堂2012国庆NOIP模拟试题隐藏>> NOIP2012 模拟赛 解题报告 Problem #1: 最近点对(Close) Description 求空间 N 个点之间最近点...

清北学堂08国庆免费赠送试题

清北学堂2012国庆NOIP课件... 27页 2财富值 清北学堂2012国庆NOIP模拟... 4...国庆学员辅助 学员辅助试 清北学堂 08 国庆学员辅助试题清北学堂教研部提供 上传...

清北学堂NOIP2010模拟试题与详细解析(13)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...清北学堂NOIP2010模拟试题与详细解析(13)_IT/计算机...防护伞【题目描述】 据说 2012 的灾难和太阳黑子的...

NOIP清北学堂11.13模拟赛题目题解

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机...清北学堂2012国庆NOIP模拟... 3页 2财富值 noip2010模拟题提高组(清北... ...

noip级考试题

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...2010年noip第一次模拟考... 5页 免费 清北学堂NOIP...201 绵阳中学高 2012 级递归专题训练 1S, 所有题...
更多相关标签:
清北学堂 | 国庆节课件 | 清北学堂生物题库 | 清北学堂官网 | 国庆节ppt课件 | 清北学堂怎么样 | 国庆节主题班会课件 | 国庆课件 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com