1、训练 阶段组织安排 序号 工作安排 具体工作内容 完成时间 负责人 责任人 /参与人 1 比赛入门训练 讲解培训过程中需要注意的事项、网上在线练习系统的使用方法 10.8 李发陵 彭娟、张红实、叶扬、廖武忠 2 比赛入门训练 入门题讲解：奇偶数分离、求矩阵转置问题 10.9 李发陵 彭娟、张红实、叶扬、廖武忠 3 算法提高训练 数学问题： 1.韩信点兵； 2.公约数和公倍数； 3.素数求和问题； 4.素数距离问题 10.10 李发陵 彭娟、张红实、叶扬、廖武忠 4 算法提高训练 数学问题： 5.光棍节的快乐； 6.A*B Problem； 7.最大素因子； 8.最大的最小公倍数 10.11 李
2、发陵 彭娟、张红实、叶扬、廖武忠 5 算法提高训练 数学问题： 9.最少乘法次数； 10.阶乘因式分解（二）；11.次方求模； 12.九的余数； 13.一个简单的数学题 10.12 李发陵 彭娟、张红实、叶扬、廖武忠 6 算法提高训练 STL 练习： 1.5 个数求最值；2.字符串替换； 3.求次数；4.括号配对问题 10.13 李发陵 彭娟、张红实、叶扬、廖武忠 7 算法提高训练 大数问题： 1. 比大小； 2.大数阶乘； 3.最小公倍数；4.开方数 10.14 李发陵 彭娟、张红实、叶扬、廖武忠 8 算法提高训练 贪心算法： 1.+ -字符串；2. 独木舟上的旅行； 3.摆方格； 4.非洲
3、小孩； 10.17 李发陵 彭娟、张红实、叶扬、廖武忠 9 算法提高训练 贪心算法： 5. 寻找最大数；6. 背包问题； 7.阶乘之和 10.18 李发陵 彭娟、张红实、叶扬、廖武忠 10 算法提高训练 搜索： 1.素数环； 2.部分和问题； 3.zb 的生日 10.19 李发陵 彭娟、张红实、叶扬、廖武忠 11 算法提高训练 搜索： 4.吝啬的国度； 5.组合数； 6.幸运三角形 10.20 李发陵 彭娟、张红实、叶扬、廖武忠 12 算法提高训练 数据结构： 1.国王的烦恼；2.生活的烦恼； 3.括号配对问题 10.21 李发陵 彭娟、张红实、叶扬、廖武忠 13 算法提高训练 数据结构： 4
4、.表达式求值；5.中缀式变后缀式； 6.重建二叉树 10.24 李发陵 彭娟、张红实、叶扬、廖武忠 14 算法提高训练 动态规划： 1.串； 2.找数达人； 3.最长公共子序列； 4. 10.25 李发陵 彭娟、张红实、叶扬、廖武忠 子串和； 5.作业题 15 算法提高训练 动态规划： 6.苹果； 7.免费馅饼； 8 硬币找零； 9.回文字符串 10.26 李发陵 彭娟、张红实、叶扬、廖武忠 16 算法提高训练 图论： 1.星际之门（一）；2.网络的可靠性； 3.天下第一； 4.布线问题 10.27 李发陵 彭娟、张红实、叶扬、廖武忠 17 算法提高训练 计算几何： 1.三角形面积；2.三点顺
5、序； 3.管道问题；4.圈水池 10.28 李发陵 彭娟、张红实、叶扬、廖武忠 18 算法提高训练 矩阵计算： 1.A*B Problem II； 2.fibonacci 数列(二 )； 3.递推求值 10.31 李发陵 彭娟、张红实、叶扬、廖武忠 19 算法强化训练 算法强化训练： 1.疯牛（贪心算法）； 2.Yougth 的最大化（贪心算法） 11.1 李发陵 彭娟、张红实、叶扬、廖武忠 20 算法强化训练 算法强化训练： 3.会场安排问题（贪心算法）； 4.三个水杯（搜索） 11.2 李发陵 彭娟、张红实、叶扬、廖武忠 21 算法强化训练 算法强化训练： 5.水池数目（搜索） 6.最少步
6、数（搜索） 11.3 李发陵 彭娟、张红实、叶扬、廖武忠 22 算法强化训练 算法强化训练： 7.表达式求值（数据结构）； 8.求逆序数（数据结构） 11.4 李发陵 彭娟、张红实、叶扬、廖武忠 23 算法强化训练 算法强化训练： 9.矩形嵌套（动态规划）； 10.开心的小明（动态规划） 11.7 李发陵 彭娟、张红实、叶扬、廖武忠 24 算法强化训练 算法强化训练： 11.最大和；12.心急的 C 小加 11.8 李发陵 彭娟、张红实、叶扬、廖武忠 25 算法强化训练 算法强化训练： 13.蚂蚁的难题（三）； 14.单词拼接（图论） 11.9 李发陵 彭娟、张红实、叶扬、廖武忠 26 算法强
7、化训练 算法强化训练： 15.街区最短路径问题（数学问题）；16.多边形重心问题（计算几何） 11.10 李发陵 彭娟、张红实、叶扬、廖武忠 27 真题模拟训练 完成第一届重庆市比赛试题练习 11.11 李发陵 彭娟、张红实、叶扬、廖武忠 28 真题模拟训练 完成第二届重庆市比赛试题练习 11.14 李发陵 彭娟、张红实、叶扬、廖武忠 29 真题模拟训练 完成第三届重庆市比赛试题练习 11.15 李发陵 彭娟、张红实、叶扬、廖武忠 30 真题模拟训练 完成第四届重庆市比赛试题练习 11.16 李发陵 彭娟、张红实、叶扬、廖武忠 31 真题模拟训练 完成第五届重庆市比赛试题练习 11.17 李发
8、陵 彭娟、张红实、叶扬、廖武忠 32 真题模拟训练和比赛注意事项 比赛具体安排，要求。完成第六届重庆市比赛试题 11.18 李发陵 彭娟、张红实、叶扬、廖武忠 附录 1：练习题 题目 1： 奇偶数分离 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述 有一个整型偶数 n(2= n =10000),你要做的是：先把 1 到 n 中的所有奇数从小到大输出，再把所有的偶数从小到大输出。 输入 第一行有一个整数 i（ 2=i30)表示有 i 组测试数据； 每组有一个整型偶数 n。 输出 第一行输出所有的奇数 第二行输出所有的偶数 样例输入 2 10 14 样例输出 1 3
9、 5 7 9 2 4 6 8 10 1 3 5 7 9 11 13 2 4 6 8 10 12 14 :题目 2： 求转置矩阵问题 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 求一个三行三列的转置矩阵。 输入 第一行一个整数 n20，表示有 n 组测试数据，下面是 n 组数据 ; 每组测试数据是九个整型数（每个数都不大于 10000），分别为矩阵的的每项； 输出 每组测试数据的转置矩阵； 请在每组输出之后加一个换行 样例输入 2 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 1 样例输出 1 4 7 2 5 8 3 6 9 2 5 8
10、3 6 9 4 7 1 数学问题 题目 1： 韩信点兵 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述 相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入 3 个非负整数a,b,c ，表示每种队形排尾的人数（ a3,b5,c7），输出总人数的最小值（或报告无解）。已知总人数不小于 10，不超过 100 。 输入 输入 3 个非负整数 a,b,c ，表示每种队形排尾的人数（ a3,b5,c7）。例如 ,输入： 2 4 5 输出 输出总人数的最小值（或报告无解，即输出
11、No answer）。实例，输出： 89 样例输入 2 1 6 样例输出 41 解释说明 优化算法：中国余数定理又名孙子定理 例子 1： 11 一个数除 3 得 2 除 5 得 1 （ 3n+2） %5=6 3n%5=4（乘积的余数等于余数的乘积） 3n%5=（ 3%5）（ n%5） （ n%5） =3= n=3 例子 2：一个数除 3 得 2 除 5 得 1 除 7 得 6 除数的个数大于等于 3； 每个除数都是素数 第一步，算常量 对于 3 的余数：找同时被 5 和 7 整除而被 3 余数为 1 的数 70 求的算法：循环 while 35 每循环一次 +35 循环里边除以 3 看余数等不
12、等于 1 对于 5 的余数：找同时被 3 和 7 整除而被 5 余数为 1 的数 21 对于 7 的余数：找同时被 5 和 3 整除而被 7 余数为 1 的数 15 第二步 （ 2*70+1*21+6*15） %（ 3*5*7） =251%105=41 （ 3 的余数 *3 的常量 +5 的余数 *5 的常量 +7 的余数 *7 的常量） %105 题目 2： 公约数和公倍数 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述 小明被一个问题给难住了，现在需要你帮帮忙。问题是：给出两个正整数，求出它们的最大公约数和最小公倍数。 输入 第一行输入一个整数 n（ 0n=
13、10000)，表示有 n 组测试数据 ; 随后的 n 行输入两个整数 i,j（ 0i,j=32767)。 输出 输出每组测试数据的最大公约数和最小公倍数 样例输入 3 6 6 12 11 33 22 样例输出 6 6 1 132 11 66 解释说明 公约数的算法 0、两个数的公约数，首先比较大小，大数作为被除数小数作为除数 1、大数 /小数若整除结束，否则把余数得到当做除数，把之前的小数（除数）当做大数（被除数），继续进行大数 /小数的运算； 2、小数 /余数若整除结束，否则把 2 次余数作为除数把余数作为被除数； 3、结束的时候其最后作为除数的为最大公约数 比如说例子 48 14 48/1
14、4 余数 6 6/2 余数 0 两个数 A/B 最小公倍数的求法 A*B 除以最大公约数 题目 3： 素数求和问题 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 现在给你 N 个数（ 0N1000），现在要求你写出一个程序，找出这 N 个数中的所有素数，并求和。 输入 第一行给出整数 M(0M10)代表多少组测试数据 每组测试数据第一行给你 N，代表该组测试数据的数量。 接下来的 N 个数为要测试的数据，每个数小于 1000 输出 每组测试数据结果占一行，输出给出的测试数据的所有素数和 样例输入 3 5 1 2 3 4 5 8 11 12 13 14 15 1
15、6 17 18 10 21 22 23 24 25 26 27 28 29 30 样例输出 10 41 52 题目 4： 素数距离问题 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。 如果输入的整数本身就是素数，则输出该素数本身，距离输出 0 输入 第一行给出测试数据组数 N(0N=10000) 接下来的 N 行每行有一个整数 M(0M1000000)， 输出 每行输出两个整数 A B. 其中 A 表示离相应测试数据最近的素数
16、， B 表示其间的距离。 样例输入 3 6（往左 5 往右 7） 8 7 11 10 7 11 样例输出 5 1 7 1 11 1 解释 素数概念 求素数的算法 优化的，求 n 从 2 开始到开 n 的平方结尾 31 从 2 开始到 5 题目 5： 光棍节的快乐 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 光棍们，今天是光棍节。聪明的 NS 想到了一个活动来丰富这个光棍节。 规则如下： 每个光棍在一个纸条上写一个自己心仪女生的名字，然后把这些纸条装进一个盒子里，这些光棍依次抽取一张纸条，如果上面的名字就是自己心仪的女生，那么主持人就在现场给该女生打电话，告诉
17、这个光棍对她的爱慕之情，并让光棍当场表白，并得到现场所有人的祝福，没抽到的，嘿嘿就可以幸免了。 假设一共有 N个光棍 ,其中有 M个没有抽到自己的纸条 ,求发生这种情况一共有多少种可能 .。 输入 每 行包含两个整数 N 和 M(1M=N=20)，以 EOF 结尾。 输出 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。 样例输入 2 2 3 2 样例输出 1 3 题目 6： A*B Problem 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 设计一个程序求出 A*B，然后将其结果每一位相加得到 C，如果 C 的位数大于等于 2
18、，继续将 C 的各位数相加，直到结果是个一位数 k。 例如： 6*8=48； 4+8=12； 1+2=3； 输出 3 即可。 输入 第一行输入一个数 N(0N=1000000)，表示 N 组测试数据。 随后的 N 行每行给出两个非负整数 m， n（ 0=m,n=1012)。 输出 对于每一行数据，输出 k。 样例输入 3 6 8 1234567 67 454 1232 样例输出 3 4 5 题目 7： 最大素因子 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 GreyAnts 最近正在学习数论中的素数，但是现在他遇到了一个难题：给定一个整数 n,要求我们求出
19、n 的最大素因子的序数 ,例如： 2 的序数是 1,3 的序数是 2,5 的序数是 3，以此类推 . 研究数论是需要很大的耐心的，为了惩罚那些没有耐心读完题目的童鞋，我们规定： 1 的最大素因子序数是 0. 输入 有多组测试数据 ,每一行输入一个数字 n.(0n=1000000) 输出 在接下来的一行，输出结果 . 样例输入 2 3 4 5 样例输出 1 2 1 3 题目 8： 最大的最小公倍数 时间限制： 1000 ms | 内存限制： 32768 KB 难度： 2 描述 高中时我们对最小公倍数就已经很熟悉了，相信你很快就可以把这个问题解决。这次的问题是：给你一个正整数 n，任取三个不大于
20、n 的正整数，取法不限，每个数可取多次，使得取到的这三个数的最小公倍数在所有取法中是最大的。 例如当 n = 5 时，不大于 5 的数为 1、 2、 3、 4、 5。则应该选 3、 4、 5 三个数，它们的最小公倍数是 60，在所有取法中是最大的。因此我们得到结果 60。 是不是很简单？抓紧时间 AC 吧。 输入 输入包含多组测试数据。每组数据为一个正整数 n（ 1n106）。 输出 对每组测试数据，输出一个整数，代表所有可能取法中，选出的三个数的最小公倍数的最大值。 样例输入 5 7 样例输出 60 210 题目 9： 最少乘法次数 时间限制： 1000 ms | 内存限制： 65535 K
21、B 难度： 3 描述 给你一个非零整数，让你求这个数的 n 次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如 24： 2*2=22（第一次乘）， 22*22=24（第二次乘），所以最少共 2 次； 输入 第一行 m 表示有 m(1=m=100)组测试数据； 每一组测试数据有一整数 n（ 0n=10000） ; 输出 输出每组测试数据所需次数 s; 样例输入 3 2 3 4 样例输出 1 2 2 题目 10 阶乘因式分解（二） 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述 给定两个数 n， m,其中 m 是一个素数。 将 n（ 0=n=231）的阶乘分
22、解质因数，求其中有多少个 m。 注： 为求幂符号。 输入 第一行是一个整数 s（ 0s=100)，表示测试数据的组数 随后的 s 行 , 每行有两个整数 n， m。 输出 输出 m 的个数 样例输入 3 100 5 16 2 1000000000 13 样例输出 24 15 83333329 题目 11： 次方求模 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 求 a 的 b 次方对 c 取余的值 输入 第一行输入一个整数 n 表示测试数据的组数（ n100） 每组测试只有一行，其中有三个正整数 a,b,c(1=a,b,c=1000000000) 输出 输出 a 的 b 次方对 c 取余之后的结果 样例输入 3 2 3 5 3 100 10 11 12345 12345 样例输出
