noip复赛总结归纳(c++)

noip 复赛总结归纳 2010 至 2015 年 c 普及组复赛试题 一 题目 1 数字统计 two pas c cpp 问题描述 请统计某个给定范围 L R 的所有整数中 数字 2 出现的次数 比如给定范围 2 22 数字 2 在数 2 中出现了 1 次 在数 12 中出现 1 次 在数 20 中出现 1 次 在数 21 中出现 1 次 在数 22 中出现 2 次 所以数字 2 在该范围内一共出现了 6 次 输入 输入文件名为 two in 输入共 1 行 为两个正整数 L 和 R 之间用一个空格隔开 输出 输出文件名为 two out 输出共 1 行 表示数字 2 出现的次数 输入输出样例 1 two in two out 2 22 6 输入输出样例 2 two in two out 2 100 20 数据范围 1 L R 10000 算法 把每一位分出来 一一判断 代码 include using namespace std int main int r l ans 0 scanf d d for int i r i0 把每一位分离 if num 10 2 ans num 10 printf d ans return 0 年份 2010 二 题目 2 接水问题 water pas c cpp 问题描述 学校里有一个水房 水房里一共装有 m 个龙头可供同学们打开水 每个龙头每 秒钟的供水量相等 均为 1 现在有 n 名同学准备接水 他们的初始接水顺序已经确定 将这些同学按接水 顺序从 1 到 n 编号 i 号同学的接水量为 wi 接水开始时 1 到 m 号同学各 占一个水龙头 并同时打开水龙头接水 当其中某名同学 j 完成其接水量要求 wj 后 下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水 这个 换人的过程是瞬间完成的 且没有任何水的浪费 即 j 同学第 x 秒结束时完成 接水 则 k 同学第 x 1 秒立刻开始接水 若当前接水人数 n 不足 m 则只有 n 个龙头供水 其它 m n 个龙头关闭 现在给出 n 名同学的接水量 按照上述接水规则 问所有同学都接完水需要多 少秒 输入 输入文件名为 water in 第 1 行 2 个整数 n 和 m 用一个空格隔开 分别表示接水人数和龙头个数 第 2 行 n 个整数 w1 w2 wn 每两个整数之间用一个空格隔开 wi 表 示 i 号同学的接水量 输出 输出文件名为 water out 输出只有一行 1 个整数 表示接水所需的总时间 输入输出样例 1 water in water out 5 3 4 4 4 1 2 1 输入输出样例 1 说明 第 1 秒 3 人接水 第 1 秒结束时 1 2 3 号同学每人的已接水量为 1 3 号同学接完水 4 号同学接替 3 号同学开始接水 第 2 秒 3 人接水 第 2 秒结束时 1 2 号同学每人的已接水量为 2 4 号 同学的已接水量为 1 第 3 秒 3 人接水 第 3 秒结束时 1 2 号同学每人的已接水量为 3 4 号 同学的已接水量为 2 4 号 i 同学接完水 5 号同学接替 4 号同 i 学开始接水 第 4 秒 3 人接水 第 4 秒结束时 1 2 号同学每人的已接水量为 4 5 号 同学的已接水量为 1 1 2 5 号 i 同学接完水 即所有人完成接水 总接水时间为 4 秒 输入输出样例 2 water in water out 8 4 23 71 87 32 70 93 80 76 163 数据范围 1 n 10000 1 m 100 且 m n 1 wi 100 算法 把人数分为两部分 一人对一个水龙头 作为第一部分 剩下是第二 部分的 每一次从第一部分找一个时间最少人 把第二部分的一个人加进去 代码 include int w 10005 int main int i j m n scanf d d for i 1 i m i 输入 1 到 m 的数据到 w i scanf d for i n 1 i m i int k 1 假设 w k w 1 是最小 for j 2 jw j k j w k w i int k 1 for i 2 i n i if w k w i k i printf d w k return 0 年份 2010 三 题目 三国游戏 sanguo pas c cpp 问题描述 小涵很喜欢电脑游戏 这些天他正在玩一个叫做 三国 的游戏 在游戏中 小涵和计算机各执一方 组建各自的军队进行对战 游戏中共有 N 位武将 N 为偶数且不小于 4 任意两个武将之间有一个 默契值 表示若 此两位武将作为一对组合作战时 该组合的威力有多大 游戏开始前 所有武 将都是自由的 称为自由武将 一旦某个自由武将被选中作为某方军队的一员 那么他就不再是自由武将了 换句话说 所谓的自由武将不属于任何一方 游戏开始 小涵和计算机要从自由武将中挑选武将组成自己的军队 规则如下 小涵先从自由武将中选出一个加入自己的军队 然后计算机也从自由武将中选 出一个加入计算机方的军队 接下来一直按照 小涵 计算机 小涵 的顺序选择武将 直到所有的武将被双方均分完 然后 程序自动从双方军队 中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武 拥有更 高默契值的一对武将组合获胜 表示两军交战 拥有获胜武将组合的一方获胜 已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合 它 采取的具体策略如下 任何时刻 轮到计算机挑选时 它会尝试将对手军队中 的每个武将与当前每个自由武将进行一一配对 找出所有配对中默契值最高的 那对武将组合 并将该组合中的自由武将选入自己的军队 下面举例说明计算机的选将策略 例如 游戏中一共有 6 个武将 他们相互之 间的默契值如下表所示 双方选将过程如下所示 小涵 轮到计算机时可选的自由武将 计算机 计算机选将说明 第一轮 5 1 2 3 4 6 4 小涵手中 5 号武将与 4 号的默契值昀高 所以 选择 4 号 第二轮 5 3 1 2 6 4 1 小涵手中的 5 号和 3 号武将与自由武将中配对 可产生的昀大默契值为 29 是由 5 号与 1 号配对产生的 因此计算机选择 1 号 第三轮 5 3 6 2 4 1 2 小涵想知道 如果计算机在一局游戏中始终坚持上面这个策略 那么自己有没 有可能必胜 如果有 在所有可能的胜利结局中 自己那对用于比武的武将组 合的默契值最大是多少 假设整个游戏过程中 对战双方任何时候均能看到自由武将队中的武将和对方 军队的武将 为了简化问题 保证对于不同的武将组合 其默契值均不相同 输入 输入文件名为 sanguo in 共 N 行 第一行为一个偶数 N 表示武将的个数 第 2 行到第 N 行里 第 i 1 行有 N i 个非负整数 每两个数之间用一个 空格隔开 表示 i 号武将和 i 1 i 2 N 号武将之间的默契值 0 默契值 1 000 000 000 输出 输出文件 sanguo out 共 1 或 2 行 若对于给定的游戏输入 存在可以让小涵获胜的选将顺序 则输出 1 并另起 一行输出所有获胜的情况中 小涵最终选出的武将组合的最大默契值 如果不存在可以让小涵获胜的选将顺序 则输出 0 输入输出样例 1 sanguo in sanguo out 6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12 1 32 输入输出样例说明 首先小涵拿走 5 号武将 计算机发现 5 号武将和剩下武将中的 4 号默契值最 高 于是拿走 4 号 小涵接着拿走 3 号 计算机发现 3 5 号武将之一和剩下 的武将配对的所有组合中 5 号和 1 号默契值最高 于是拿走 1 号 小涵接着 拿走 2 号 计算机最后拿走 6 号 在小涵手里的 2 3 5 号武将中 3 号和 5 号配合最好 默契值为 32 而计算机能推出的最好组合为 1 号和 6 号 默契 值为 27 结果为小涵胜 并且这个组合是小涵用尽所有方法能取到的最好组合 输入输出样例 2 sanguo in sanguo out 8 42 24 10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 1 77 数据范围 对于 40 的数据有 N 10 对于 70 的数据有 N 18 对于 100 的数据有 N 500 算法 每个武将先找第一大 删掉 再找第一大 就是找第二大 看看是 否比现有答案大 人是必胜的 直接输 1 和答案 代码 include include include include include using namespace std int n a 1000 1000 ans maxx int main scanf d for int i 1 i n 1 i 输入 a 作为邻接矩阵 for int j i 1 j n j if i j continue scanf d a j i a i j for int i 1 i n i for int j 1 ja i maxx maxx j a i maxx 0 for int j 1 j n j ans max ans a i j maxx 1 printf 1 n d ans return 0 年份 2010 四 题目 1 数字反转 reverse cpp c pas 问题描述 给定一个整数 请将该数各个位上数字反转得到一个新数 新数也应满足整数 的常见形式 即除非给定的原数为零 否则反转后得到的新数的最高位数字不 应为零 参见样例 2 输入 输入文件名为 reverse in 输入共 1 行 一个整数 N 输出 输出文件名为 reverse out 输出共 1 行 一个整数 表示反转后的 新数 输入输出样例 1 123 321 输入输出样例 2 380 83 数据范围 1 000 000 000 N 1 000 000 000 算法 其实就是逆序输出一个字符串 但要判断正负 特判 0 另外要删除 前导 0 这题就是考字符串思想 代码 include include include include include using namespace std int main char a 20120 gets a int b len strlen a if a 0 0 cout 0 return 0 if a 0 cout 0 i if f 1 a i 0 return 0 年份 2011 五 题目 2 统计单词数 stat cpp c pas 问题描述 一般的文本编辑器都有查找单词的功能 该功能可以快速定位特定单词在文章 中的位置 有的还能统计出特定单词在文章中出现的次数 现在 请你编程实 现这一功能 具体要求是 给定一个单词 请你输出它在给定的文章中出现的 次数和第一次出现的位置 注意 匹配单词时 不区分大小写 但要求完全匹 配 即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相 同 参见样例 1 如果给定单词仅是文章中某一单词的一部分则不算匹配 参见样例 2 输入 输入文件名为 stat in 2 行 第 1 行为一个字符串 其中只含字母 表示给 定单词 第 2 行为一个字符串 其中只可能包含字母和空格 表示给定的文章 输出 输出文件名为 stat out 只有一行 如果在文章中找到给定单词则输出两个整 数 两个整数之间用一个空格隔开 分别是单词在文章中出现的次数和第一次 出现的位置 即在文章中第一次出现时 单词首字母在文章中的位置 位置从 0 开始 如果单词在文章中没有出现 则直接输出一个整数 1 输入输出样例 1 stat in stat out To to be or not to be is a question 2 0 输入输出样例 1 说明 输出结果表示给定的单词 To 在文章中出现两次 第一次出现的位置为 0 输入输出样例 2 stat in stat out to Did the Ottoman Empire lose its power at that time 1 输入输出样例 2 说明 表示给定的单词 to 在文章中没有出现 输出整数 1 数据范围 1 单词长度 10 1 文章长度 1 000 000 算法 每遇到一个单词就和原来的进行比对 比对成功后再判断之后是否是 空格 代码 include include include include using namespace std int main void char a 1010100 ch 1010 gets ch gets a for int i 0 i a for int i 0 i a int j 0 ans 0 pl 1111 for int i 0 i strlen a i if a i ch j j else j 0 if j strlen ch if pl 1111 pl i strlen ch 1 if ans 0 cout ans pl else cout 1 return 0 年份 2011 六 题目 1 质因数分解 prime cpp c pas 问题描述 已知正整数 n 是两个不同的质数的乘积 试求出较大的那个质数 输入 输入文件名为 prime in 输入只有一行 包含一个正整数 n 输出 输出文件名为 prime out 输出只有一行 包含一个正整数 p 即较大的那个质数 输入输出样例 prime in prime out 21 7 数据范围 对于 60 的数据 6 n 1000 对于 100 的数据 6 n 2 109 算法 题目说这个数是两个质数的乘积 所以它只有两个因数 我们只要 从 1 搜到 sqrt n 找出小的那个因数 再用原数除以它就可以了 代码 include include int main int n scanf d for int i 2 ii printf d n n return 0 else printf d n i return 0 年份 2012 七 题目 2 寻宝 treasure cpp c pas 问题描述 传说很遥远的藏宝楼顶层藏着诱人的宝藏 小明历尽千辛万苦终于找到传说中 的这个藏宝楼 藏宝楼的门口竖着一个木板 上面写有几个大字 寻宝说明书 说明书的内容如下 藏宝楼共有 N 1 层 最上面一层是顶层 顶层有一个房间里面藏着宝藏 除了 顶层外 藏宝楼另有 N 层 每层 M 个房间 这 M 个房间围成一圈并按逆时针 方向依次编号为 0 M 1 其中一些房间有通往上一层的楼梯 每层楼的楼 梯设计可能不同 每个房间里有一个指示牌 指示牌上有一个数字 x 表示从 这个房间开始按逆时针方向选择第 x 个有楼梯的房间 假定该房间的编号为 k 从该房间上楼 上楼后到达上一层的 k 号房间 比如当前房间的指示牌 上写着 2 则按逆时针方向开始尝试 找到第 2 个有楼梯的房间 从该房间上 楼 如果当前房间本身就有楼梯通向上层 该房间作为第一个有楼梯的房间 寻宝说明书的最后用红色大号字体写着 寻宝须知 帮助你找到每层上楼房 间的指示 牌上的数字 即每层第一个进入的房间内指示牌上的数字 总和为打开宝箱的 密钥 请帮助小明算出这个打开宝箱的密钥 输入 输入文件为 treasure in 第一行 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 开始 输出 输出文件名为 treasure out 输出只有一行 一个整数 表示打开宝箱的密钥 这个数可能会很大 请输出 对 20123 取模的结果即可 输入输出样例 treasure in 2 3 1 2 0 3 1 4 0 1 1 5 1 2 1 输入输出样例说明 第一层 treasure out 5 0 号房间 有楼梯通往上层 指示牌上的数字是 2 1 号房间 无楼梯通往上层 指示牌上的数字是 3 2 号房间 有楼梯通往上层 指示牌上的数字是 4 第二层 0 号房间 无楼梯通往上层 指示牌上的数字是 1 1 号房间 有楼梯通往上层 指示牌上的数字是 5 2 号房间 有楼梯通往上层 指示牌上的数字是 2 小明首先进入第一层 底层 的 1 号房间 记下指示牌上的数字为 3 然后从 这个房间 开始 沿逆时针方向选择第 3 个有楼梯的房间 2 号房间进入 上楼后到达第 二层的 2 号房间 记下指示牌上的数字为 2 由于当前房间本身有楼梯通向上层 该房间作为第 一个有楼梯的 房间 因此 此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间 进 入后上楼梯到达 顶层 这时把上述记下的指示牌上的数字加起来 即 3 2 5 所以打开宝箱的 密钥就是 5 数据范围 对于 50 数据 有 0 N 1000 0 x 10000 对于 100 数据 有 0 N 10000 0 M 100 0 x 1 000 000 算法 利用递推 模拟每一层的情况 我用结构体储存每一间的情况 第二 重循环中 k 被多加了一次 应在外面去掉 为了形成一个环 每走一步都要 模一下房间数 代码 include include include using namespace std struct node int num int lt node room 1010 1010 int main int n m scanf d d for int i 1 i n i for int j 0 j room i j lt room i j num int k ans 0 cin k for int i 1 i n i ans room i k num int x 0 y room i k num for x y k k m if room i k lt 1 x k k m cout ans return 0 年份 2012 八 题目 小明的花店新开张 为了吸引顾客 他想在花店的门口摆上一排花 共 m 盆 通过调 查顾客的喜好 小明列出了顾客最喜欢的 n 种花 从 1 到 n 标号 为了在门 口展出更多种花 规定第 i 种花不能超过 ai 盆 摆花时同一种花放在一起 且不同种类的花需按标号的从小到大的顺序依次摆列 试编程计算 一共有多少种不同的摆花方案 输入 输入文件 flower in 共 2 行 第一行包含两个正整数 n 和 m 中间用一个空格隔开 第二行有 n 个整数 每两个整数之间用一个空格隔开 依次表示 a1 a2 an 输出 输出文件名为 flower out 输出只有一行 一个整数 表示有多少种方案 注意 因为方案数可能很多 请输出 方案数对 1000007 取模的结果 输入输出样例 1 flower in 2 4 3 2 输入输出样例说明 flower out 2 有 2 种摆花的方案 分别是 1 1 1 2 1 1 2 2 括号里的 1 和 2 表示两种花 比如第一个方案是前三个位置摆第一种花 第四个位置摆第二种花 数据范围 对于 20 数据 有 0 n 8 0 m 8 0 ai 8 对于 50 数据 有 0 n 20 0 m 20 0 ai 20 对于 100 数据 有 0 n 100 0 m 100 0 ai 100 算法 用 dp 解决 有一个规律 当种数固定时 摆 m 盆花的方案数是从 1 盆 到 n 1 盆的方案数总和 种数为 n 时 按照上一个步骤从一盆做到 m 盆 用得 到的新数据加到旧数据上 但一定要从上往下做 否则旧数据会被改变 第一 个循环控制种数 第二个从上往下控制盆数 第三个循环为了是为了加上它之 前的所有数据 最后记得要把初始值 dp 0 设为 1 否则没有数据出得来 代码 include include include include using namespace std int a 1050 dp 1050 n m int main scanf d d for int i 1 i n i scanf d memset dp 0 sizeof dp dp 0 1 for int i 1 i 0 j for int k 1 k min a i j k dp j dp j dp j k 1000007 printf d dp m 1000007 年份 2012 九 题目 记数问题 NOIP 普及组 2013 第一题 count cpp c pas 描述 试计算在区间 1 到 n 的所有整数中 数字 x 0 x 9 共出现了多少次 例 如 在 1 到 11 中 即在 1 2 3 4 5 6 7 8 9 10 11 中 数字 1 出 现了 4 次 输入 输入文件名为 count in 输入共 1 行 包含 2 个整数 n x 之间用一个空格隔开 输出 输出文件名为 count out 输出共 1 行 包含一个整数 表示 x 出现的次数 输入输出样例 count in count out 11 1 4 限制 每个测试点 1s 数据说明 对于 100 的数据 1 n 1 000 000 0 x 9 算法 这一题数据不大 一个一个找就可以了 关键之处就是用 sprintf 转 化成字符数组一一判断 代码 include int main int n num i j ans 0 scanf d d char s 1000010 for i 1 i n i sprintf s 1 d i for j 1 s j j if s j num 48 ans printf d n ans return 0 年份 2013 十 题目 小朋友的数字 有 n 个小朋友排成一列 每个小朋友手上都有一个数字 这个数字可正可负 规定每个小朋友的特征值等于排在他前面 包括他本人 的小朋友中连续若干个 最少有一个 小朋友手上的数字之和的最大值 作为这些小朋友的老师 你需要给每个小朋友一个分数 分数是这样规定的 第一 个小朋友的分数是他的特征值 其它小朋友的分数为排在他前面的所有小朋友中 不包括他本人 小朋友分数加上其特征值的最大值 请计算所有小朋友分数的最大值 输出时保持最大值的符号 将其绝对值对 p 取 模后输出 格式 输入 输入文件为 number in 第一行包含两个正整数 n p 之间用一个空格隔开 第二行包含 n 个数 每两个整数之间用一个空格隔开 表示每个小朋友手上的数字 输出 输出文件名为 number out 输出只有一行 包含一个整数 表示最大分数对 p 取模的结果 输入输出样例 1 number in number out 5 997 21 1 2 3 4 5 输入输出样例说明 小朋友的特征值分别为 1 3 6 10 15 分数分别为 1 2 5 11 21 最大值 21 对 997 的模是 21 输入输出样例 2 number in number out 5 7 1 1 1 1 1 1 输入输出样例说明 小朋友的特征值分别为 1 1 1 1 1 分数分别为 1 2 2 2 2 最大值 1 对 7 的模为 1 输出 1 数据范围 对于 50 的数据 1 n 1 000 1 p 1 000 所有数字的绝对 值不超过 1000 对于 100 的数据 1 n 1 000 000 1 p 109 其他数字的 绝对值均不超过 109 算法 求特征值就是最大字段和 先预处理一下 复杂度更低 剩下就直接 循环求出答案 代码 include define f a for int i 1 i a i using namespace std int main long long n p score 10101 a 10101 b 10101 0 c 10101 c 是特 征值 for int i 1 i n p f n cin a i for int i 1 i n i for int j 1 j i j b i a j for int i 1 i n i for int l 1 l i l for int r l r i r c i max c i b r b l 1 score 1 c 1 for int i 2 i n i for int j 1 j i j score i max score i score j c j sort score 1 score n 1 int ans score n if ans 0 ans ans 1 p 1 cout ans return 0 年份 2013 十一 题目 表达式求值 noip2013 普及组第二题 expr cpp c pas 描述 给定一个只包含加法和乘法的算术表达式 请你编程计算表达式的值 输入 输入文件为 expr in 输入仅有一行 为需要你计算的表达式 表达式中只包含数字 加法运算 符 和乘 且没有括号 所有参与运算的数字均为 0 到 231 1 之间的整 数 输入数据保 法运算符 证这一行只有 0 9 这 12 种字符 输出 输出文件名为 expr out 输出只有一行 包含一个整数 表示这个表达式的值 注意 当答案长度 多于 4 位时 请只输出最后 4 位 前导 0 不输出 输入输出样例 1 expr in expr out 1 1 3 4 8 输入输出样例 2 expr in expr out 1 1234567890 1 7891 输入输出样例 3 expr in expr out 1 1000000003 1 4 输入输出样例说明 样例 1 计算的结果为 8 直接输出 8 样例 2 计算的结果为 1234567891 输出后 4 位 即 7891 样例 3 计算的结果为 1000000004 输出后 4 位 即 4 数据范围 对于 30 的数据 0 表达式中加法运算符和乘法运算符的总数 100 对于 80 的数据 0 表达式中加法运算符和乘法运算符的总数 1000 对于 100 的数据 0 表达式中加法运算符和乘法运算符的总数 100000 算法 关键在于输入 hzwer 教的这种输入可以把数字和运算符分开 然后 先找乘 再找加 代码 include include using namespace std long long a 1000001 char c 1000001 int main int i 2 cin a 1 int ans 0 while scanf c i 2 for int j i j 0 j if c j a j 1 a j 1 a j 1 10000 for int j 1 j i j if c j ans a j 1 ans 10000 cout ans a 1 10000 return 0 年份 2013 十二 题目 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术 珠心 算训练 既能够开发智力 又能够为日常生活带来很多便利 因而在很多学校 得到普及 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法 他随机生 成一个正整数集合 集合中的数各不相同 然后要求学生回答 其中有多少个 数 恰好等于集合中另外两个 不同的 数之和 最近老师出了一些测验题 请你帮忙求出答案 格式 输入格式 输入共两行 第一行包含一个整数 n 表示测试题中给出的正整数个数 第二行有 n 个正整数 每两个正整数之间用一个空格隔开 表示测试题中给出 的正整数 输出格式 输出共一行 包含一个整数 表示测验题答案 样例 1 样例输入 1 4 1 2 3 4 样例输出 1 2 对于 100 的数据 3 n 100 测验题给出的正整数大小不超过 10 000 算法 枚举所有加法后得数 稍微更改桶排序 在排序同时去掉多余的数 然后和原数比对 因为得数排过序 所以当得数大于原数时就不用判断了 正常情况用栈做 代码 include include include include using namespace std int main int n num 1010 cin n for int i 1 i num i int pl 10101 x 0 for int i 2 i n i for int j 1 j i j pl x num i num j int ans 10101 y 0 bool tong 10101 memset tong 0 sizeof tong for int i 1 i x i tong pl i 1 for int i 1 i 10001 i if tong i 1 ans y i int sum 0 for int i 1 i n i for int j 1 j y j if num i ans j sum break if num i ans j break cout sum return 0 年份 2014 十三 题目 在社交媒体上 经常会看到针对某一个观点同意与否的民意调查以及结果 例 如 对某 一观点表示支持的有 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 的值尽可能小 格式 输入格式 输入共一行 包含三个整数 A B L 每两个整数之间用一个空格隔开 分别 表示支持人数 反对人数以及上限 输出格式 输出共一行 包含两个整数 A B 中间用一个空格隔开 表示化简后的比 例 样例输入 1 1498 902 10 样例输出 1 5 3 对于 100 的数据 1 A 1 000 000 1 B 1 000 000 1 L 100 A B L 算法 在 1 L 的范围内找出和原比例精度差距最小的一组数字 代码 include using namespace std double a b aa bb l int gcd int a int b return b 0 a gcd b a b int main cin a b l double ans a b double ans2 0 0000 double ans3 1000000 00 for double i 1 0 i l i for double j 1 0 j 0 aa i bb j cout aa bb endl return 0 年份 2014 十四 题目 一个 n 行 n 列的螺旋矩阵可由如下方法生成 从矩阵的左上角 第 1 行第 1 列 出发 初始时向右移动 如果前方是未曾 经过的格子 则继续前进 否则右转 重复上述操作直至经过矩阵中所有格子 根据经过顺序 在格子中 依次填入 1 2 3 n2 便构成了一个螺旋矩 阵 下图是一个 n 4 时的螺旋矩阵 1121110 213169 314158 4567 现给出矩阵大小 n 以及 i 和 j 请你求出该矩阵中第 i 行第 j 列的数是多 少 格式 输入格式 输入共一行 包含三个整数 n i j 每两个整数之间用一个空格隔开 分别 表示矩阵大小 待求的数所在的行号和列号 输出格式 输出共一行 包含一个整数 表示相应矩阵中第 i 行第 j 列的数 样例 1 样例输入 1 4 2 3 样例输出 1 14 对于 50 的数据 1 n 100 对于 100 的数据 1 n 30 000 1 i n 1 j n 算法 外壳上的数分布是有规律的 可以由左上角的数推出所有的数 在外 壳上找不到就把外壳剥掉 在新的矩阵的外壳找 但注意更新左上角的数 可 以用递归做 代码 include include using namespace std int num int beg int n int i int j if i 1 return beg j 1 if j n return beg n i 2 if i n return beg n n 2 n j if j 1 return beg n n n 3 n i return num beg 4 n 1 n 2 i 1 j 1 int main int n i j cin n i j cout num 1 n i j endl return 0 年份 2014 十五 题目 扫雷游戏 mine cpp c pas Online judge 问题描述 扫雷游戏是一款十分经典的单机小游戏 在 n 行 m 列的雷区中有一些格子 含有地雷 称之为地雷格 其他格子不含地雷 称之为非地雷格 玩家翻开 一个非地雷格时 该格将会出现一个数字 提示周围格子中有多少个是地雷 格 游戏的目标是在不翻出任何地雷格的条件下 找出所有的非地雷格 现在给出 n 行 m 列的雷区中的地雷分布 要求计算出每个非地雷格周围的 地雷格数 注 一个格子的周围格子包括其上 下 左 右 左上 右上 左下 右 下八个方向上与之直接相邻的格子 输入格式 输入文件名为 mine in 输入文件第一行是用一个空格隔开的两个整数 n 和 m 分别表示雷区的行 数和列数 接下来 n 行 每行 m 个字符 描述了雷区中的地雷分布情况 字符 表示相应格子是地雷格 字符 表示相应格子是非地雷格 相邻字符之间无 分隔符 输出格式 输出文件名为 mine out 输出文件包含 n 行 每行 m 个字符 描述整个雷区 用 表示地雷格 用周围的地雷个数表示非地雷格 相邻字符之间无分隔符 输入输出样例 1 mine in mine out 3 3 10 221 1 1 见选手目录下的 mine mine1 in 和 mine mine1 ans 输入输出样例 2 mine in mine out 2 3 2 1 21 见选手目录下的 mine mine2 in 和 mine mine2 ans 输入输出样例 3 见选手目录下的 mine mine3 in 和 mine mine3 ans 数据说明 对于 100 的数据 1 n 100 1 m 100 算法 只要搜索一遍就可以了 复杂度只有 O 8nm 注意数组要开至少 103 103 我前面开 102 结果 RE 了 代码 include include include using namespace std int u 9 10 0 1 0 1 1 1 1 1 w 9 10 1 0 1 0 1 1 1 1 int main void int a b cin a b char maps 105 105 for int i 1 i a i for int j 1 j maps i j int map 105 105 memset map 0 sizeof map for int i 1 i a i for int j 1 j b j if maps i j map i j 1 for int i 1 i a i for int j 1 j b j if map i j 1 for int k 1 k 8 k if map i u k j w k 1 map i j for int i 1 i a i for int j 1 j b j if map i j 1 cout map i j else cout cout endl return 0 年份 2015 十六 题目 经过 11 年的韬光养晦 某国研发出了一种新的导弹拦截系统 凡是与它的距 离不超过其工作半径的导弹都能够被它成功拦截 当工作半径为 0 时 则能够 拦截与它位置恰好相同的导弹 但该导弹拦截系统也存在这样的缺陷 每套系 统每天只能设定一次工作半径 而当天的使用代价 就是所有系统工作半径的 平方和 某天 雷达捕捉到敌国的导弹来袭 由于该系统尚处于试验阶段 所 以只有两套系统投入工作 如果现在的要求是拦截所有的导弹 请计算这一天 的最小使用代价 格式 输入格式 第一行包含 4 个整数 x1 y1 x2 y2 每两个整数之间用一个空格隔开 表示 这两套导弹拦截系统的坐标分别为 x1 y1 x2 y2 第二行包含 1 个整数 N 1 N 100000 表示有 N 颗导弹 接下来 N 行 每行两个整数 x y 中间用一个空格隔开 表示一颗导弹的坐标 x y 不同导弹的坐标可能相同 所有坐标分量的绝对值都不超过 1000 输出格式 只有一行 包含一个整数 即当天的最小使用代价 样例 1 样例输入 1 0 0 10 0 2 3 3 10 0 样例输出 1 18 样例 2 样例输入 2 0 0 6 0 5 4 2 2 3 4 0 6 2 9 1 样例输出 2 30 限制 每个测试点 1s 提示 两个点 x1 y1 x2 y2 之间距离的平方是 x1 x2 2 y1 y2 2 两套系统工作半径 r1 r2 的平方和 是指 r1 r2 分别取平方后再求和 即 r12 r22 样例 1 说明 样例 1 中要拦截所有导弹 在满足最小使用代价的前提下 两套系统工作半径 的平方分 别为 18 和 0 样例 2 说明 样例中的导弹拦截系统和导弹所在的位置如下图所示 要拦截所有导弹 在满 足最小使用代价的前提下 两套系统工作半径的平方分别为 20 和 10 算法 这是一道贪心 把所有导弹和第一套的距离从大到小排序 然后平均 分配一些第二套 使两套系统的工作半径尽量接近 因为后面要求平方和 前 面就不要开平方了 代码 include include include include using namespace std int x1 x2 y1 y2 n rb 0 int ans 1 20 struct data int x y s1 s2 a 100005 bool cmp data a data b return a s1 x1 y1 x2 y2 n for int i 1 i a i x a i y a i s1 a i x x1 a i x x1 a i y y1 a i y y1 a i s2 a i x x2 a i x x2 a i y y2 a i y y2 sort a 1 a n 1 cmp for int i n i i rb max a i 1 s2 rb ans min ans a i s1 rb printf d ans return 0 年份 2010 十七 题目 有一位使者要游历各国 他每到一个国家 都能学到一种文化 但他不愿意学 习任何一种文化超过一次 即如果他学习了某种文化 则他就不能到达其他有 这种文化的国家 不同的国家可能有相同的文化 不同文化的国家对其他文化 的看法不同 有些文化会排斥外来文化 即如果他学习了某种文化 则他不能 到达排斥这种文化的其他国家 现给定各个国家间的地理关系 各个国家的文 化 每种文化对其他文化的看法 以及这位使者游历的起点和终点 在起点和 终点也会学习当地的文化 国家间的道路距离 试求从起点到终点最少需走 多少路 格式 输入格式 第一行为五个整数 N K M S T 每两个整数之间用一个空格隔开 依次代 表国家个数 国家编号为 1 到 N 文化种数 文化编号为 1 到 K 道路的条数 以及起点和终点的编号 保证 S 不等于 T 第二行为 N 个整数 每两个整 数之间用一个空格隔开 其中第 i 个数 Ci 表示国家 i 的文化为 Ci 接下来 的 K 行 每行 K 个整数 每两个整数之间用一个空格隔开 记第 i 行的第 j 个 数为 aij aij 1 表示文化 i 排斥外来文化 j i 等于 j 时表示排斥相同文化的 外来人 aij 0 表示不排斥 注意 i 排斥 j 并不保证 j 一定也排斥 i 接下来 的 M 行 每行三个整数 u v d 每两个整数之间用一个空格隔开 表示国家 u 与国家 v 有一条距离为 d 的可双向通行的道路 保证 u 不等于 v 两个国家之 间可能有多条道路 输出格式 输出只有一行 一个整数 表示使者从起点国家到达终点国家最少需要走的距 离数 如果无解则输出 1 样例 1 样例输入 1 2 2 1 1 2 1 2 0 1 1 0 1 2 10 样例输出 1 1 样例 2 样例输入 2 2 2 1 1 2 1 2 0 1 0 0 1 2 10 样例输出 2 10 算法 就用了 floyed 最短路算法 如果一个国家排斥另一个国家 就把道路 设为不可通行 表示数据太弱 O n 3 也不会炸 代码 include using namespace std const int INF 999999 int n k m s t dist 101 101 c 101 a 101 101 int main scanf d d d d d for int i 1 i n i for int j i j n j dist i j INF for int i 1 i n i scanf d for int i 1 i k i for int j 1 j k j scanf d for int i 1 i m i int a1 b1 c1 scanf d d d dist a1 b1 dist b1 a1 min dist a1 b1 c1 for int i 1 i n i for int j 1 j n j if a c i c j dist i j INF for int k 1 k n k floyd for int i 1 i n i for int j 1 j n j dist i j min dist i j dist i k dist k j if dist s t INF printf d 1 else printf d dist t s 年份 2014 十八 题目 算法 用什么算法思想解决 数据存储结构 代码 加上注释 年份 十九 题目 算法 用什么算法思想解决 数据存储结构 代码 加上注释 年份 二十 题目 算法 用什么算法思想解决 数据存储结构 代码 加上注释 年份 二十一 题目 算法 用什么算法思想解决 数据存储结构 代码 加上注释 年份