当前位置:首页 >> 学科竞赛 >>

信息学奥赛注意事项


潍坊信息学竞赛注意事项 潍坊信息学竞赛注意事项
一、复赛内容与要求: 复赛内容与要求: 在初赛的内容上增加以下内容: 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”文件 夹中,考试结束后此文件夹要处于打开状态方可离开考场。
1

例:某中学的学生本次测试做了四道题目: (fbi.pas、martian.pas、peanuts.pas、unhappy.pas),他提交的格式如下 fbi.pas martian.pas D:\test\“考号 BBB”\ peanuts.pas unhappy.pas 7. 每题允许开辟的最大内存空间为 128M。 8.试题完成后,一定要再仔细检查一遍,查看文件名对不对,输入输出文件名对不对,在 提交程序中是否将//或{}等注释符号去掉了。 三:评测 4.1 测试环境 测试系统采用国家统一发布的 NOI LINUX,评测组保证对每个选手的测试均真实、公平, 测试机器的配置为 CPU P43.0GHZ,内存 1G。每题允许开辟的最大内存空间为 128M。 4.2 测试方法 本次竞赛为了能实现更加公正和快速的测试,全部采用自动测试系统来加以评测,输入和 输出都采用文件的方式,测试时遵循“程序不改动”原则,即使是程序中有不正确的文件 名导致程序不能正确地得出结果,也不可以更改程序。 每道题目测试 10 次,每次只测一个测试点,每个测试点的运行时间限制是 1 秒钟。选手程 序运行后输出数据的格式和数据数目必须和标准结果完全一致或完全等效,在输出数据格 式不同于标准结果的情况下不论与标准结果多么相似都不予给分。

选手请认真核对提交的源程序的文件名, 选手请认真核对提交的源程序的文件名,写错的文件名的题得 0 分。
如何骗分: 对于一个约定无解输出-1 的题目,骗分者只写一行代码就可以把无解的部分分数拿到,有 时把示例输出也可能拿到 10 分。这只是万不得已的情况。最好是依靠实力拿分。

1 秒内时间复杂度 N 的大小 10 20 1000 100000 1000000 1S 内可以解出的时间复杂度 N! 2n N2 nlogn n

空间复杂度不能超过内存限制,一般情况下数组不宜开的过大。如果开一个 109 数组将会出现内存不足的情况,这时就要设计一个优秀的算法来优化空间性能只 找出实际有用的信息。

2

2010 潍坊试题分析
2010 年潍坊市青少年信息学奥林匹克竞赛试题(普及组) 2010-11-05 10:06 2010 年潍坊市青少年信息学奥林匹克竞赛试题(普及组) 考试注意事项:答题时间为 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(正整数,0≤V≤20000), 同时有 N 个物品(0<N≤30),每个物品有一个体积 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 经过 一系列操作可能得到的输出序列总数。
3

【输入文件】stack.in 一个整数(1≤n≤15) 【输出文件】stack.out 一个整数,即可能输出序列的总数目 【样例输入】3 【样例输出】5 邮局设立(post.pas/c/cpp)【问题描述】一些村庄建在一条笔直的高速公路边上,我们 用一条坐标轴来描述这条公路,每个村庄的坐标都是整数,没有两个村庄的坐标相同。两 个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用 与它距离最近的邮局,建立邮局的原则是:所有村庄到各自使用的邮局的距离总和最小。 【输入文件】 post.in 输入数据有两行, 第一行两个整数用空格间隔, 分别是 N(1<=N<=300) 表示村庄数,M(1<=M<=30)表示邮局数。第二行共 N 个用空格间隔的整数,表示 N 个村庄的 坐标,1<=村庄坐标<=10000。 【输出文件】post.out 输出数据一个整数表示最小距离和。 【样例输入】 10 【样例输出】 9 5 1 2 3 6 7 9 11 22 44 50

第一题:一般是排序问题,最好用数组来做。2009 年试题也是一个排序的试题,这样的题 目比较简单。一般情况下只要把第一题做出来就可以参加省赛。 第二题:是背包问题,而且是典型的 01 背包问题。这个要用到动态规划。在省赛里也常有 动态规划问题。不过试题要相对难一些。 第三题:实际上考的是排列组合问题。
出栈序列统计解题报告 题目描述很简单,将数据通过栈输的序列数目输出。 由于只有两种操作 push 和 pop (即入栈和出栈) ,所以我们可以把入栈操作记为 0,出栈操作记为 1。 所以这道题可以转化为在 2n 个数中放入 n 个 1(其余的填充 0)且满足任何一个位置中的 1 个数不 大于 0 的个数的排列方式。 有了这样一个模型解题就有了我们的方向。 1、直接接受的方法应推搜索: 我们可以枚举所有满足要求的排列方式,再不重复的前提下将计数器加 1。方法很简单但是效 率很低很低。 2、O(n)的算法(组合法) : 首先不要过于激动我们的两种算法的效率差距。经过下面 分析你会发现其实我们所要求的只不过是卡特兰数。 分析你会发现其实我们所要求的只不过是卡特兰数。 首先在 2n 个位置中放 n 个 1 的方法有 C(n/2n)种,当然其中也有不满足情况的序列。那么 不满足情况的序列有什么性质呢?
4

再不满足要求的序列中肯定有一个地方满足 “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:array[1..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); c[1]:=1;z:=1; for i:=2*n downto n+2 do begin for j:=1 to z do c[j]:=c[j]*i; for j:=1 to z+4 do begin c[j+1]:=c[j+1]+c[j] div 10; c[j]:=c[j] mod 10; end; z:=z+5; while c[z]=0 do dec(z); end; for i:=n downto 2 do begin t:=0; for j:=z downto 1 do begin
5

k:=c[j]; c[j]:=(k+t*10) div i; t:=(k+t*10) mod i; end; while c[z]=0 do dec(z); end; for i:=z downto 1 do write(c[i]); writeln; close(input);close(output); end. 第四题:也是一个动态规划基础试题,如以下试题: 【联赛练习题目】采摘西瓜 时间限制: 1000 ms 【题目描述】 佳儿爷爷经常给她讲故事,某天就讲了一个采摘西瓜的故事(因为她闹着要买...) 。某年某村的瓜农把 一个个西瓜放在象一条直线的水库大坝上,叫本村的小朋友去大坝搬西瓜,谁的西瓜搬走得多,谁就是 胜者。搬西瓜必须遵守的原则是:西瓜一个一个搬,可以从任何位置开始搬运,按西瓜所摆放的位置, 只能往后取西瓜,取走的西瓜重量不得大于前面已经搬走西瓜的重量(除第一个西瓜) 。你能知道他们最 多一次能搬走多少个西瓜吗? 【输入】 第一行为 n(小于 10000),西瓜的个数,第二行为 n 个正整数(小于 30000) ,表示 n 个西瓜的重量(以 克为单位),各个之间用一个空格隔开 【输出】 最多一次能搬走的西瓜个数 【输入样例】 7 5473221 【输出样例】 6 【05NOIP 普及组】采药 时间限制: 1000 ms 【题目描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为 师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说: “孩 子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一
6

内存限制: 65536 KB

内存限制: 65536 KB

段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的 总价值最大。 ” 如果你是辰辰,你能完成这个任务吗? 【输入】 第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100) ,用一个空格隔开,T 代表总共能够用 来采药的时间,M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。 【输出】 一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。 【输入样例】 70 3 71 100 69 1 12 【输出样例】 3 【提示】 【数据规模】 对于 30%的数据,M <= 10; 对于全部的数据,M <= 100。 【联赛练习题目】数字金字塔 时间限制: 1000 ms 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 内存限制: 65536 KB

2 7 4 4 4 5 2 6 5

在上面的样例中,从 7 到 3 到 8 到 7 到 5 的路径产生了最大和:30 【输入】 第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面 R 行,每行为这个数字金字塔特定行包含的整数。
7

所有的被供应的整数是非负的且不大于 100。 【输出】 单独的一行包含那个可能得到的最大的和。 【输入样例】 5 7 38 810 2744 45265 【输出样例】 30

推荐看《背包九讲》 另外 学动归 推荐看《背包九讲》
综观近几年的潍坊试题, 难度逐年加大, 除第一题外, 其它的试题多是一些以前的 NOIP 综观近几年的潍坊试题, 难度逐年加大, 除第一题外, 试题和一些动态规划典型试题,也就是说是一些基础试题。 试题和一些动态规划典型试题,也就是说是一些基础试题。所以应该注意学习一些基本的 算法,如排序(08、09、10) 分治( 年乒乓球循环赛) 贪心、 算法,如排序(08、09、10)、分治(07 年乒乓球循环赛)、贪心、动态规划的思想及基 本算法。个人认为如果学会了动态规划,在高中阶段要拿省二等奖也比较容易。 本算法。个人认为如果学会了动态规划,在高中阶段要拿省二等奖也比较容易。而且拿到 省二等奖也就具备了参加自主招生考试的资格( 省二等奖也就具备了参加自主招生考试的资格(通过自主招生考试的学生可降分录取最高 可降 60 分)。 从现在起要做一些 NOIP 试题,并且对每一道试题进行数据测试(可从网上找到历年的 试题及测试数据),自己分析调试。对于信息学竞赛来讲,要取得好的成绩,最重要的是 要善于自学。教学过程中教师要有意识地培养学生“自主学习”的习惯,这一点在信息学 竞赛辅导开始之初尤其重要,教师要作出适当引导,并制定明确的各学期目标与计划。 “纸 上得来终觉浅,绝知此事要躬行”,这不仅是计算机教学特殊性的体现,也是教师对参加 计算机竞赛的学生的忠告。学生只有通过上机实践行动,才能在不断促进其独立思考能力 培养的同时激发出学习兴趣。对学生而言,兴趣是最好的老师。不通过上机实践,就不可 能提出实际问题,也就不能有效激发出学习积极性。信息学竞赛要求学生只有通过自身不 断实践与探索,才能做到对所学内容有更深层的理解,才能让实践、思考、提高三者成为 一个统一体。 曾听全国第三名的魏铭说过自己做过 2000 道试题。只有见多识广,才能在 考试时游刃有余,得心应手。

8


相关文章:
信息学奥赛问题求解(带答案)
信息学奥赛问题求解(带答案)_学科竞赛_初中教育_教育专区。1.已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出...
浅析当今中学信息学奥赛存在的问题
浅析当今中学信息学奥赛存在的问题_教育学_高等教育_教育专区。浅析当今中学信息学奥赛存在的问题 信息学奥赛如火如荼的进行着,其中,取得的成绩自不必说。但我们不...
信息学奥赛教学之我见
信息学奥赛教学之我见_教学研究_教育专区。信息学奥赛教学之我见 全国青少年信息学奥林匹克分区联赛(简称 NOIP)是经中国科协、国家教育 部批准,由中国计算机学会主办...
信息学奥赛(问题求解)
信息学奥赛(问题求解)_其它课程_高中教育_教育专区。第十届: 1、一个家具公司...注意:任意中间结果只有在某台 PC 上已经得到, 才可以被其他 PC 引用。 例如...
信息学奥赛教程
信息学奥赛算法教程_Pas... 110页 免费喜欢...UNPACK,WRITE,WRITELN 注意:单词不要写错,不分大小...需要输入什么,解决问题需要几步, 最终要得到什么结果...
信息学奥赛计算机基础知识
信息学奥赛计算机基础知识_电脑基础知识_IT/计算机_专业资料。信息学奥赛计算机...注意符号位不变。 如:若机器数是 16 位: 十进制数 17 的原码、反码与补码...
凭什么我得了信息学奥赛国家一等奖
什么我得了信息学奥赛国家一等奖_教学反思/汇报_教学研究_教育专区。这人就是牛啊!凭啥!凭的是意志!凭的是信念!凭什么我得了信息学奥赛国家一等奖 山东省莱州...
信息学奥赛普及组1-18届问题求解题解析
信息学奥赛普及组1-18届问题求解题解析_学科竞赛_高中...如果只有一层,结果是什么(1) 如果有两层呢(1×2...三个顶点 最多选 8 个 注意到 S0=0 是必须选的...
信息学奥赛 基础知识习集
信息学奥赛 基础知识习集信息学奥赛 基础知识习集隐藏>> 全国青少年信息学奥林匹克...5.硬盘工作时应特别注意避免 B (A)噪声 (B)震动 (C)潮湿 (D)日光 6....
更多相关标签:
拔牙后注意事项 | 面试技巧和注意事项 | 备孕注意事项 | 坐月子注意事项 | 泰国旅游注意事项 | 孕早期注意事项 | 买二手房注意事项 | 买房注意事项 |