Noip2012 普及组解题报告普及组解题报告 南京市育英第二外国语学校 施昊阳 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 10 9 算法分析 算法 1 暴力解法 根据 对于 60 的数据 6 n 1000 易得出模拟解法 将数字从 1 循环到 trunc sqrt n 得到第一个可以被 n 整除的数字再判断是否为素数 以 此类推 期望得分 60 实际得分 100 算法 2 欧拉筛选法 根据 对于 100 的数据 6 n 2 10 9 易得出 trunc sqrt 2 10 9 50000 故可用筛选法求解 其他同算法 1 期望得分 100 实际得分 100 算法 3 模拟法 根据小学知识两个素数的积一定是合数且只有 3 个因子 可以得出最简单的算法 期望得分 100 实际得分 100 程序 算法 1 省略 算法 2 include include include include using namespace std short pr 50000 0 int main ifstream fin prime in ofstream fout prime out pr 1 1 int n maxi 1 fin n for int i 2 i int sqrt n i if pr i 0 for int j i 2 j int sqrt n j i pr j 1 if n i 0 maxi n i fout maxi endl return 0 算法 3 include include include using namespace std int n int main freopen prime in r stdin freopen prime out w stdout scanf d for int i 2 i 44721 i if n i 0 cout n i endl break return 0 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 treasure out 2 3 1 2 0 3 1 4 0 1 1 5 1 2 1 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 算法分析 算法 1 按照题解模拟 期望得分 50 实际得分 50 算法 2 将 x 对每层有楼梯的房间总和进行取模 将时间复杂度降低 程序 算法 1 var a array 1 10000 0 100 1 2 of longint b array 1 1000000 1 2 of longint i j k n m t x s longint begin assign input treasure in reset input assign output treasure out rewrite output readln n m for J 1 to m n do begin read b j 1 b j 2 readln end for i 1 to n do for j 1 to m do begin a i j 1 1 b i 1 m j 1 a i j 1 2 b i 1 m j 2 end readln t s 0 for i 1 to n do begin x a i t 2 j 0 t t 1 while jx do begin t t 1 mod m if a i t 1 1 then j j 1 end s s x end writeln s mod 20123 close input close output end 算法 2 var n m i j k ans x y z longint a array 1 10005 1 105 1 2 of longint s array 1 10005 of longint begin assign input treasure in assign output treasure out reset input rewrite output readln n m fillchar s sizeof s 0 for i 1 to n do for j 1 to m do begin readln a i j 1 a i j 2 s i s i a i j 1 end readln x x x mod m 1 ans 0 for i 1 to n do begin ans ans a i x 2 mod 20123 if i n then break z x a i x 2 a i x 2 mod s i if a i x 2 0 then a i x 2 s i y a i x 1 while y a i z 2 do begin x x mod m 1 y y a i x 1 end end writeln ans close input close output end 3 摆花 flower cpp c pas 问题描述 小明的花店新开张 为了吸引顾客 他想在花店的门口摆上一排花 共 m 盆 通过调 查顾客的喜好 小明列出了顾客最喜欢的 n 种花 从 1 到 n 标号 为了在门口展出更多 种花 规定第 i 种花不能超过 ai 盆 摆花时同一种花放在一起 且不同种类的花需按标号 的从小到大的顺序依次摆列 试编程计算 一共有多少种不同的摆花方案 输入 输入文件 flower in 共 2 行 第一行包含两个正整数 n 和 m 中间用一个空格隔开 第二行有 n 个整数 每两个整数之间用一个空格隔开 依次表示 a1 a2 an 输出 输出文件名为 flower out 输出只有一行 一个整数 表示有多少种方案 注意 因为方案数可能很多 请输出 方案数对 1000007 取模的结果 输入输出样例 1 flower in flower out 2 4 3 2 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 算法分析 算法 1 朴素模拟 根据 对于 20 数据 有 0 n 8 0 m 8 0 ai 8 易得出模拟解法 算法类似与背包问题的暴力解法 期望得分 20 实际得分 20 算法 2 动态规划 三种循环进行 DP 动态转移方程 f i j f i j f i 1 j k mod 1000007 你发现了什么 对了 这还是一个 最简单的 01 背包问题 只不过要看清题意 即可实现算法 期望得分 100 实际得分 100 程序 算法 1 var a b f array 0 100 of integer n k m l i j longint t boolean begin assign input flower in assign output flower out reset input rewrite output readln n m for i 1 to n do read b i for i 1 to m do a i 1 a 0 0 if n 8 and ma j 1 then begin t false break end if t then begin fillchar f sizeof f 0 for j 1 to m do inc f a j for j 1 to n do if f j b j then begin t false break end end if t then l l 1 mod 1000007 k m while a k n do begin a k 1 k k 1 end a k a k 1 end end else begin l 1 for j 1 to n do l l b j mod 1000007 l l div m n 1 end writeln l close input close output end 算法 2 var n m i j k longint a array 1 100 of longint f array 0 100 0