第一篇：2013年山东省信息学奥赛夏令营提高一树及其应用练习题目
树及其应用上机练习题目
1.FBI树(fbi)
【问题描述】
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
烟台事业单位招聘2022年（1）T的根结点为R，其类型与串S的类型相同；
（2）若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
【输入文件】
高校教师招聘输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。
【输出文件】
输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
【样例输入】
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据，N <= 2；
对于全部的数据，N<= 10。
2.树的遍历(tree)
【问题描述】
我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。
【输入】
第一行是一个整数n，表示节点个数。
第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。
【输出】
输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。
【样例输入】
5 21 22 27 25 20 10
【样例输出】21 22 25 20 7 1 5 10
【样例说明】
【数据规模和约定】
对于30%的数据，n<=100
对于100%的数据，n<=200000，所有节点数值不超过maxlongint且互异。
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二
行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】2 9
【样例输出】
【数据规模】
对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。行政能力测试真题题库
第二篇：信息学奥赛练习8
信息学奥赛练习8
I8-1 用素数表求孪生素数
如果自然数N是素数，N+2也是素数，则称它们为孪生素数。如:3—55—711—13 编程求10000以内的孪生素数山东会计信息网查询
I8-2 求费尔马“二平方”素数
除了2这个特别的素数外，所有的素数都可以分为2类：第一类被4除余1，如5，41；第二类被4除余3，如3、43。第一类素数都能表示成两个整数的平方和的形式，第二类则不能，这就是著名的费尔马“二平方”定理。
我们起名叫做费尔马“二平方”素数，即一个素数能够表示成两个素数的平方和的形式。如: 13=2*2+3*329=2*2+5*5
编程求10000以内的费尔马“二平方”素数
2022年公务员什么时候报名I8-3 回文式素数
有些回文数同时还是素数，如11，101，757，10301，98689，就叫做回文式素数。编程求1000以内的回文式素数。
I8-4 反序猜想：
任意的一个正整数，将其反序（高低位交换），与原来的整数相加，得到新的整数后重复以上步骤，最终可以得到一个回文数，这就叫做回文数反序猜想。
例如：291：291+192=483483+384=867867+768=16351635+5361=6996 6996是回文数，经过了4步
编程验证回文数反序猜想。
第三篇：怎么搞好信息学奥赛
怎么搞好信息学奥赛？
怎么搞好信息学奥赛？
——对话信息学奥赛获奖选手
长沙市长郡中学 石东妮
全国青少年信息学奥林匹克NOI及其分区联赛NOIP（简称奥赛）是由国家教育部批准，中国科协主管，中国计算机学会主办的一项全国性的青少年学科竞赛活动。活动是以在青少年中普及计算机科学为宗旨，信息学奥赛的成功举办激发了广大青少年对计算机及其应用的兴趣，培养了他们的逻辑思维、创造思维以及应用计算机解决实际问题的能力。近年来，有越来越多的青少年参与到这一活动中来。下面是笔者与奥赛金牌获奖选手胡伟栋同学的对话，希望通过对话，能给广大青少年计算机爱好者及其辅导老师一些启发。
胡伟栋同学是湖南长沙市长郡中学毕业生，师从向期中老师，进行信息学奥赛培训。曾在第16届国际信息学奥赛中以总分排名第二获得金牌；在17届国际信息学奥赛中以总分排名第一再次获得金牌。现就读于清华大学计算机科学与技术系。
石：你两次代表中国队参加国际信息学奥赛，并两次获得了金牌，可以说你在信息学奥赛方面取得了辉煌的成绩！今天，咱们就怎么搞信息学奥赛跟你聊聊大家关注的一些问题，行吗？
胡：行，搞奥赛获奖拿金牌并不是我的目的，我还会继续努力。石：你当初为什么要参加信息学奥赛培训？
胡：好奇。
石：你是从什么时候开始接触信息学奥赛培训的？
胡：小学、初中接触程序设计语言，高中开始接受系统的培训。
石：什么时候拿到NOIP的一等奖，要达到NOIP一等奖的水平，你认为应该掌握哪些知识？
胡：初三时拿到普及组的一等奖，之前学完了程序设计语言，对《数据结构》也应有一点点了解。高一时拿到提高组一等奖，我认为要想在NOIP提高组中取得好的成绩，必须学好程序设计语言、《数据结构》两门课程，另外必须掌握好：贪心、枚举、搜索等基本算法，当然最好动态规划也所了解。
石：你每周花多少时间上奥赛培训课？
胡：基本上是每周三晚上及周六一天上培训课，但除此之外，我课余时间也喜欢编程序。
石：你什么时候进入省队，省队每省只有5个人左右，你认为要进入省队必须具备哪些知识？什么时候进入国家集训队、国家代表队？
胡：我在高一时，通过湖南省队的选拔赛考试进入湖南省队，在同年8月的NOI比赛中进入国家集训队，第二年5月通过国家队的选拔赛进入国家队 石：奥赛培训，你是不是认为自学非常重要？教师和自学的关系？
胡：是的，一定要主动去钻研，不能等着别人给答案。教师起辅导和指导的作用，除了向老师请教外，还可以向学长们请教，跟学长们一起讨论。
高考分数线2022年公布石：能给大家推荐一些奥赛的资料吗？
石：参加比赛之前，你通常会做哪些准备？
胡：把最简单的算法回顾一遍，然后轻装上阵。
石：对现在正在参加奥赛培训的学弟学妹们说一句话。
胡：努力吧！
通过以上谈话，大家不难发现搞好信息学奥赛需要掌握好几个关键因素：
一、对种子选手要早发现、早培养;
二、对选手要长期、全面、深入培养;让学生自我拓宽交流渠道，形成综合培养氛围。
发布评论