2013年蜀山区青少年信息学竞赛.doc

2013年蜀山区青少年信息学竞赛 小学组试题 题目概况 题目名称 数字求和 数字统计 计数 过河问题 文件名 sum tongji count river 输入文件名 sum.in tongji.in count.in river.in 输出文件名 sum.out tongji.out count.out river.out 满分 100 100 100 100 时间限制 1s 1s 1s 1s 空间限制 128MB 128MB 128MB 128MB 注意事项 1. 考试时间为150分钟。 2. 务必看清题目，严格按照所要求的格式输入、输出。 3. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组 测试数据进行调试。 4. 每题一般有10个测试点，测试有严格的时间限制，请尽可能优化算法。 5. 命名规则： (1)每题都规定了该题的英文名称。 (2)程序文件和数据文件的主文件名都是该题的英文名字。 (3)程序文件扩展名采用语言环境的默认扩展名。 (4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。 6. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在文件名中含有盘符信息和任何形式的路径信息。 7.选手应在指定分区的根目录下建立以准考证号命名的文件夹，并将所完成各题的源程序文件和可执行文件拷贝到该文件夹中。 第一题 数字求和 （sum.pas/c/cpp） 【问题描述】 给定一个正整数a，以及另外的n个正整数，要求：这n个整数中，小于a的整数的和是多少？ 【输入数据】 输入数据有两行，第一行两个正整数a和n，含义如上所述； 第二行包含n个小于1000的正整数，两个正整数之间以空格隔开。 【输出数据】 输出一行，给出一个正整数，表示n个数中小于a的数的和。 【样例输入】 10 5 1 2 3 4 11 【样例输出】 10 【数据范围】 对于50% 的数据，n=5; 对于100%的数据，n=1000, a=2000000000 第二题 数字统计 （tongji.pas/c/cpp） 【问题描述】 某次科研调查时得到了n个自然数，每个数均不超过1500000000 （1.5*109）。已知不相同的数不超过10000个，现在需要统计这 些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 【输入数据】 输入文件包含n+1行； 第一行是整数n，表示自然数的个数； 第2~n+1每行一个自然数。 【输出数据】 输出文件包含m行（m为n个自然数中不相同数的个数）， 按照自然数从小到大的顺序输出。每行输出两个整数，分别 是自然数和该数出现的次数，其间用一个空格隔开。 【样例输入】8 2 4 2 4 5 100 2 100 【样例输出】flag[70]++;(i,flag[i] 2 3 4 2 5 1 100 2 int k=1,i=0,x=a[i]; while(a[i]= =x) {i++;k++; } coutx” “kendl; 【数据范围】 40%的数据满足，1=n=1000 80%的数据满足，1=n=50000 100%的数据满足，1=n=200000,每个数均不超过 1500 000 000（1.5*109） for(i=1;i=10;i++) for(j=1;j=100;j++) couti*jendl; 循环不超过1亿（8个0），数组不超过90 0000(90万)，改变算法思想 《1》如果读的每个数的值都不超过100000，int a[100000];读入x ; a[x]++; for(i=1;i=100000;i++) if(a[i0) outi” “a[i]endl; 《2》定义数组是 int a[200000],num; void 3DP动态规划：自己+潜力最大的合作伙伴。 ***核心是填记忆数组（你要求什么他就表示什么，就是潜力） #includefstream using namespace std; ifstream in(tongji.in); ofstream out(tongji.out); int a[200000],num,n; void read() { int i,x; inn; for(i=0;in;i++)//下标从0开始，为了用sort函数 ina[i]; //排序 sort(a,a+n);//下标从0开始排序 for(i=0;in;i++)//测试一下排序结果可对》 outa[i] ; for(i=0;in;i++) { x=a[i]; //x=1 num=0;//