NOIP普及组历届试题分析.ppt

NOIP普及组历届试题分析 安徽省六安第一中学江家和 引言 noip复赛的知识面很广泛 对选手的综合素质考核要求更为严格 难度和分数的阶梯层次更趋科学合理 对信息学活动的推动力和社会公信力更为增强 NOIP普及组题型分布 NOIP普及组题型分布 一 枚举类试题 枚举法的基本思想是根据提出的问题枚举所有可能的解 并用问题给定的条件检验哪些解是需要的 哪些解是不需要的 能使条件成立 即为其解 枚举法其实是最简单的搜索算法 珠心算测验 noip2014普及组第一题 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术 珠心算训练 既能够开发智力 又能够为日常生活带来很多便利 因而在很多学校得到普及 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法 他随机生成一个正整数集合 集合中的数各不相同 然后要求学生回答 其中有多少个数 恰好等于集合中另外两个 不同的 数之和 最近老师出了一些测验题 请你帮忙求出答案 珠心算测验 noip2014普及组第一题 输入 输入共两行 第一行包含一个整数n 表示测试题中给出的正整数个数 第二行有n个正整数 每两个正整数之间用一个空格隔开 表示测试题中给出的正整数 输出 输出共一行 包含一个整数 表示测验题答案 样例输入 样例输出 421234 对于100 的数据 3 n 100测验题给出的正整数大小不超过10 000 试题分析 题意大意 给你n个数 在这n个数中 找到满足A B C的C的个数 注意不是这个等式的个数 样例中 1 2 3 4有1 2 3 1 3 4两个 由于本题数据规模n 100 我们可以直接枚举C A B 三层循环解决问题 方法1 三层循环 考试中 有许多选手的程序是这样的 错在哪里 ans 0 forc 1tondofora 1tondoforb 1tondoif f c f a f b and ca and ab and cb theninc ans writeln ans 样例中 上述错误答案是4 3 1 2 3 2 1 4 1 3 4 3 1 方法1 参考程序 vari n a b c t ans longint f array 0 105 oflongint beginreadln n fori 1tondoread f i ans 0 forc 1tondobegint 0 fora 1tondoforb 1tondoif f c f a f b and t 0 and ca and ab and cb thenbegininc ans t 1 end end writeln ans end 方法2 两层循环 我们能不能使用两层循环呢 由于本题测验题给出的正整数大小不超过10 000 我们可以直接枚举A B 判断A B在不在给定的数中即可 定义一个数组vis 初始值为0 读入数a i 时 vis a i 标记为1 fori 1tondo read f i vis f i 1 方法2 两层循环 两层循环枚举a b的值 判断a b是否存在 fora 1tondoforb 1tondoif vis f a f b 1 and ab thenbegininc ans vis f a f b 2 避免出现重复的等式end 方法2 参考代码 vari n a b ans longint vis array 0 20005 of0 2 f array 0 105 oflongint beginreadln n fillchar vis sizeof vis 0 fori 1tondobeginread f i vis f i 1 end ans 0 fora 1tondoforb 1tondoif vis f a f b 1 and ab thenbegininc ans vis f a f b 2 end writeln ans end 数字统计 noip2010普及组第一题 请统计某个给定范围 L R 的所有整数中 数字2出现的次数 比如在给定范围 2 22 数字2在数2中出现了1次 在数12中出现了1次 在数20中出现了1次 在数21中出现了1次 在数22中出现了2次 所以数字2在该范围内一共出现了6次 输入格式输入共一行 为两个正整数L和R 之间用一个空格隔开 输出格式输出共1行 表示数字2出现的次数 样例输入 222样例输出 6 试题分析 题目大意是给定a b 统计a b之间数字2出现的次数 从a到b直接枚举每一个数 判断这个数中含有几个2 fori atobdo 求i中含2的个数t ans ans t 输出t 参考程序 vari a b ans longint beginreadln a b ans 0 fori atobdobeginifimod10 2theninc ans ifidiv10mod10 2theninc ans ifidiv10div10mod10 2theninc ans ifidiv10div10div10mod10 2theninc ans end writeln ans end 扫雷游戏 noip2015普及组第二题 扫雷游戏是一款十分经典的单机小游戏 在n行m列的雷区中有一些格子含有地雷 称之为地雷格 其他格子不含地雷 称之为非地雷格 玩家翻开一个非地雷格时 该格将会出现一个数字 提示周围格子中有多少个是地雷格 游戏的目标是在不翻出任何地雷格的条件下 找出所有的非地雷格 现在给出n行m列的雷区中的地雷分布 要求计算出每个非地雷格周围的地雷格数 注 一个格子的周围格子包括其上 下 左 右 左上 右上 左下 右下八个方向上与之直接相邻的格子 扫雷游戏 noip2015普及组第二题 输入样例133 输入样例223 输出样例1mine out 102211 1输出样例2mine out2 1 21 对于100 的数据 1 n 100 1 m 100 问题分析 本题也是简单的枚举类试题 我们从雷区的第一行第一列 1 1 开始 判断它周围有多少个地雷 由于本题读入的是字符 读入时需要注意 readln n m fori 1tondobeginforj 1tomdoread a i j readln end 问题分析 一个格子的周围格子包括其上 下 左 右 左上 右上 左下 右下八个方向上与之直接相邻的格子 判断如下 ifa i j 1 theninc s ifa i j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j theninc s ifa i 1 j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j theninc s 参考程序 vari j n m s longint a array 0 105 0 105 ofchar beginreadln n m fori 1tondobeginforj 1tomdoread a i j readln end fori 1tondobeginforj 1tomdobegins 0 ifa i j thenwrite a i j elsebeginifa i j 1 theninc s ifa i j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j theninc s ifa i 1 j 1 theninc s ifa i 1 j 1 theninc s ifa i 1 j theninc s write s end end writeln end end 比例简化 noip2014普及组第二题 在社交媒体上 经常会看到针对某一个观点同意与否的民意调查以及结果 例如 对某一观点表示支持的有1498人 反对的有902人 那么赞同与反对的比例可以简单的记为1498 902 不过 如果把调查结果就以这种方式呈现出来 大多数人肯定不会满意 因为这个比例的数值太大 难以一眼看出它们的关系 对于上面这个例子 如果把比例记为5 3 虽然与真实结果有一定的误差 但依然能够较为准确地反映调查结果 同时也显得比较直观 现给出支持人数A 反对人数B 以及一个上限L 请你将A比B化简为A 比B 要求在A 和B 均不大于L且A 和B 互质 两个整数的最大公约数是1 的前提下 A B A B且A B A B的值尽可能小 比例简化 noip2014普及组第二题 输入格式输入共一行 包含三个整数A B L 每两个整数之间用一个空格隔开 分别表示支持人数 反对人数以及上限 输出格式输出共一行 包含两个整数A B 中间用一个空格隔开 表示化简后的比例 样例输入149890210样例输出53 比例简化试题分析 读入a b L后 从1到L分别枚举a 和b 判断a 和b 是否合法 合法的话就记录下来 输入a b L fori 1toLdoforj 1toLdoifi j合法then ansx i ansy j 输出ansx ansy 比例简化试题分析 程序的关键在于如何判断i j合法 if gcd i j 1 and i j a b thenifi j a b minnthenbeginminn i j a b ansx i ansy j end 条件1 i和j互质 条件2 i j的值大于等于A B的值 条件3 i j A B的值尽可能小 比例简化参考程序 vara b L i j ansx ansy longint minn real functiongcd x y longint longint beginify 0thenexit x gcd gcd y xmody end beginreadln a b L minn 99999999 fori 1toLdoforj 1toLdoif gcd i j 1 and i j a b thenifi j a b minnthenbeginminn i j a b ansx i ansy j end writeln ansx ansy end 二 模拟类试题 有些问题 我们很难建立数学模型 或者很难用计算机建立递推 递归 枚举 回溯法等算法 在这种情况下 一般采用模拟策略 所谓模拟策略就是模拟某个过程 通过改变数学模型的各种参数 进而观察变更这些参数所引起过程状态的变化 由此展开算法设计 金币 noip2015普及组第一题 国王将金币作为工资 发放给忠诚的骑士 第一天 骑士收到一枚金币 之后两天 第二天和第三天 每天收到两枚金币 之后三天 第四 五 六天 每天收到三枚金币 之后四天 第七 八 九 十天 每天收到四枚金币 这种工资发放模式会一直这样延续下去 当连续N天每天收到N枚金币后 骑士会在之后的连续N 1天里 每天收到N 1枚金币 请计算在前K天里 骑士一共获得了多少金币 输入格式 输入文件只有1行 包含一个正整数K 表示发放金币的天数 输出格式 输出文件只有1行 包含一个正整数 即骑士收到的金币数 输入输出样例输入样例 1000输出样例 29820 试题分析 本题直接模拟即可 定义变量时注意不要混淆了 i代表枚举的天数 t代表连续的天数 也是每天收到的金币数 s收到的金币总数 读入天数k i 1 t 1 s 0 whileikthenbreak t t 1 输出s 参考程序 vari j k s t longint beginreadln k i 1 t 1 s 0 whileikthenbreak end inc t end writeln s end 螺旋方阵 noip2014普及组第三题 一个n行n列的螺旋矩阵可由如下方法生成 从矩阵的左上角 第1行第1列 出发 初始时向右移动 如果前方是未曾经过的格子 则继续前进 否则右转 重复上述操作直至经过矩阵中所有格子 根据经过顺序 在格子中依次填入1 2 3 便构成了一个螺旋矩阵 现给出矩阵大小n以及i和j 请你求出该矩阵中第i行第j列的数是多少 下图是一个n 4时的螺旋矩阵 螺旋方阵 noip2014普及组第三题 输入格式输入共一行 包含三个整数n i j 每两个整数之间用一个空格隔开 分别表示矩阵大小 待求的数所在的行号和列号 输出格式输出共一行 包含一个整数 表示相应矩阵中第i行第j列的数 样例输入 423样例输出 14对于50 的数据 1 n 100 对于100 的数据 1 n 30 000 1 i n 1 j n 螺旋方阵试题分析 本题首先让我们想到传统的模拟 从 1 1 开始往数组中填充数字 但对于 30000 30000 的数组 直接爆零 对于读入的n x y 先判断 x y 在第几圈 再模拟圈内的数字 螺旋方阵试题分析 如 n 4 2 2 在第2圈 3 1 在第1圈 n 6 4 5 在第2圈 圈数q min x y n x 1 n y 1 即目标位置到四个边界距离的最小值 螺旋方阵试题分析 圈数q求出后 前q圈的数字总和很容易求出来 对于任何一个方阵 第1圈有4n 4个数 第2圈有4 n 2 4个数 第3圈有4 n 4 4个数 第q圈有4 n q n 1 4个数 螺旋方阵试题分析 前1圈有4n 4个数 前2圈有4n 4 4 n 2 4 2 4n 2 4 个数 前3圈有4 n 4 4 2 4n 8 3 4n 3 4 个数 前q圈有q 4n 4q 个数 螺旋方阵试题分析 目标位置 i j 到底在当前这一圈的第几个位置 如目标数26所在的位置 4 5 在第2圈的什么位置 分两种情况 1 目标数 i j 在上行或右行 i j 2q 12 目标数 i j 在下行或左行 距离第一个数的距离i j 2q 1 螺旋方阵参考程序 varn i j q ans longint functionmin a b longint longint beginifa bthenexit a elseexit b end beginreadln n i j q min i min j min n i 1 n j 1 ifi jthenans q 4 n 1 4 q 10 q 4 n 3 i jelseans q 4 n 4 q 2 q 1 i j writeln ans end 计数问题 noip2013普及组第一题 试计算在区间1到n的所有整数中 数字x 0 x 9 共出现了多少次 例如 在1到11中 即在1 2 3 4 5 6 7 8 9 10 11中 数字1出现了4次 输入 输入共1行 包含2个整数n x 之间用一个空格隔开 输出 输出共1行 包含一个整数 表示x出现的次数 输入示例 111输出示例 4其他说明 对于100 的数据 1 n 1 000 000 0 x 9 计数问题试题分析 这道题入门难度 直接模拟 循环1到n之间的所有数 对每个数的每位判断即可 读入n x fori 1tondo k i whilek的每一位jdoifj xtheninc ans 输出ans 计数问题参考程序 这道题入门难度 直接模拟 循环1到n之间的所有数 对每个数的每位判断即可 vari n x k ans longint beginreadln n x ans 0 fori 1tondobegink i whilek 0dobeginifkmod10 xtheninc ans k kdiv10 end end writeln ans end 寻宝 noip2012普及组第二题 传说很遥远的藏宝楼顶层藏着诱人的宝藏 小明历尽千辛万苦终于找到传说中的这个藏宝楼 藏宝楼的门口竖着一个木板 上面写有几个大字 寻宝说明书 说明书的内容如下 藏宝楼共有N 1层 最上面一层是顶层 顶层有一个房间里面藏着宝藏 除了顶层外 藏宝楼另有N层 每层M个房间 这M个房间围成一圈并按逆时针方向依次编号为0 M 1 其中一些房间有通往上一层的楼梯 每层楼的楼梯设计可能不同 每个房间里有一个指示牌 指示牌上有一个数字x 表示从这个房间开始按逆时针方向选择第x个有楼梯的房间 假定该房间的编号为k 从该房间上楼 上楼后到达上一层的k号房间 比如当前房间的指示牌上写着2 则按逆时针方向开始尝试 找到第2个有楼梯的房间 从该房间上楼 如果当前房间本身就有楼梯通向上层 该房间作为第一个有楼梯的房间 寻宝 noip2012普及组第二题 寻宝说明书的最后用红色大号字体写着 寻宝须知 帮助你找到每层上楼房间的指示牌上的数字 即每层第一个进入的房间内指示牌上的数字 总和为打开宝箱的密钥 请帮助小明算出这个打开宝箱的密钥 输入 第一行2个整数N和M 之间用一个空格隔开 N表示除了顶层外藏宝楼共N层楼 M表示除顶层外每层楼有M个房间 接下来N M行 每行两个整数 之间用一个空格隔开 每行描述一个房间内的情况 其中第 i 1 M j行表示第i层j 1号房间的情况 i 1 2 N j 1 2 M 第一个整数表示该房间是否有楼梯通往上一层 0表示没有 1表示有 第二个整数表示指示牌上的数字 注意 从j号房间的楼梯爬到上一层到达的房间一定也是j号房间 最后一行 一个整数 表示小明从藏宝楼底层的几号房间进入开始寻宝 注 房间编号从0开始 寻宝 noip2012普及组第二题 输出 输出只有一行 一个整数 表示打开宝箱的密钥 这个数可能会很大 请输出对20123取模的结果即可 输入输出样例 treasure intreasure out2351203140115121 寻宝 noip2012普及组第二题 输入输出样例说明 第一层 0号房间 有楼梯通往上层 指示牌上的数字是2 1号房间 无楼梯通往上层 指示牌上的数字是3 2号房间 有楼梯通往上层 指示牌上的数字是4 第二层 0号房间 无楼梯通往上层 指示牌上的数字是1 1号房间 有楼梯通往上层 指示牌上的数字是5 2号房间 有楼梯通往上层 指示牌上的数字是2 小明首先进入第一层 底层 的1号房间 记下指示牌上的数字为3 然后从这个房间开始 沿逆时针方向选择第3个有楼梯的房间2号房间进入 上楼后到达第二层的2号房间 记下指示牌上的数字为2 由于当前房间本身有楼梯通向上层 该房间作为第一个有楼梯的房间 因此 此时沿逆时针方向选择第2个有楼梯的房间即为1号房间 进入后上楼梯到达顶层 这时把上述记下的指示牌上的数字加起来 即3 2 5 所以打开宝箱的密钥就是5 寻宝试题分析 题目大意 n层楼 每层m个房间 每个房间有一个号码 楼梯 从底楼出发 如果该房间有楼梯 直接上楼 否则走到该层下个指定的房间 将每一层第一个到达的房间号加起来就是答案 寻宝试题分析 我们把每一层楼看成一个圈 完全模拟一下小明的行走路线即可 注意细节 1 房间号从0开始 所以读入时要注意 readln n m fori 1tondoforj 0tom 1do读入楼梯和号码 寻宝试题分析 我们把每一层楼看成一个圈 完全模拟一下小明的行走路线即可 注意细节 1 房间号从0开始 所以读入时要注意 2 读入时统计每一层有多少个带楼梯的房间 readln n m fori 1tondoforj 0tom 1dobeginreadln stair i j num i j ifstair i j 1theninc sum i end 寻宝试题分析 我们把每一层楼看成一个圈 完全模拟一下小明的行走路线即可 注意细节 1 房间号从0开始 所以读入时要注意 2 读入时统计每一层有多少个带楼梯的房间 3 理解 从这个房间开始按逆时针方向选择第x个有楼梯的房间 假如当前房间没有楼梯 指示牌上的号为j whilej 0dobeginifstair i k 1thendec j ifj 0thenk k 1 modm end 寻宝参考程序 vari j n m k ans longint num array 0 10001 0 101 oflongint sum array 0 10001 oflongint stair array 0 10001 0 101 of0 1 beginreadln n m fillchar sum sizeof sum 0 fori 1tondoforj 0tom 1dobeginreadln stair i j num i j ifstair i j 1theninc sum i end readln k ans 0 fori 1tondobeginans ans num i k mod20123 num i k num i k modsum i ifnum i k 0thennum i k sum i j num i k whilej 0dobeginifstair i k 1thendec j ifj 0thenk k 1 modm end end writeln ans end 接水问题 noip2010普及组第二题 学校里有一个水房 水房里一共装有m个龙头可供同学们打开水 每个龙头每秒钟的供水量相等 均为1 现在有n名同学准备接水 他们的初始接水顺序已经确定 将这些同学按接水顺序从1到n编号 i号同学的接水量为wi 接水开始时 1到m号同学各占一个水龙头 并同时打开水龙头接水 当其中某名同学j完成其接水量要求wj后 下一名排队等候接水的同学k马上接替j同学的位置开始接水 这个换人的过程是瞬间完成的 且没有任何水的浪费 即j同学第x秒结束时完成接水 则k同学第x 1秒立刻开始接水 若当前接水人数n不足m 则只有n个龙头供水 其它m n个龙头关闭 现在给出n名同学的接水量 按照上述接水规则 问所有同学都接完水需要多少秒 接水问题 noip2010普及组第二题 输入第1行2个整数n和m 用一个空格隔开 分别表示接水人数和龙头个数 第2行n个整数w1 w2 wn 每两个整数之间用一个空格隔开 wi表示i号同学的接水量 输出输出只有一行 1个整数 表示接水所需的总时间 样例输入 5344121样例输出 4 接水问题试题分析 题目大意 n个人排队顺序接水 共m个水龙头 求接完水需要最少的秒数 本题直接模拟即可 有的选手在考试中使用秒去枚举 结果严重超时 对于每一个人 选择这m个水龙头中接水量最小的去接 最后输出这m个水龙头中接水量最大的 接水问题参考程序 vara array 0 10001 oflongint s array 0 101 oflongint n m i j k ans minn longint beginreadln n m fori 1tondoread a i fillchar s sizeof s 0 fori 1tondobeginminn 9999999 forj 1tomdoifs j ansthenans s i writeln ans end 三 字符串类试题 对于字符串 表达式的求解 大整数的处理等等 我们经常采用字符串来处理 字符串处理常见函数和过程 length delete pos val str 数字反转 noip2011普及组第一题 给定一个整数 请将该数各个位上数字反转得到一个新数 新数也应满足整数的常见形式 即除非给定的原数为零 否则反转后得到的新数的最高位数字不应为零 如 输入 380 输出 83 输入输入共1行 一个整数N 输出输出共1行 一个整数 表示反转后的新数 样例输入123样例输出321 数字反转试题分析 方法1 直接降位取个位降位 ndiv10取个位 nmod10注意删去末尾的0 缺点 数不能太大 容易溢出 数字反转试题分析 varn longint beginreadln n ifn0dobeginwrite nmod10 n ndiv10 end end end 数字反转试题分析 方法2 字符串注意1 负数的处理 ifs 1 thenbeginwrite delete s 1 1 end 数字反转试题分析 方法2 字符串注意1 负数的处理注意2 末尾0的处理 len length s while s len 0 dodec len fori lendownto1dowrite s i 数字反转参考程序 vars ansistring i len longint beginreadln s ifs 1 thenbeginwrite delete s 1 1 end len length s while s len 0 dodec len fori lendownto1dowrite s i end 统计单词个数 noip2011普及组第二题 一般的文本编辑器都有查找单词的功能 该功能可以快速定位特定单词在文章中的位置 有的还能统计出特定单词在文章中出现的次数 现在 请你编程实现这一功能 具体要求是 给定一个单词 请你输出它在给定的文章中出现的次数和第一次出现的位置 注意 匹配单词时 不区分大小写 但要求完全匹配 即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同 参见样例1 如果给定单词仅是文章中某一单词的一部分则不算匹配 参见样例2 统计单词个数 noip2011普及组第二题 输入格式第1行为一个字符串 其中只含字母 表示给定单词 第2行为一个字符串 其中只可能包含字母和空格 表示给定的文章 输出格式只有一行 如果在文章中找到给定单词则输出两个整数 两个整数之间用一个空格隔开 分别是单词在文章中出现的次数和第一次出现的位置 即在文章中第一次出现时 单词首字母在文章中的位置 位置从0开始 如果单词在文章中没有出现 则直接输出一个整数 1 统计单词个数 noip2011普及组第二题 样例输入1 Totobeornottobeisaquestion样例输出1 20样例输入2 toDidtheOttomanEmpireloseitspoweratthattime样例输出2 1 输入输出样例2说明 表示给定的单词to在文章中没有出现 输出整数 1 注释说明1 单词长度 10 1 文章长度 1 000 000 统计单词个数试题分析 本题是简单的字符串处理 读入单词和文章 字符串 后 可以把单词和文章全部转换成大写 或小写 然后循环在文章中对单词进行查找 找到就存储位置 并统计找到的次数 转换成大写有两种方法 方法1 利用ord 和chr 函数逐个字符转换 fori 1tolength s doifs i a thens i chr ord s i 32 方法2 利用upcase 函数直接转换 s upcase s 统计单词个数试题分析 本题还有一个问题需要处理 查找的单词s1只是文章s中某个单词的一部分 如 ToDidtheOttomanEmpire处理方法 读入单词s1后 在s1的两端各添加一个空格 s1 s1 统计单词个数参考程序 vars1 s ansistring i p len ans longint beginreadln s1 单词readln s 文章s1 upcase s1 s upcase s p 1 ans 0 len length s1 fori 1tolength s len 1doifcopy s i len s1thenbeginifp 1thenp i 1 inc ans end ifp 1thenwrite p elsewrite ans p end 四 贪心类试题 从问题的某一个初始解出发 向给定的目标递推 推进的每一步不是依据某一固定的递推公式 而是做一个当时看似最佳的贪心选择 不断地将问题归纳为更小的相似的子问题 最终产生出一个全局最优解 排座椅 noip2008普及组第二题 上课的时候总有一些同学和前后左右的人交头接耳 这是令小学班主任十分头疼的一件事情 不过 班主任小雪发现了一些有趣的现象 当同学们的座次确定下来之后 只有有限的D对同学上课时会交头接耳 同学们在教室中坐成了M行N列 坐在第i行第j列的同学的位置是 i j 为了方便同学们进出 在教室中设置了K条横向的通道 L条纵向的通道 于是 聪明的小雪想到了一个办法 或许可以减少上课时学生交头接耳的问题 她打算重新摆放桌椅 改变同学们桌椅间通道的位置 因为如果一条通道隔开了两个会交头接耳的同学 那么他们就不会交头接耳了 请你帮忙给小雪编写一个程序 给出最好的通道划分方案 在该方案下 上课时交头接耳的学生对数最少 排座椅 noip2008普及组第二题 输入输入的第一行 有5个用空格隔开的整数 分别是M N K L D 2 N M 1000 0 K M 0 L N D 2000 接下来D行 每行有4个用空格隔开的整数 第i行的4个整数Xi Yi Pi Qi 表示坐在位置 Xi Yi 与 Pi Qi 的两个同学会交头接耳 输入保证他们前后相邻或者左右相邻 输入数据保证最优方案的唯一性 输出输出共两行 第一行包含K个整数 a1a2 aK 表示第a1行和a1 1行之间 第a2行和第a2 1行之间 第aK行和第aK 1行之间要开辟通道 其中ai ai 1 每两个整数之间用空格隔开 行尾没有空格 第二行包含L个整数 b1b2 bk 表示第b1列和b1 1列之间 第b2列和第b2 1列之间 第bL列和第bL 1列之间要开辟通道 其中bi bi 1 每两个整数之间用空格隔开 行尾没有空格 排座椅 noip2008普及组第二题 输入样例45123424323332524输出样例224 排座椅试题分析 贪心 题意 教室有m行n列 现在要划分k条横向通道 L条纵向的通道 交头接耳的学生位置 xi yi 和 pi qi 怎么划分通道 使得上课时交头接耳的学生对数最少 用row i 记录第i行与第i 1行之间有多少对交头接耳的 用col i 记录第i列与第i 1列有多少对交头接耳的 将row从大到小排序 前k个即为要隔开的行 将col从大到小排序 前L个即为要隔开的列 排座椅试题分析 程序的框架 读入m n k L d Fori 1tod 读入x y p q ifx ptheninc row min x p value elseinc col min y q value 对数组row按row value从大到小排序 对于数组row 1 到row k 按row no从小到大排序 输出row 1 row k 对数组col按col value从大到小排序 对于数组col 1 到col L 按col no从小到大排序 输出col 1 col L 排座椅参考程序 varm n t k L d i j x y p q maxx longint row col a array 0 1005 oflongint functionmin x y longint longint beginifx ythenexit y elseexit x end beginreadln m n k L d fillchar row sizeof row 0 fillchar col sizeof col 0 fori 1toddobeginreadln x y p q ifx ptheninc col min y q elseinc row min x p end t 0 whiletrow maxx thenmaxx i row maxx 1 inc t end t 0 whiletcol maxx thenmaxx i col maxx 1 inc t end fori 1tomdoifrow i 1thenwrite i writeln fori 1tondoifcol i 1thenwrite i writeln end 纪念品分组 noip2007普及组第二题 元旦快到了 校学生会让乐乐负责新年晚会的纪念品发放工作 为使得参加晚会的同学所获得的纪念品价值相对均衡 他要把购来的纪念品根据价格进行分组 但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数 为了保证在尽量短的时间内发完所有纪念品 乐乐希望分组的数目最少 你的任务是写一个程序 找出所有分组方案中分组数最少的一种 输出最少的分组数目 纪念品分组 noip2007普及组第二题 输入包含n 2行 第1行包括一个整数w 为每组纪念品价格之和的上眼 第2行为一个整数n 表示购来的纪念品的总件数G第3 n 2行每行包含一个正整数Pi 5 Pi w3 w表示所对应纪念品的价格 输出仅一行 包含一个整数 ep最少的分组数目合 纪念品分组 noip2007普及组第二题 样例输入 样例输出 10069902020305060708090100 的数据满足 1 n 30000 80 W 200 纪念品分组试题分析 算法 贪心先按n件纪念品的价值进行排序 贪心策略是价值最小的与价值最大的为一组 这样分组是最少的 纪念品分组试题分析 算法 贪心先按n件纪念品的价值进行排序 贪心策略是价值最小的与价值最大的为一组 这样分组是最少的 纪念品分组参考程序 vari j t m n left right ans longint a array 0 30001 oflongint beginreadln m n fori 1tondoreadln a i fori 1ton 1doforj i 1tondoifa i a j thenbegint a i a i a j a j t end ans 0 left 1 right n whileleft rightdobeginifa left a right mthenbegininc left dec right endelsedec right inc ans end ifleft righttheninc ans writeln ans end 六 简单动态规划类试题 动态规划是解决多阶段决策最优化问题的一种思想方法 一般我们从初始阶段出发 枚举每个阶段的所有状态 在状态转移的过程中 我们需要决策 根据每一步所选决策的不同 将随即引起状态的转移 最终在变化的状态中产生一个决策序列 动态规划就是为了使产生的决策序列在符合某种条件下达到最优 普及组一般考查的动态规划 01背包 最长上升子序列 一些简单的线性动规 守望者的逃离 noip2007普及组第三题 恶魔猎手尤迫安野心勃勃 他背叛了暗夜精灵 率深藏在海底的那加企图叛变 守望者在与尤迪安的交锋中遭遇了围杀 被困在一个荒芜的大岛上 为了杀死守望者 尤迪安开始对这个荒岛施咒 这座岛很快就会沉下去 到那时 岛上的所有人都会遇难 守望者的跑步速度 为17m s 以这样的速度是无法逃离荒岛的 庆幸的是守望者拥有闪烁法术 可在1s内移动60m 不过每次使用闪烁法术都会消耗魔法值10点 守望者的魔法值恢复的速度为4点 s 只有处在原地休息状态时才能恢复 现在已知守望者的魔法初值M 他所在的初始位置与岛的出口之间的距离S 岛沉没的时间T 你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛 若不能逃出 则输出守望者在剩下的时间内能走的最远距离 注意 守望者跑步 闪烁或休息活动均以秒 s 为单位 且每次活动的持续时间为整数秒 距离的单位为米 m 守望者的逃离 noip2007普及组第三题 输入输入文件escape in仅一行 包括空格隔开的三个非负整数M S T 输出输出文件escape out包含两行 第1行为字符串 Yes 或 No 区分大小写 即守望者是否能逃离荒岛 第2行包含一个整数 第一行为 Yes 区分大小写 时表示守望着逃离荒岛的最短时间第一行为 No 区分大小写 时表示守望者能走的最远距离 样例输入392004样例输出No197提示100 的数据满足 1 T 300000 0 M 10001 S 10 8 守望者的逃离试题分析 题目大意 一个人在t时间内是否能够行走的s米的距离 行走的方式有两种 1 使用魔法 每秒60米 缺点每秒耗费10点魔法值 2 跑步 每秒17米 守望者的逃离试题分析 算法 贪心 背包型动态规划 贪心的策略 有魔法的情况下 肯定先用魔法跑 这样跑的快 如果魔法不够 那么我们利用背包模型 只有在下列两种选择中选择其中一种 1 使用魔法2 跑步 守望者的逃离试题分析 令f i 表示前i秒利用魔法行走的距离 dp i 表示利用魔法或者跑步行走的最大距离 很容易求出1到t的f i 的值 fori 1totdo ifmagic 10then magic magic 10 f i f i 1 60 else magic magic 4 f i f i 1 守望者的逃离试题分析 下面求dp i 01背包 dp i max dp i 1 17 f i 守望者的逃离参考程序 小朋友的数字 noip2013普及组第三题 有n个小朋友排成一列 每个小朋友手上都有一个数字 这个数字可正可负 规定每个小朋友的特征值等于排在他前面 包括他本人 的小朋友中连续若干个 最少有一个 小朋友手上的数字之和的最大值 作为这些小朋友的老师 你需要给每个小朋友一个分数 分数是这样规定的 第一个小朋友的分数是他的特征值 其它小朋友的分数为排在他前面的所有小朋友中 不包括他本人 小朋友分数加上其特征值的最大值 请计算所有小朋友分数的最大值 输出时保持最大值的符号 将其绝对值对p取模后输出 小朋友的数字 noip2013普及组第三题 输入格式第一行包含两个正整数n p 之间用一个空格隔开 第二行包含n个数 每两个整数之间用一个空格隔开 表示每个小朋友手上的数字 输出格式输出只有一行 包含一个整数 表示最大分数对p取模的结果 样例输入1599712345样例输出121 小朋友的数字试题分析 主要考查选手的语文理解能力 关键把题读懂 需要理解的两个值 特征值 前面连续若干个数字和的最大值 分数 前面每个小朋友的分数 特征值的最大值 小朋友的数字试题分析 算法 动态规划 贪心 求小朋友的特征值需要求最大子段和 fori 1tondodp i max dp i 1 a i a i 每个小朋友的特征值t i fori 1tondo dp i max dp i 1 a i a i t i max t i 1 dp i 小朋友的数字试题分析 算法 动态规划 贪心 求小朋友的分数需要贪心 如果第一个小朋友的分数 特征值为负数 那么后面所有小朋友的分数 第一个小朋友的分数 特征值 否则 前一个小朋友的分数 特征值 fori 2tondoifte 1 fen 1 0thenfen i te 1 fen 1 elsefen i te i 1 fen i 1 采药 noip2005普及组第三题 辰辰是个天资聪颖的孩子 他的梦想是成为世界上最伟大的医师 为此 他想拜附近最有威望的医师为师 医师为了判断他的资质 给他出了一个难题 医师把他带到一个到处都是草药的山洞里对他说 孩子 这个山洞里有一些不同的草药 采每一株都需要一些时间 每一株也有它自身的价值 我会给你一段时间 在这段时间里 你可以采到一些草药 如果你是一个聪明的孩子 你应该可以让采到的草药的总价值最大 采药 noip2005普及组第三题 输入格式 第一行有两个整数T和M T代表总共能够用来采药的时间 M代表山洞里的草药的数目 接下来的M行每行包括两个在1到100之间 包括1和100 的整数 分别表示采摘某株草药的时间和这株草药的价值 输出格式 一行只包含一个整数 表示在规定的时间内 可以采到的草药的最大总价值 输入样例 7037110069112输出样例 3 1 T 10