NOIP2014普及组复赛试题讲解(c++版本).ppt

NOIP2014普及组复赛题解 NOIP2014普及组C 2 第1题 珠心算测验 简述 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法 他随机生成一个正整数集合 集合中的数各不相同 然后要求学生回答 其中有多少个数 恰好等于集合中另外两个 不同的 数之和 直接三重循环穷举外层循环枚举和 两个内层循环分别枚举两个加数 如果有两个数之和对应外层循环的枚举值 退出两个内层循环注意 找到满足等式的必须退出两个内循环 注意看清题意 其中有多少个数 恰好等于集合中另外两个 不同的 数之和 3 参考程序C includeusingnamespacestd intmain intn i j k ans 0 inta 105 cin n for i 1 i a i for i 1 i n i 和为A i boolf false for j 1 j n j for k j 1 k n k if a i a j a k f true ans break if f break cout ans return0 4 第2题 比例简化 简述 在社交媒体上 经常会看到针对某一个观点同意与否的民意调查以及结果 例如 对某一观点表示支持的有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的值尽可能小 5 确定解题思路 L很小 还是枚举分别枚举化简之后的A 和B 判断A B A B 避免精度问题 转换成乘法A B A B 判断互质 最大公约数为1判断A 和B 最小A ansB ansA B 找到更小的A 和B 设置为ansA和ansB 6 主程序 includeusingnamespacestd intgcd intx inty intt t x y if t 0 returny elsereturngcd y t intmain inta b l a1 b1 ansa ansb cin a b l ansa 100 ansb 1 for a1 l a1 1 a1 for b1 l b1 1 b1 if a1 b a b1 if gcd a1 b1 1 if ansa b1 ansb a1 ansa a1 ansb b1 cout ansa ansb return0 7 第3题 螺旋矩阵 简述 一个n行n列的螺旋矩阵可由如下方法生成 从矩阵的左上角 第1行第1列 出发 初始时向右移动 如果前方是未曾经过的格子 则继续前进 否则右转 重复上述操作直至经过矩阵中所有格子 根据经过顺序 在格子中依次填入1 2 3 n2 便构成了一个螺旋矩阵 下图是一个n 4时的螺旋矩阵 现给出矩阵大小n以及i和j 请你求出该矩阵中第i行第j列的数是多少 8 确定解题思路 思想 剥洋葱皮 分成一个个 口 先找出这个点在第几个 口 中 口 的边长就是n 2 c 2 c表示层一个个 口 整行整列处理u表示最上行 d表示最下行 l表示最左列 r表示最右列 计算出起始数值 判断目标行 列是否在这个 口 中 按u r d l的顺序判断 没有找到 目标行 列 则收缩一圈 循环执行 9 参考程序 includeusingnamespacestd intmain longintn u d l r s 0 x y cin n x y u l 1 d r n while 1 if x u s s y l 1 break else s s r l if y r s s x u 1 break else s s d u if x d s s r y 1 break else s s r l if y l s s d x 1 break else s s d u u l d r cout s 10 第4题 子矩阵 简述 11 暴力搜索 预计得分50分 构造出行 DFS 构造出列 DFS 计算目前的子矩阵的分值 12 暴力搜索程序模块 voidw intk if k row 1 h 1 进入列搜索return if n r k 1 row k 1 for inti r k 1 1 i n i r k i w k 1 13 暴力搜索程序模块 voidh intg if g col 1 intt pd if t col g 1 for inti c g 1 1 i m i c g i h g 1 14 暴力搜索程序模块 intpd intsum 0 for inti 1 i row i for intj 1 j col j sum abs a r i c j a r i c j 1 for intj 1 j col j for inti 1 i row i sum abs a r i c j a r i 1 c j returnsum 15 暴力搜索程序模块 intmain cin n m row col for inti 1 i a i j w 1 cout ans return0 16 确定解题思路AC 思路 搜索 DP枚举出选那些行算出j列各行之间的分数w j k j两列之间的分数v k j f i j 表示已经选了i 数量 列 最后一列是j 下标 的最小分数且第i列是j状态转移方程 f i j min f i 1 k w j v k j 17 数据结构 a maxn maxn 存放原数据n行m列的矩阵r maxn c存放枚举出的行号vx maxn maxn maxn vx I K J 记录i行k列与j列之间的差值的绝对值w maxn j列各行之间的分数v maxn maxn k j两列之间的分数f maxn maxn i列 最后一列是j的最小分数且第i列是j 18 参考程序 DP部分 voiddp memset w 0 sizeof w memset v 0 sizeof v memset f 127 sizeof f for intj 1 j m j for inti 2 i row i w j abs a r i j a r i 1 j for intj 1 j m j f 1 j w j for intj 2 j m j for intk 1 k j k for inti 1 i m i v k j vx r i k j for inti 2 i col i for intj