信息学奥赛NOIP教程基于贪心的算法和应用
- 格式：ppt
- 大小：1.92 MB
- 文档页数：39
下载文档原格式
合集下载
信息学竞赛NOIP考试10大建议(编程竞赛考试经验)
信息学竞赛NOIP考试10大建议——编程竞赛考试经验对参加NOIP全国青少年信息学奥赛的考生，我们整理和收集了10个建议给家长和学生参考。
目录：1先思考→2考虑全面→3要灵活→4认真读题→5特殊数据→6思路清晰→7勿着急→8查错误→9要骗分→10成败观→灵感补充一、先思考一定要想好了算法，思路清晰了再编。
分析问题时遇到一些即兴问起的情况，马上要深入下去，看已有的算法思路是否有问题。
经验证明,这种即兴提起的问题往往是决定算法正误的关键问题。
这是一种本能的质疑，本能的差错，一定不要想：我一会再来看这个问题。
一定要立即想清楚，看算法怎么样处理才能解决这样一个问题。
确认算法没有什么错误了再编。
如果思路没清晰，算法不对，编到一半时才发现错了，这种情况没有考虑到，浪费了很多时间，或者编完了都还不知道算法是错的，最后由于样例特殊，过了样例，以为对了，但实际上只得10分，或者根本不得分。
二、考虑全面对于简单的题，一定要考虑全面，不是编好了程序再来考虑全面，而是想算法的时候就要考虑全面。
不要知道个大概就开始写，后来发现一些特殊数据要作特殊处理，又把程序改过去改过来，改得面目全非，最后老是改不对，不但影响心情，而且还是错的。
三、要灵活看题要灵活，不要绊死在一道题，不要怕。
NOIP的题不想就做出来，怎么可能，肯定是需要想的。
但是最好先写好写的题，不一定是前两道题。
其实很多时候你是有能力做起的，只是你一看就怕了，也没有去认真想，随便敷衍想了一点特殊情况的算法，认为可以骗到分。
但经验证明最后基本是没有分，即使有，最多不过10。
时间是3个小时，要积极一点，经验证明，很多题想到一定时候便想出来了，并且很简单。
四、认真读题一定要认真读题，读的时候积极思考，看看这某句话到底是个什么意思，要会转换。
特别是对于有时间的问题，到底把时间看成一个点，还是一个区间，具体题目具体分析，一定要符合题意。
题没读懂就开始做，100%是错的。
题错，思路也就错，时间浪费了，数据还是1个都不过。
高中信息技术信息学奥林匹克竞赛(德州)
2.NOI （全国信息学奥林匹克竞赛）
National Olympiad in Informatics
3.IOI （国际信息学奥林匹克竞赛）
International Olympiad in Informatics
NOIP分区联赛
初赛： • 10月中旬（周六下午2:30-4:30） • 笔试（100分） • 资格赛，地市独立组织（全国统一命题，统一时间） 复赛： • 11月份中旬（第二周,周六、周日上午8:30-12:00） • 两试（上机） • 每试3个题目，每题100分，共600分 • 提交源程序，黑盒子测试法 • 各省统一组织考试 • 全国统一评测
全国联赛（NOIP）知识点：
一、语言：Free pascal （c/c++）基础 二、数据结构 线性表、栈、队列、树、图 三、算法： 高精度运算
主要考察基本数据结构与算法的应用能力
搜索算法（dfs，bfs） 动态规划dp 贪心算法、模拟算法等 相关的数论知识
排序算法
全国竞赛（NOI）
• • • • 并查集、树状数组、线段树 查源自树 网络流 几何算法 ……人数
每个年级保持在15人左右较好 开始多一点，慢慢的淘汰
吸引学生、培养兴趣 第一堂课很重要
信息学奥赛解决的问题：
• 经过思考能够得出解决的方法，但是却很难或者根 本不可能用人工的做出来。 • 设计算法，用计算机语言设计程序实现自己的方法， 从而解决问题。
步骤：
• • • • • 观察分析问题 思考问题，得出模型（数学模型） 设计解决问题的算法或者步骤 用计算机语言设计程序实现算法 调试验证算法的正确性
报名参赛人数全国前两位。 一等奖分数线基本前5 一等奖人数分配到省（山东50左右，不包括重复获奖） 全国前6左右 金牌8枚(4所学校)
信息学奥赛中的动态规划 ppt课件
11
对于全部的数据，M<=100。
老规矩： 暴搜TLE 贪心一定WA 最短路你可以试试……
怎么办？
PPT课件
12
动态规划才是王道！
我们先分析下暴搜的过程： 我们对每个物品进行了搜索，产生了大量的状态，每个状态包括三个要
点： 1.目前已用的背包的容量，这个不用多说 2.目前已经获得的价值，这个也不用多说 3.目前已经处理了多少物品，记录下已经处理物品数量的原因是由于每
1.不带附件
2.带附件A
3.带附件B
4.带附件A和B
5.连主件都不拿
那么只要在状态转移时枚举每个物品拿还是不拿，拿几个附
件即可……
PPT课件
36
至此，背包问题全部完成！
但这仅仅是简单的背包问题而已
PPT课件
37
区间型DP
PPT课件
别看我看标题
38
石子归并
PPT课件
经典区间型dp
PPT课件
22
二维背包问题
对于每个物品，分别有体积v和重量w，求体积和重量均不超 标的情况下可以拿到的最大价值
维数改为三维，改变下转移，也可简化为二维，从后往前for 得出正确答案
PPT课件
23
完全背包问题
每个物品可以拿无限次，只要不超过最大重量即可
PPT课件
24
思路1：背包+枚举
输出描述 Output Description 输出包括一行，这一行只包含一个整数，表示在不超过规定重量的情况下，可以拿到 的最大价值。
样例输入 Sample Input 11 11
样例输出 Sample Output 1
数据范围及提示 Data Size & Hint
全国青少年信息学奥林匹克联赛大纲
全国青少年信息学奥林匹克联赛大纲(节选)NOIP大纲一、总则由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛(NOIP)是全国信息学奥林匹克竞赛(NOI)整个系列中的一个重要组成部分,旨在向中学生普及计算机基础知识,培养计算机科学和工程领域的后备人才。
普及的重点是根据中学生的特点,培养学生学习计算机的兴趣,使得他们对信息技术的一些核心内容有更多的了解,提高他们创造性地运用程序设计知识解决实际问题的能力。
对学生的能力培养将注重以下的几个方面:●想象力与创造力;●对问题的理解和分析能力;●数学能力和逻辑思维能力;●对客观问题和主观思维的口头和书面表达能力;●人文精神:包括与人的沟通能力,团队精神与合作能力,恒心和毅力,审美能力等。
二、命题程序和组织机构命题是选拔过程的重要一环,同时对计算机的普及内容起着导向性的作用。
命题应注重趣味性、新颖性、知识性、应用性和中学生的心智特点,不直接从大学专业教材中选题。
在命题和审题工作中,坚持开放和规范的原则。
在NOI科学委员会主持下成立的联赛命题委员会负责命题工作,命题委员会成员主要来自参加联赛的省(包括直辖市、自治区、下同。
每个省最多派一名委员),也可来自社会计算机界。
联赛命题委员会的主要职责是提供联赛的备选题目,并承担对所提供的题目保密的责任。
1. 联赛命题委员会委员应具备如下资格:●从事一线计算机教学或信息学奥赛辅导工作两年(含)以上;●有精力和时间从事该项工作;●对此项工作有兴趣并愿意作为志愿者从事NOIP命题及其相关工作。
2. 联赛命题委员会委员的产生过程:●本人提出申请(填写表格);●中学教师需所在单位同意或省奥赛主管部门同意;●科学委员会批准,由中国计算机学会颁发聘书(每一聘期为两年)。
3. 联赛命题委员会委员的职责:●每年为NOIP提供备选题题目若干,在9月1日之前提交科学委员会;●备选试题的保密期为2年,在该段时间内不得泄密或另作他用;●搜集本省信息学奥赛的有关信息并向科学委员会通报;题目一经提交,即表明同意授权中国计算机学会科学委员会全权处理,包括使用、修改和出版。
CCF中学生计算机程序设计能力评级信息学奥赛NOIP动态规划算法及优化
1 ≤ n ≤ 5000, 1 ≤ b, ci, di ≤ 109。
动态规划算法 及优化
Codeforces 815C Karen and Supermarket
背包类问题 数据结构优化 决策单调性 计数
可以发现依赖关系形成了一棵树，因此可以考虑在树上
进行 DP。需要注意的是，本题中物品的价格可能非常大， 但是每个物品的收益只有 1，因此我们 DP 时第二维表示的 应当是买了多少个物品。
动态规划算法 及优化
背包类问题 数据结构优化 决策单调性 计数
动态规划算法及优化
动态规划算法 及优化
背包问题
背包类问题 数据结构优化 决策单调性 计数
01 背包：n 个物品，每个物品有价格 ci 及收益 wi ，问 m 元最多能得到多少收益。
完全背包：n 种物品，每种物品有价格 ci 及收益 wi，并 且每种物品能买无限个，问 m 元最多能得到多少收益。
n ≤ 500, m ≤ 4000, di ≤ 100。
动态规划算法 及优化
BZOJ4182 Shopping
背包类问题 数据结构优化 决策单调性 计数
先考虑我们知道必选某个节点时怎么做。可以把这个点
当成根，那么问题就转化为了一个树上依赖背包问题。 考虑用和上一题类似的方法进行 DP。令 fi,j 表示在节点
背包类问题 数据结构优化 决策单调性 计数
树上依赖背包其实还有一个经典的做法。考虑一边 dfs 一边 DP。dfs 到节点 i 的时候，我们先把 DP 数组拷贝一份， 表示不选 i 的子树时的背包。接着我们用多重背包的做法加 入商品 i，并且强制至少买一个商品 i。然后我们再依次 dfs 进每个儿子的子树中，回溯到 i 时我们就得到了在 i 的子树 中买了物品的背包，把它与原先拷贝的背包取个 max 即可。 这样复杂化即可。这样加入一个物品的复杂度是 O(m)
动态规划算法 及优化
Codeforces 815C Karen and Supermarket
背包类问题 数据结构优化 决策单调性 计数
可以发现依赖关系形成了一棵树，因此可以考虑在树上
进行 DP。需要注意的是，本题中物品的价格可能非常大， 但是每个物品的收益只有 1，因此我们 DP 时第二维表示的 应当是买了多少个物品。
动态规划算法 及优化
背包类问题 数据结构优化 决策单调性 计数
动态规划算法及优化
动态规划算法 及优化
背包问题
背包类问题 数据结构优化 决策单调性 计数
01 背包：n 个物品，每个物品有价格 ci 及收益 wi ，问 m 元最多能得到多少收益。
完全背包：n 种物品，每种物品有价格 ci 及收益 wi，并 且每种物品能买无限个，问 m 元最多能得到多少收益。
n ≤ 500, m ≤ 4000, di ≤ 100。
动态规划算法 及优化
BZOJ4182 Shopping
背包类问题 数据结构优化 决策单调性 计数
先考虑我们知道必选某个节点时怎么做。可以把这个点
当成根，那么问题就转化为了一个树上依赖背包问题。 考虑用和上一题类似的方法进行 DP。令 fi,j 表示在节点
背包类问题 数据结构优化 决策单调性 计数
树上依赖背包其实还有一个经典的做法。考虑一边 dfs 一边 DP。dfs 到节点 i 的时候，我们先把 DP 数组拷贝一份， 表示不选 i 的子树时的背包。接着我们用多重背包的做法加 入商品 i，并且强制至少买一个商品 i。然后我们再依次 dfs 进每个儿子的子树中，回溯到 i 时我们就得到了在 i 的子树 中买了物品的背包，把它与原先拷贝的背包取个 max 即可。 这样复杂化即可。这样加入一个物品的复杂度是 O(m)
(完整版)信息学奥赛考试大纲
信息学奥赛考试大纲一、竞赛形式和成绩评定联赛分两个等级组：普及组和提高组.每组竞赛分两轮：初试和复试。
l 初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。
初试为资格测试，各省初试成绩在本赛区前15%的学生进入复赛。
l 复试形式为上机，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。
各省联赛的等第奖在复试的优胜者中产生。
比赛中使用的程序设计语言是：l 2003年:初赛：BASIC、PASCAL或C/C++；复赛:BASIC、PASCAL或C/C++.l 2004年：初赛:BASIC、PASCAL或C/C++：复赛：PASCAL或C/C++。
l 2005年及之后：初赛：PASCAL或C/C++：复赛:PASCAL或C/C++.每年复赛结束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。
经复审确认后，由中国计算机学会报送中国科协和教育部备案。
中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。
二、试题形式每次联赛的试题分四组:普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。
其中，A1和B1类型相同，A2和B2类型相同,但题目不完全相同,提高组难度高于普及组. l 初赛:初赛全部为笔试，满分100分。
试题由四部分组成:1、选择题：共20题,每题1。
5分，共计30分。
每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案,只有全部选对才得分)。
2、问题求解题:共2题,每题5分,共计10分。
试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法,并推算出问题的解。
考生给出的答案与标准答案相同，则得分；否则不得分。
3、程序阅读理解题：共4题,每题8分，共计32分.题目给出一段程序（不一定有关于程序功能的说明）,考生通过阅读理解该段程序给出程序的输出。
贪心算法求解最优解问题
贪心算法求解最优解问题贪心算法是计算机科学领域中常用的一种算法。
它常常被用来求解最优解问题，如背包问题、最小生成树问题、最短路径问题等。
贪心算法解决最优解问题的基本思路是，每一步都选取当前状态下最优的解决方案，直到达到全局最优解。
在这篇文章中，我们将为大家深入探讨贪心算法求解最优解问题的基本思路、算法复杂度和应用场景等方面的知识。
基本思路贪心算法是一种基于贪心策略的算法。
其核心思想是，每一步都采用当前最优策略，以期最终达到全局最优解。
在贪心算法中，每个子问题的最优解一般都是由上一个子问题的最优解推导出来的。
因此，关键在于如何找到最优解。
具体而言，贪心算法一般由三部分组成，分别为：状态、选择和判断。
首先，需要明确当前问题的状态，即问题的规模和限制条件。
然后，在当前的限制条件下，我们需要从可能的方案中选择出最优的方案，并把这个选择作为解的一部分。
最后，需要判断选择是否符合问题的限制条件，是否达到全局最优解。
算法复杂度在进行算法分析时，我们需要考虑算法的时间复杂度和空间复杂度。
对于贪心算法而言，其时间复杂度一般是 O(nlogn) 或 O(n) 级别的，其中 n 表示问题的规模。
这种效率在实际应用中表现出了很高的稳定性和效率。
应用场景贪心算法通常应用于需要求解最优解问题的场景中。
例如：- 贪心算法可以用来求解背包问题。
在背包问题中，我们需要在限定的空间内选取最有价值的物品装入背包中以努力获得最大的收益。
在贪心策略下，我们只需要按单位重量价值从大到小的顺序进行选择，就可以得到最优解；- 贪心算法也可以用来求解最小生成树问题。
这个问题是指，在给定一个图的时候，我们需要选出一棵生成树，使得生成树上的所有边权之和最小。
在此问题中，我们可以将图上的边权按大小排序，然后顺序选择边直至生成树。
这样，我们可以得到与全局最优解很接近的解；- 贪心算法还可以用来求解最短路径问题。
在最短路径问题中，我们需要找到从一个节点到另一个节点的最短路径。
noip信息学奥赛规则及要求
noip信息学奥赛规则及要求大家好！今天我要跟大家聊聊那个让人又爱又恨的“noip”信息学奥赛。
这个比赛，就像是一场没有硝烟的战争，考验着我们的智慧和耐心。
我们要明确一点，noip信息学奥赛可不是闹着玩的，它可是全国大学生程序设计竞赛哦！这可是计算机科学领域的奥林匹克大赛，参赛者都是来自全国各地的优秀大学生。
他们不仅要在比赛中展示自己的编程技巧，还要在紧张的赛程中保持冷静，发挥出最好的水平。
比赛内容嘛，就是让我们用电脑来解决各种有趣的问题。
这些问题可能涉及到算法、数据结构、操作系统、人工智能等领域。
我们需要运用所学的知识，编写出高效、稳定、易于维护的程序来解决问题。
比赛的时间限制非常严格，每一分钟都关乎胜负，所以我们必须做到既快又好。
在这个过程中，我们会遇到各种各样的挑战。
一个问题可能会让我们头疼不已；一个难题会让我们陷入困境。
但正是这些挑战，激发了我们学习的动力，让我们不断进步，变得更加强大。
除了技术层面的问题，noip信息学奥赛还考验我们的心理素质。
比赛过程中，我们可能会遇到失败和挫折，这时候就需要我们保持冷静，调整心态，重新出发。
我们要相信自己的能力，勇敢面对困难，这样才能在比赛中取得好成绩。
参加noip信息学奥赛也是一种享受。
我们在准备过程中，可以学到很多实用的知识，提高自己的编程能力。
这也是一次难得的锻炼机会，让我们在实战中积累经验，为将来的职业生涯打下坚实的基础。
noip信息学奥赛是一场充满挑战和机遇的比赛。
它不仅能够锻炼我们的技术能力，还能培养我们的心理素质和团队合作精神。
我相信，只要我们坚持不懈，勇往直前，就一定能够在这场比赛中取得优异的成绩！今天的分享到此结束。
希望大家通过这篇文章，对noip信息学奥赛有了更深入的了解。
如果你也对编程感兴趣，那就赶紧加入这场精彩的战斗吧！让我们一起努力，为了梦想而奋斗！。
NOIP2016信息学奥赛普及组初赛C++精彩试题及问题详解较完美版
NOIP2016第二十二届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2016年10月22日14:30～16:30一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1．以下不是微软公司出品的软件是( )。
A．Powerpoint B．Word C.Excel D. Acrobat Reader2．如果256种颜色用二进制编码来表示，至少需要( )位。
A．6 B．7 C．8 D．93．以下不属于无线通信技术的是( )。
A．蓝牙 B．WiFi C．GPRS D．以太网4．以下不是CPU生产厂商的是( )。
A.IntelB.AMDC.MicrosoftD.IBM5．以下不是存储设备的是( )。
A．光盘 B．磁盘 C．固态硬盘 D．鼠标6．如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S 和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D、……，屏幕上输出的第81个字符是字母( )。
A．A B．S C．D D．a7．二进制数00101100和00010101的和是( )。
A.00101000B.01000001C.01000100D.001110008．与二进制小数0.1相等的八进制数是( )。
A．0.8 B．0.4 C．0.2 D．0.19．以下是32位机器和64位机器的区别的是( )。
A．显示器不同 B．硬盘大小不同C．寻址空间不同 D．输入法不同10．以下关于字符串的判定语句中正确的是( )A．字符串是一种特殊的线性表 B．串的长度必须大于零C．字符串不可以用数组来表示 D．空格字符组成的串就是空串11．一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标(2i+1)处），则图中所有结点的最大下标为( ) 。
信息学奥赛简介NOIP及C基础知识第一讲PPT课件
【问题分析】： 周长等于边长的4倍。 【算法设计】：正方形的边长用a表示，周长用c表示。
21
【参考程序】
#include<cstdio> int main(){
int a,c; scanf("%d",&a); c=4*a; printf("%d",c); return 0; }
22
三、基础知识
23
例2.输入三角形的三边a,b,c。求三角形的面积s （a，b，c是实数<100，满足三角形条件，结果保留3位小数）
样例输入1：3 4 5 样例输出1：6.000
样例输入2：1 1 1 样例输出2：0.433
分析： 求三角形面积的海伦公式：
sp (p a )p ( b )p ( c )
其中
p=(a+b+c)/2
12(8)。 3）十六进制形式。以0x打头，如0x12A，表示十六进制整数12A，即12A(16)。
2、实型常量：如3.1、-6.1E+2（科学记数法）。 3、字符常量：是用单引号括起来的字符，如 'k' 、'5' 、'%'。 注意：'a'与"a"表示的含义是不同的，'a'表示一个字符常量，"a"表示一个字符串。
printf(“%d”,a+b);
//输出a+b的值
return 0; //结束整个程序，返回0，每个主程序都必有。
} 25
说明
（1）以“//”开头为注释行，“//”后的内容用以对语句进 行说明，不运行，无需输入。
（2）上面的程序中共有4条语句，每条语句必须以分号“；” 作为结束。
21
【参考程序】
#include<cstdio> int main(){
int a,c; scanf("%d",&a); c=4*a; printf("%d",c); return 0; }
22
三、基础知识
23
例2.输入三角形的三边a,b,c。求三角形的面积s （a，b，c是实数<100，满足三角形条件，结果保留3位小数）
样例输入1：3 4 5 样例输出1：6.000
样例输入2：1 1 1 样例输出2：0.433
分析： 求三角形面积的海伦公式：
sp (p a )p ( b )p ( c )
其中
p=(a+b+c)/2
12(8)。 3）十六进制形式。以0x打头，如0x12A，表示十六进制整数12A，即12A(16)。
2、实型常量：如3.1、-6.1E+2（科学记数法）。 3、字符常量：是用单引号括起来的字符，如 'k' 、'5' 、'%'。 注意：'a'与"a"表示的含义是不同的，'a'表示一个字符常量，"a"表示一个字符串。
printf(“%d”,a+b);
//输出a+b的值
return 0; //结束整个程序，返回0，每个主程序都必有。
} 25
说明
（1）以“//”开头为注释行，“//”后的内容用以对语句进 行说明，不运行，无需输入。
（2）上面的程序中共有4条语句，每条语句必须以分号“；” 作为结束。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
writeln;
经典例题
【例5】均分纸牌（NOIP 2002） 有N堆纸牌，编号分别为1，2，……，N。第i
堆有a[i]张纸牌（a[i]≤10000）,但纸牌总数必 为N的倍数。可以在任一堆上取若干张纸牌，然后 移动。移牌规则为：在编号为1堆上取的纸牌，只 能移到编号为2的堆上；在编号为N的堆上取的纸 牌，只能移到编号为N－1的堆上；其他堆上取的 纸牌，可以移到相邻左边或右边的堆上。现在要 求找出一种移动方法，用最少的移动次数使每堆 牌数都一样多。
贪心算法的特点
【分析】 有以下几种策略可供选择： （1）每次挑选价值最大的物品装入背包， 得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是 否能得到最优解？ （3）每次选取单位容量价值最大的物品。
贪心算法的特点
解题一般步骤: 1、设计数据找规律； 2、进行贪心猜想； 3、正确性证明（严格证明和一般证明） ★一般证明：列举反例； ★严格证明：数学归纳和反证法； 4、程序实现。
经典例题
for i:=1 to n-1 do for j:=i+1 to n do if num[i]+num[j]<num[j]+num[i] then begin temp:=num[i]; num[i]:=num[j]; num[j]:=temp end;
for i:=1 to n do write(num[i]);
经典例题
结论： 每一次删除的数字应该是这个数字序列
中最左边递减序列的第一个数字。具体操作 为，按高位到低位的方向搜索递减区间。若 不存在递减区间，则删除尾数字，否则删除 递减区间的首数符，这样就形成一个最小的 数。
重复上述规则，直到删除S个数字为止。
经典例题
例如：N＝8796542，S＝4 第一次：N＝8796542，删除8； 第二次：N＝796542，删除9； 第三次：N＝76542，删除7； 第四次：N＝6542，删除6，得到542。
经典例题
例如：N＝4，纸牌数分别为9、8、17、6，移动3 次可达到目的。 第一次：从第3堆取4张牌放到第4堆；
9、8、13、10 第二次：从第3堆取3张牌放到第2堆；
9、11、10、10 第三次：从第2堆取1张牌放到第1堆。
10、10、10、10
经典例题
【分析】 设v为均分后每堆纸牌的张数，s为最少移动
的两端都是偶数位置上的数，如果A方取走 偶数位置上的数后，剩下的两端都是奇数 位置上的数。
A方既可以取走所有奇数位置上的数， 或者取走所有偶数位置上的数。
另一个策略：让A方取“数和较大的奇 （或偶）位置上的所有数”。
讨论一
readln(n); for i:=1 to 2*n do
read(a[i]); sa:=0; sb:=0; for i:=1 to n do begin
经典例题
【分析】 根据题意用另一种字符串比较办法，将A+B与
B+A相比较，如果前者大于后者，则认为A>B，按 这一定义将所有的数字字符串从大到小排序后连 接起来所得到的数字字符串即是问题的解。排序 时先将所有字符串中的最大值选出来存在数组的 第一个元素中，再从第二至最后一个元素中最大 的字符串选出来存在数组的第二个元素中，直到 从最后两个元素中选出最大的字符串存在数组的 倒数第二个元素中为止。
讨论二
武将了），换句话说，所谓的自由武将不属于任 何一方。游戏开始，小涵和计算机要从自由武将 中挑选武将组成自己的军队，规则如下：小涵先 从自由武将中选出一个加入自己的军队，然后计 算机也从自由武将中选出一个加入计算机方的军 队。接下来一直按照“小涵→计算机→小涵 →……”的顺序选择武将，直到所有的武将被双 方均分完。然后，程序自动从双方军队中各挑出 一对默契值最高的武将组合代表自己的军队进行 二对二比武，拥有更高默契值的一对武将组合获 胜，表示两军交战，拥有获胜武将组合的一方获 胜。
讨论二
双方选将过程如下所示：
武将相互之间的默契值： 双方选将过程如下所示：
讨论二
小涵想知道，如果计算机在一局游戏中始终 坚持上面这个策略，那么自己有没有可能必胜？ 如果有，在所有可能的胜利结局中，自己那对用 于比武的武将组合的默契值最大是多少？
假设整个游戏过程中，对战双方任何时候均 能看到自由武将队中的武将和对方军队的武将。 为了简化问题，保证对于不同的武将组合，其默 契值均不相同。
end;
writeln(s);
讨论二
【例6】三国游戏（NOIP2010普及组第4题） 小涵很喜欢电脑游戏，这些天他正在玩一个
叫做《三国》的游戏。 在游戏中，小涵和计算机各执一方，组建各
自的军队进行对战。游戏中共有N位武将（N为偶 数且不小于4），任意两个武将之间有一个“默契 值”，表示若此两位武将作为一对组合作战时， 该组合的威力有多大。游戏开始前，所有武将都 是自由的（称为自由武将，一旦某个自由武将被 选中作为某方军队的一员，那么他就不再是自由
能会出现第i+1堆的纸牌数小于0的情况。如n＝3 ，三堆纸牌数为1、2、27，v＝10，要从第2堆移 动9张纸牌到第1堆，而第2堆只有2张纸牌可以移 动。按照规则会得到10、-7、27，再从第3堆移动 17张纸牌到第2堆，即得到10、10、10。在移动过 程中，只要改变一下移动的顺序，而移动的次数 不会变。
经典例题
readln(n); readln(s); for k:=1 to s do begin
i:=1; while (i<length(n)) and (n[i]<=n[i+1]) do
inc(i); delete(n,i,1); end; while (length(n)>1) and (n[1]=‘0’) do delete(n,1,1) writeln(n);
基于贪心的算法和应用
贪心算法引入
【引例1】在n行m列的正整数矩阵中，要求 从每行中选出1个数，使得选出的总共n个 数的和最大。 【分析】要使总和最大，则每个数要尽可 能大，自然应该选每行中最大的那个数。
贪心算法引入
【引例2】有1元、5元、10元、50元、100 元、500元的硬币各C1、C5、C10、C50、 C100、C500枚。现在要用这些硬币来支付A 元，最少需要多少枚硬币？ 【分析】优先使用面值大的硬币。
经典例题
【分析】 平均等待时间就是每个人的等待时间之和再除以
n，因为n是常数，所以等待时间之和最小也就等同于 平均等待时间最小。 Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+…(Ti1+Ti2+…+Tin)
=nTi1+(n-1)Ti2+(n-2)Ti3+…+Tin 如果让Ti1最小，Ti2次小，…，Tin最大，也就是 把接水时间少的人尽可能排在前面，总的等待时间就 最少了。
输出剩下的最小数。
经典例题
【分析】 因为要删除S个数字，可以一个一个地删
，每一次删除的目的都是使剩下的数尽量小 。
那么在每一次删除时，应该选择哪个数 字呢？最大的那个数字？还是最左边的那个 数字？
例如5768，删除7可以使剩余的数最小。
//删除7会使后面的较小数前移，从而得到更小的数。如果不删除7，删除之前的较小数，会 使大数7前移。删除7之后的较小数，则比删除7这个较大数得到的数要大。
讨论一
【例2】取数问题（IOI 1996） 给出2n（n≤100）个自然数（小于等
于30000），将这2n个自然数排成一列，游 戏双方A和B从中轮流取数，只允许从两端 取数，A方先取，然后B方再取。取完时， 谁取的数字总和最大为取胜方；若双方和 相等，则B胜，试问A方是否有必胜策略？
讨论一
输入格式：两行，第一行一个整数n，第二 行有2n个自然数。 输出格式：只有一行，若A有必胜策略，则 输出“YES”，否则输出“NO”。 输入样例： 4 79364253 输出样例： YES
经典例题
【分析】 本例因为涉及将两个自然数连接起来的问
题，采用字符串来处理比较方便。首先我们自 然会想到大的字符串应该排在前面，因为如果 A与B是两个由数字字符构成的字符串且A>B， 一般情况下有A+B>B+A，但是当A=B+C时，按字 符串的大小定义有A>B，但有可能会出现 A+B<B+A的情况，如A=121,B=12,则 A+B=12112,B+A=12121,A+B<B+A。
讨论一
【分析】 若采用这样一种策略，让A方每次取数
列两端较大的那个数，则B方也会这样取， 对于样例：7 9 3 6 4 2 5 3，
A方会取得7、3、4、5， B方会取得9、6、2、3， A方的总和为19，B方的总和为20，按 照规则，输出“NO”。
讨论一
【分析】 如果A方取走奇数位置上的数后，剩下
经典例题
※ 删数问题（NOI 1995） ※ 取数问题（IOI 1996） ※ 接水问题 ※ 最大整数 ※ 均分纸牌（NOIP 2002） ※ 三国游戏（NOIP 2010） ※ 火柴排队（NOIP 2013）
经典例题
【例1】删数问题（NOI 1994） 键盘输入一个高精度的正整数N，去掉
其中任意S个数字后剩下的数字按原左右次 序将组成一个新的正整数。编程对给定的N 和S，寻找一种方案使得剩下的数字组成的 新数最小。
讨论二
已知计算机一方选择武将的原则是尽量破坏 对手下一步将形成的最强组合，它采取的具体策 略如下：任何时刻，轮到计算机挑选时，它会尝 试将对手军队中的每个武将与当前每个自由武将 进行一一配对，找出所有配对中默契值最高的那 对武将组合，并将该组合中的自由武将选入自己 的军队。
经典例题
【例5】均分纸牌（NOIP 2002） 有N堆纸牌，编号分别为1，2，……，N。第i
堆有a[i]张纸牌（a[i]≤10000）,但纸牌总数必 为N的倍数。可以在任一堆上取若干张纸牌，然后 移动。移牌规则为：在编号为1堆上取的纸牌，只 能移到编号为2的堆上；在编号为N的堆上取的纸 牌，只能移到编号为N－1的堆上；其他堆上取的 纸牌，可以移到相邻左边或右边的堆上。现在要 求找出一种移动方法，用最少的移动次数使每堆 牌数都一样多。
贪心算法的特点
【分析】 有以下几种策略可供选择： （1）每次挑选价值最大的物品装入背包， 得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是 否能得到最优解？ （3）每次选取单位容量价值最大的物品。
贪心算法的特点
解题一般步骤: 1、设计数据找规律； 2、进行贪心猜想； 3、正确性证明（严格证明和一般证明） ★一般证明：列举反例； ★严格证明：数学归纳和反证法； 4、程序实现。
经典例题
for i:=1 to n-1 do for j:=i+1 to n do if num[i]+num[j]<num[j]+num[i] then begin temp:=num[i]; num[i]:=num[j]; num[j]:=temp end;
for i:=1 to n do write(num[i]);
经典例题
结论： 每一次删除的数字应该是这个数字序列
中最左边递减序列的第一个数字。具体操作 为，按高位到低位的方向搜索递减区间。若 不存在递减区间，则删除尾数字，否则删除 递减区间的首数符，这样就形成一个最小的 数。
重复上述规则，直到删除S个数字为止。
经典例题
例如：N＝8796542，S＝4 第一次：N＝8796542，删除8； 第二次：N＝796542，删除9； 第三次：N＝76542，删除7； 第四次：N＝6542，删除6，得到542。
经典例题
例如：N＝4，纸牌数分别为9、8、17、6，移动3 次可达到目的。 第一次：从第3堆取4张牌放到第4堆；
9、8、13、10 第二次：从第3堆取3张牌放到第2堆；
9、11、10、10 第三次：从第2堆取1张牌放到第1堆。
10、10、10、10
经典例题
【分析】 设v为均分后每堆纸牌的张数，s为最少移动
的两端都是偶数位置上的数，如果A方取走 偶数位置上的数后，剩下的两端都是奇数 位置上的数。
A方既可以取走所有奇数位置上的数， 或者取走所有偶数位置上的数。
另一个策略：让A方取“数和较大的奇 （或偶）位置上的所有数”。
讨论一
readln(n); for i:=1 to 2*n do
read(a[i]); sa:=0; sb:=0; for i:=1 to n do begin
经典例题
【分析】 根据题意用另一种字符串比较办法，将A+B与
B+A相比较，如果前者大于后者，则认为A>B，按 这一定义将所有的数字字符串从大到小排序后连 接起来所得到的数字字符串即是问题的解。排序 时先将所有字符串中的最大值选出来存在数组的 第一个元素中，再从第二至最后一个元素中最大 的字符串选出来存在数组的第二个元素中，直到 从最后两个元素中选出最大的字符串存在数组的 倒数第二个元素中为止。
讨论二
武将了），换句话说，所谓的自由武将不属于任 何一方。游戏开始，小涵和计算机要从自由武将 中挑选武将组成自己的军队，规则如下：小涵先 从自由武将中选出一个加入自己的军队，然后计 算机也从自由武将中选出一个加入计算机方的军 队。接下来一直按照“小涵→计算机→小涵 →……”的顺序选择武将，直到所有的武将被双 方均分完。然后，程序自动从双方军队中各挑出 一对默契值最高的武将组合代表自己的军队进行 二对二比武，拥有更高默契值的一对武将组合获 胜，表示两军交战，拥有获胜武将组合的一方获 胜。
讨论二
双方选将过程如下所示：
武将相互之间的默契值： 双方选将过程如下所示：
讨论二
小涵想知道，如果计算机在一局游戏中始终 坚持上面这个策略，那么自己有没有可能必胜？ 如果有，在所有可能的胜利结局中，自己那对用 于比武的武将组合的默契值最大是多少？
假设整个游戏过程中，对战双方任何时候均 能看到自由武将队中的武将和对方军队的武将。 为了简化问题，保证对于不同的武将组合，其默 契值均不相同。
end;
writeln(s);
讨论二
【例6】三国游戏（NOIP2010普及组第4题） 小涵很喜欢电脑游戏，这些天他正在玩一个
叫做《三国》的游戏。 在游戏中，小涵和计算机各执一方，组建各
自的军队进行对战。游戏中共有N位武将（N为偶 数且不小于4），任意两个武将之间有一个“默契 值”，表示若此两位武将作为一对组合作战时， 该组合的威力有多大。游戏开始前，所有武将都 是自由的（称为自由武将，一旦某个自由武将被 选中作为某方军队的一员，那么他就不再是自由
能会出现第i+1堆的纸牌数小于0的情况。如n＝3 ，三堆纸牌数为1、2、27，v＝10，要从第2堆移 动9张纸牌到第1堆，而第2堆只有2张纸牌可以移 动。按照规则会得到10、-7、27，再从第3堆移动 17张纸牌到第2堆，即得到10、10、10。在移动过 程中，只要改变一下移动的顺序，而移动的次数 不会变。
经典例题
readln(n); readln(s); for k:=1 to s do begin
i:=1; while (i<length(n)) and (n[i]<=n[i+1]) do
inc(i); delete(n,i,1); end; while (length(n)>1) and (n[1]=‘0’) do delete(n,1,1) writeln(n);
基于贪心的算法和应用
贪心算法引入
【引例1】在n行m列的正整数矩阵中，要求 从每行中选出1个数，使得选出的总共n个 数的和最大。 【分析】要使总和最大，则每个数要尽可 能大，自然应该选每行中最大的那个数。
贪心算法引入
【引例2】有1元、5元、10元、50元、100 元、500元的硬币各C1、C5、C10、C50、 C100、C500枚。现在要用这些硬币来支付A 元，最少需要多少枚硬币？ 【分析】优先使用面值大的硬币。
经典例题
【分析】 平均等待时间就是每个人的等待时间之和再除以
n，因为n是常数，所以等待时间之和最小也就等同于 平均等待时间最小。 Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+…(Ti1+Ti2+…+Tin)
=nTi1+(n-1)Ti2+(n-2)Ti3+…+Tin 如果让Ti1最小，Ti2次小，…，Tin最大，也就是 把接水时间少的人尽可能排在前面，总的等待时间就 最少了。
输出剩下的最小数。
经典例题
【分析】 因为要删除S个数字，可以一个一个地删
，每一次删除的目的都是使剩下的数尽量小 。
那么在每一次删除时，应该选择哪个数 字呢？最大的那个数字？还是最左边的那个 数字？
例如5768，删除7可以使剩余的数最小。
//删除7会使后面的较小数前移，从而得到更小的数。如果不删除7，删除之前的较小数，会 使大数7前移。删除7之后的较小数，则比删除7这个较大数得到的数要大。
讨论一
【例2】取数问题（IOI 1996） 给出2n（n≤100）个自然数（小于等
于30000），将这2n个自然数排成一列，游 戏双方A和B从中轮流取数，只允许从两端 取数，A方先取，然后B方再取。取完时， 谁取的数字总和最大为取胜方；若双方和 相等，则B胜，试问A方是否有必胜策略？
讨论一
输入格式：两行，第一行一个整数n，第二 行有2n个自然数。 输出格式：只有一行，若A有必胜策略，则 输出“YES”，否则输出“NO”。 输入样例： 4 79364253 输出样例： YES
经典例题
【分析】 本例因为涉及将两个自然数连接起来的问
题，采用字符串来处理比较方便。首先我们自 然会想到大的字符串应该排在前面，因为如果 A与B是两个由数字字符构成的字符串且A>B， 一般情况下有A+B>B+A，但是当A=B+C时，按字 符串的大小定义有A>B，但有可能会出现 A+B<B+A的情况，如A=121,B=12,则 A+B=12112,B+A=12121,A+B<B+A。
讨论一
【分析】 若采用这样一种策略，让A方每次取数
列两端较大的那个数，则B方也会这样取， 对于样例：7 9 3 6 4 2 5 3，
A方会取得7、3、4、5， B方会取得9、6、2、3， A方的总和为19，B方的总和为20，按 照规则，输出“NO”。
讨论一
【分析】 如果A方取走奇数位置上的数后，剩下
经典例题
※ 删数问题（NOI 1995） ※ 取数问题（IOI 1996） ※ 接水问题 ※ 最大整数 ※ 均分纸牌（NOIP 2002） ※ 三国游戏（NOIP 2010） ※ 火柴排队（NOIP 2013）
经典例题
【例1】删数问题（NOI 1994） 键盘输入一个高精度的正整数N，去掉
其中任意S个数字后剩下的数字按原左右次 序将组成一个新的正整数。编程对给定的N 和S，寻找一种方案使得剩下的数字组成的 新数最小。
讨论二
已知计算机一方选择武将的原则是尽量破坏 对手下一步将形成的最强组合，它采取的具体策 略如下：任何时刻，轮到计算机挑选时，它会尝 试将对手军队中的每个武将与当前每个自由武将 进行一一配对，找出所有配对中默契值最高的那 对武将组合，并将该组合中的自由武将选入自己 的军队。