信息学奥赛注意事项.doc

潍坊信息学竞赛注意事项一、复赛内容与要求：在初赛的内容上增加以下内容：A数据结构：1指针类型2多维数组3单链表及循环链表4二叉树5文件操作（从文本文件中读入数据，并输出到文本文件中）B程序设计1算法的实现能力2程序调试基本能力3设计测试数据的基本能力4程序的时间复杂度和空间复杂度的估计C算法处理1离散数学知识的应用（如排列组合、简单图论、数理逻辑）2分治思想3模拟法4贪心法5简单搜索算法（深度优先 广度优先）搜索中的剪枝6动态规划的思想及基本算法二：注意事项1.务必看清题目，严格按照所要求的格式输入、输出。2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。特别注意最大值与最小值（极值）。3.测试有严格的时间限制，请尽可能优化算法。4.命名规则：各题都规定了该题的英文名称。要求提交程序的文件名一律采用小写。程序文件和数据文件的主文件名都是该题的英文名字。程序文件扩展名采用语言环境的默认扩展名。数据文件都是文本文件，输入数据文件和输出数据文件的扩展名分别是.in和.out。5.程序应从输入文件中读取数据，然后把结果严格地按照规定的输出格式输出到输出文件中。6.考试题目在考试微机的D:/盘下“prlblem”文件夹中，考试结束请将程序放到以“你的考号+姓名”（中间无空格）命名的文件夹中，并将此文件夹放到D:/盘下“test”文件夹中,考试结束后此文件夹要处于打开状态方可离开考场。例：某中学的学生本次测试做了四道题目：（fbi.pas、martian.pas、peanuts.pas、unhappy.pas）,他提交的格式如下 fbi.pas martian.pas D:test“考号BBB” peanuts.pasunhappy.pas 7.每题允许开辟的最大内存空间为128M。8试题完成后，一定要再仔细检查一遍，查看文件名对不对，输入输出文件名对不对，在提交程序中是否将/或等注释符号去掉了。三：评测4.1测试环境测试系统采用国家统一发布的NOILINUX，评测组保证对每个选手的测试均真实、公平，测试机器的配置为CPUP43.0GHZ，内存1G。每题允许开辟的最大内存空间为128M。4.2测试方法本次竞赛为了能实现更加公正和快速的测试，全部采用自动测试系统来加以评测，输入和输出都采用文件的方式，测试时遵循“程序不改动”原则，即使是程序中有不正确的文件名导致程序不能正确地得出结果，也不可以更改程序。每道题目测试10次，每次只测一个测试点，每个测试点的运行时间限制是1秒钟。选手程序运行后输出数据的格式和数据数目必须和标准结果完全一致或完全等效，在输出数据格式不同于标准结果的情况下不论与标准结果多么相似都不予给分。选手请认真核对提交的源程序的文件名，写错的文件名的题得0分。如何骗分：对于一个约定无解输出-1的题目，骗分者只写一行代码就可以把无解的部分分数拿到，有时把示例输出也可能拿到10分。这只是万不得已的情况。最好是依靠实力拿分。1秒内时间复杂度N的大小1S内可以解出的时间复杂度10N!202n1000N2100000nlogn1000000n空间复杂度不能超过内存限制，一般情况下数组不宜开的过大。如果开一个109数组将会出现内存不足的情况，这时就要设计一个优秀的算法来优化空间性能只找出实际有用的信息。2010潍坊试题分析2010年潍坊市青少年信息学奥林匹克竞赛试题（普及组）2010-11-05 10:062010年潍坊市青少年信息学奥林匹克竞赛试题（普及组） 考试注意事项：答题时间为3小时。本试卷共4题，每题分值100分，总分400分。 比赛得分 (score.pas/c/cpp) 【问题描述】最近，市里组织了一次计算机技能大赛，每个选手的最终成绩的计算方法是：根据评委亮分(分数为正整数，不超过100)，去掉一个最高分，去掉一个最低分，剩余的得分为该选手的有效得分，对其取平均值就是该选手的最终得分。现在请你编写程序，输入评委数目和所有评委的打分，输出该选手的最终得分，保留小数点后两位。【输入文件】score.in 一行，第一个是评委的数量，之后是每个评委的打分。各整数用空格隔开。【输出文件】score.out 平均分的值，一个实数，保留小数点后两位。【样例输入】 5 95 80 89 90 86 【样例输出】 88.33装箱问题（pack.pas/c/cpp）【问题描述】有一个箱子容量为V（正整数，0V20000），同时有N个物品（0N30），每个物品有一个体积Vi（正整数）。要求N个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。【输入文件】pack.in 第一行一个整数，表示箱子容量；第二行一个整数，表示共有N个物品；第3行N+2行，各有一个整数，表示这N个物品的各自体积。【输出文件】pack.out 一行，一个整数。表示箱子剩余的最小空间。【样例输入】 24 6 8 3 12 7 9 7 【样例输出】 0 出栈序列统计 (stack.pas/c/cpp) 【问题描述】栈是一种常用的数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。现在已经知道栈的操作有两种： PUSH和 POP，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列得到一系列的输出序列。给定一个n，计算并输出操作序列1,2,3,n经过一系列操作可能得到的输出序列总数。【输入文件】stack.in 一个整数（1n15）【输出文件】stack.out 一个整数，即可能输出序列的总数目【样例输入】3 【样例输出】5 邮局设立（post.pas/c/cpp）【问题描述】一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。【输入文件】post.in 输入数据有两行，第一行两个整数用空格间隔，分别是N(1=N=300)表示村庄数，M(1=M=30)表示邮局数。第二行共N个用空格间隔的整数，表示N个村庄的坐标，1=村庄坐标=10000。【输出文件】post.out 输出数据一个整数表示最小距离和。【样例输入】 105 12367911224450 【样例输出】 9第一题：一般是排序问题，最好用数组来做。2009年试题也是一个排序的试题，这样的题目比较简单。一般情况下只要把第一题做出来就可以参加省赛。第二题：是背包问题，而且是典型的01背包问题。这个要用到动态规划。在省赛里也常有动态规划问题。不过试题要相对难一些。第三题：实际上考的是排列组合问题。出栈序列统计解题报告题目描述很简单，将数据通过栈输的序列数目输出。由于只有两种操作push 和 pop （即入栈和出栈），所以我们可以把入栈操作记为0，出栈操作记为1。所以这道题可以转化为在2n个数中放入n个1（其余的填充0）且满足任何一个位置中的1个数不大于0的个数的排列方式。有了这样一个模型解题就有了我们的方向。1、直接接受的方法应推搜索：我们可以枚举所有满足要求的排列方式，再不重复的前提下将计数器加1。方法很简单但是效率很低很低。 2、O(n)的算法（组合法）： 首先不要过于激动我们的两种算法的效率差距。经过下面分析你会发现其实我们所要求的只不过是卡特兰数。首先在2n个位置中放n个1的方法有C（n/2n）种，当然其中也有不满足情况的序列。那么不满足情况的序列有什么性质呢？再不满足要求的序列中肯定有一个地方满足 “1的个数”= “0的个数”+1，此时这个位置以后的1个数为0的个数-1（因为他们个数均各为n）。我们不妨把此位置以左的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; var c:array1.10000 of longint; n,i,j,k,t,z:longint; begin assign(input,stack.in);reset(input); assign(output,stack.out);rewrite(output); readln(n); fillchar(c,sizeof(c),0); c1:=1;z:=1; for i:=2*n downto n+2 do begin for j:=1 to z do cj:=cj*i; for j:=1 to z+4 do begin cj+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 do begin t:=0; for j:=z downto 1 do begin k:=cj; cj:=(k+t*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【题目描述】佳儿爷爷经常给她讲故事，某天就讲了一个采摘西瓜的故事（因为她闹着要买.）。某年某村的瓜农把一个个西瓜放在象一条直线的水库大坝上，叫本村的小朋友去大坝搬西瓜，谁的西瓜搬走得多，谁就是胜者。搬西瓜必须遵守的原则是：西瓜一个一个搬，可以从任何位置开始搬运，按西瓜所摆放的位置,只能往后取西瓜,取走的西瓜重量不得大于前面已经搬走西瓜的重量（除第一个西瓜）。你能知道他们最多一次能搬走多少个西瓜吗？【输入】第一行为n（小于10000）,西瓜的个数,第二行为n个正整数（小于30000），表示n个西瓜的重量(以克为单位)，各个之间用一个空格隔开 【输出】最多一次能搬走的西瓜个数【输入样例】75 4 7 3 2 2 1【输出样例】6【05NOIP普及组】采药时间限制: 1000 ms 内存限制: 65536 KB【题目描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 【输入】第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 【输出】一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 【输入样例】70 371 10069 11 2【输出样例】3【提示】【数据规模】 对于30%的数据，M = 10； 对于全部的数据，M = 100。 【联赛练习题目】数字金字塔时间限制: 1000 ms 内存限制: 65536 KB【题目描述】考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30 【输入】第一个行包含 R(1= R=1000) ,表示行的数目。 后面R行,每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。【输出】单独的一行包含那个可能得到的最大的和。【输入样例】573 88 1 02 7 4 44 5 2 6 5【输出样例】30另外 学动归 推荐看背包九讲 综观近几年的潍坊试题，难度逐年加大，除第一题外，其它的试题多是一些以前的NOIP试题和一些动态规划典型试题，也就是说是一些基础试题。所以应该注意学习一些基本的算法，如排序（08、09、10）、分治（07年乒乓球循环赛）、贪心、动态规划的思想及基本算法。个人认为如果学会了动态规划，在高中阶段要拿省二等奖也比较容易。而且拿到省二等奖也就具备了参加自主招生考试的资格（通过自主招生考试的学生可降分录取最高可降60分）。从现在起要做一些NOIP试题，并且对每一道试题进行数据测试（可从网上找到历年的试题及测试数据），自己分析调试。对于信息学竞赛来讲，要取得好的成绩，最重要的是要善于自学。教学过程中教师要有意识地培养学生“自主学习”的习惯，这一点在信息学