信息学奥赛注意事项

《信息学奥赛注意事项》由会员分享，可在线阅读，更多相关《信息学奥赛注意事项（9页珍藏版）》请在金锄头文库上搜索。

1、潍坊信息学竞赛注意事项一、复赛内容与要求：在初赛的内容上增加以下内容：A数据结构：1指针类型2多维数组3单链表及循环链表4二叉树5文件操作（从文本文件中读入数据，并输出到文本文件中）B程序设计1算法的实现能力2程序调试基本能力3设计测试数据的基本能力4程序的时间复杂度和空间复杂度的估计C算法处理1离散数学知识的应用（如排列组合、简单图论、数理逻辑）2分治思想3模拟法4贪心法5简单搜索算法（深度优先 广度优先）搜索中的剪枝6. 动态规划的思想及基本算法二：注意事项1. 务必看清题目，严格按照所要求的格式输入、输出。2. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。特

2、 别注意最大值与最小值（极值）。3测试有严格的时间限制，请尽可能优化算法。4. 命名规则：各题都规定了该题的英文名称。要求提交程序的文件名一律采用小写。程序 文件和数据文件的主文件名都是该题的英文名字。程序文件扩展名采用语言环境的默认扩 展名。数据文件都是文本文件，输入数据文件和输出数据文件的扩展名分别是.in和.ou t。5. 程序应从输入文件中读取数据，然后把结果严格地按照规定的输出格式输出到输出文件 中。6. 考试题目在考试微机的D:/盘下“prlblem”文件夹中，考试结束请将程序放到以“你 的考号+姓名”（中间无空格）命名的文件夹中，并将此文件夹放到D:/盘下“test”文件 夹中，

3、考试结束后此文件夹要处于打开状态方可离开考场。例：某中学的学生本次测试做了四道题目：(fbi.pas、martian.pas、peanuts.pas、unhappy.pas)，他提交的格式如下fbi.pasD:test、“考号 BBB” mar ti an.pas pean ut s.pas unhappy.pas7. 每题允许开辟的最大内存空间为128M。8. 试题完成后，一定要再仔细检查一遍，查看文件名对不对，输入输出文件名对不对，在 提交程序中是否将/或等注释符号去掉了。三：评测4.1测试环境测试系统采用国家统一发布的NOI LINUX，评测组保证对每个选手的测试均真实、公平，测试机器的

4、配置为CPU P43.0GHZ，内存1G。每题允许开辟的最大内存空间为128M。4.2测试方法本次竞赛为了能实现更加公正和快速的测试，全部采用自动测试系统来加以评测，输入和 输出都采用文件的方式，测试时遵循“程序不改动”原则，即使是程序中有不正确的文件 名导致程序不能正确地得出结果，也不可以更改程序。每道题目测试10次，每次只测一个测试点，每个测试点的运行时间限制是1秒钟。选手程 序运行后输出数据的格式和数据数目必须和标准结果完全一致或完全等效，在输出数据格 式不同于标准结果的情况下不论与标准结果多么相似都不予给分。选手请认真核对提交的源程序的文件名，写错的文件名的题得0分。如何骗分：对于一个

5、约定无解输出-1的题目，骗分者只写一行代码就可以把无解的部分分数拿到，有 时把示例输出也可能拿到10分。这只是万不得已的情况。最好是依靠实力拿分。1 秒内时间复杂度N的大小1S内可以解出的时间复杂度10N!202n1000N2100000nlogn1000000n空间复杂度不能超过内存限制，一般情况下数组不宜开的过大。如果开一个 109 数组将会出现内存不足的情况，这时就要设计一个优秀的算法来优化空间性能只 找出实际有用的信息。2010潍坊试题分析2010 年潍坊市青少年信息学奥林匹克竞赛试题（普及组）2010-11-05 10:062010年潍坊市青少年信息学奥林匹克竞赛试题（普及组） 考试

6、注意事项：答题时间为 3 小时。本试卷共4题，每题分值 100分，总分400分。比赛得分 （score.pas/c/cpp） 【问题描述】最近，市里组织了一次计算机技能大赛，每个 选手的最终成绩的计算方法是：根据评委亮分（分数为正整数，不超过 100），去掉一个最 高分，去掉一个最低分，剩余的得分为该选手的有效得分，对其取平均值就是该选手的最 终得分。现在请你编写程序，输入评委数目和所有评委的打分，输出该选手的最终得分， 保留小数点后两位。【输入文件】score.in 行，第一个是评委的数量，之后是每个评委的打分。各整数用空 格隔开。【输出文件】 score.out 平均分的值，一个实数，保留

7、小数点后两位。【样例输入】595 80 89 90 86【样例输出】 88.33装箱问题（pack.pas/c/cpp）【问题描述】有一个箱子容量为V （正整数，0WVW20000）, 同时有N个物品（0VNW30），每个物品有一个体积Vi （正整数）。要求N个物品中，任 取若干个装入箱内，使箱子的剩余空间为最小。【输入文件】pack.in第一行一个整数，表示箱子容量；第二行一个整数，表示共有N个 物品；第3行N+2行，各有一个整数，表示这N个物品的各自体积。【输出文件】 pack.out 一行，一个整数。表示箱子剩余的最小空间。【样例输入】2468 3 12 7 9 7【样例输出】 0出栈序

8、列统计（stack.pas/c/cpp）【问题描述】栈是一种常用的数据结构，有n个元素 在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。现在已经知道栈的操作有两种： PUSH 和POP，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一 个操作序列得到一系列的输出序列。给定一个n,计算并输出操作序列1,2,3,n经过一系列操作可能得到的输出序列总数。【输入文件】stack.in 个整数(lWnW15)【输出文件】 stack.out 一个整数，即可能输出序列的总数目【样例输入】 3【样例输出】 5邮局设立(pos t.pas/c/cpp)【问题描述】一些村庄建在一条笔直的高速

9、公路边上，我们 用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两 个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用 与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。【输入文件】post.in输入数据有两行，第一行两个整数用空格间隔，分别是N(l=N=300) 表示村庄数，M(l=M=30)表示邮局数。第二行共N个用空格间隔的整数，表示N个村庄的 坐标， 1=村庄坐标=10000。【输出文件】 post.out 输出数据一个整数表示最小距离和。【样例输入】 10 5 1 2 3 6 7 9 11 22 44

10、 50【样例输出】 9第一题：一般是排序问题，最好用数组来做。 2009 年试题也是一个排序的试题，这样的题 目比较简单。一般情况下只要把第一题做出来就可以参加省赛。第二题：是背包问题，而且是典型的01背包问题。这个要用到动态规划。在省赛里也常有 动态规划问题。不过试题要相对难一些。第三题：实际上考的是排列组合问题。出栈序列统计解题报告题目描述很简单，将数据通过栈输的序列数目输出。由于只有两种操作 push 和 pop (即入栈和出栈)，所以我们可以把入栈操作记为 0，出栈操作记为 1。所以这道题可以转化为在 2n 个数中放入 n 个 1(其余的填充 0)且满足任何一个位置中的1 个数不 大于

11、 0 的个数的排列方式。有了这样一个模型解题就有了我们的方向。1、直接接受的方法应推搜索： 我们可以枚举所有满足要求的排列方式，再不重复的前提下将计数器加 1。方法很简单但是效 率很低很低。2 、 O(n) 的算法(组合法)：首先不要过于激动我们的两种算法的效率差距。经过下面 分析你会发现其实我们所要求的只不过是卡特兰数。首先在2n个位置中放n个1的方法有C(n/2n )种，当然其中也有不满足情况的序列。那么不满足情况的序列有什么性质呢？再不满足要求的序列中肯定有一个地方满足 “1 的个数”= “0 的个数”+1，此时这个位置以 后的1个数为0的个数T (因为他们个数均各为n)。我们不妨把此位

12、置以左的0和1对调(即原 为1出改为0,原为0处改为1),则肯定有n+1个0和n-1个1,所以C(n-1/2n)种可能他不满足 我们的要求。因此所求的数为C(n/2n)-C(n-1/2n),经过数学化简我们可以发现该式是等价于C(n/2n)/( n+1 ),即为卡特兰数。以该模型为基础的实际问题有非常多，例如球票问题 另外由于数字较大,所以需要高精度算法。附程序据参考：program stack;varc:array1.10000 of longint; n,i,j,k,t,z:longint;begin assign(input,stack.in);reset(input); assign(

13、output,stack.out);rewrite(output); readln(n);fillchar(c,sizeof(c),0);c1:=1;z:=1;for i:=2*n downto n+2 dobeginfor j:=1 to z do cj:=cj*i;for j:=1 to z+4 dobegincj+1:=cj+1+cj div 10;cj:=cj mod 10;end;z:=z+5;while cz=0 do dec(z);end;for i:=n downto 2 dobegint:=0;for j:=z downto 1 dobegin k:=cj;cj:=(k+t*

14、10) div i; t:=(k+t*10) mod i;end;while cz=0 do dec(z);end;for i:=z downto 1 do write(ci);writeln;close(input);close(output);end. 第四题：也是一个动态规划基础试题，如以下试题： 【联赛练习题目】采摘西瓜时间限制: 1000 ms内存限制: 65536 KB【题目描述】佳儿爷爷经常给她讲故事，某天就讲了一个采摘西瓜的故事(因为她闹着要买 .)。某年某村的瓜农把 一个个西瓜放在象一条直线的水库大坝上，叫本村的小朋友去大坝搬西瓜，谁的西瓜搬走得多，谁就是 胜者。搬西瓜必须遵

15、守的原则是：西瓜一个一个搬，可以从任何位置开始搬运，按西瓜所摆放的位置 , 只能往后取西瓜,取走的西瓜重量不得大于前面已经搬走西瓜的重量(除第一个西瓜)。你能知道他们最 多一次能搬走多少个西瓜吗？【输入】第一行为n (小于10000)，西瓜的个数，第二行为n个正整数(小于30000),表示n个西瓜的重量(以 克为单位)，各个之间用一个空格隔开【输出】最多一次能搬走的西瓜个数【输入样例】75 4 7 3 2 2 1【输出样例】6【05NOIP普及组】采药时间限制: 1000 ms内存限制: 65536 KB【题目描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为 师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩 子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一 段时间，在这段时间里，你可以采到一些草药。