欢迎来到天天文库
浏览记录
ID:58831912
大小:1.15 MB
页数:44页
时间:2020-10-01
《信息学奥数NOIP归纳、贪心、二分、数论ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、信息学奥赛NOIP归纳、贪心、二分、数论内容提要二分,倍增贪心例1例2小结当变量之间有单调关系时,可以考虑使用二分法如搬运食物量与时间、理发人数与时间之间的关系例3例4小结“最大值最小”“最小值最大”这类字眼往往与二分法相关通过使用二分法可以把最优化问题转化为判定性问题二分法本质上永远基于单调性例5快速幂代码例6例7ST代码例8例9贪心由局部最优解得到全局最优解高效猜测困难(简单?),证明困难先来看几个经典例题例10例11例12给出若干区间,要求选出一些使得两两不相交,问最多选多少个。例13例14例15例16小结先给出策略,再证明
2、正确性证明可尝试对问题规模归纳,或反证实在不行暴力打表验证数论数学号称科学之王,而数论则谓之为其王冠。“数论,那可是我们数学的半壁江山!……哦不,三分之一……呃,四分之一……五分之一!你们看到我有多讨厌数论了吧!”基础知识基础知识埃拉托斯特尼筛法欧几里得算法扩展欧几里得算法扩展欧几里得算法例17欧拉函数欧拉定理模意义下的乘法逆元例18中国剩余定理组合数两种基本模型插板模型格路模型例19例20容斥原理例21That’sall预祝大家在NOIP、省选、NOI甚至IOI中都取得优异成绩!欢迎与我联系,讨论题目!
此文档下载收益归作者所有