JSOI2007第一轮试题.doc

JSOI2007江苏省青少年信息学奥林匹克代表队组队选拔赛第一轮试题 第一轮组队选拔赛共有四道题，每题100分，共400分 每题有十组测试数据，每组10分 = 组数Solved 题目描述：组数.doc 输入数据：number0.in number9.in 输出数据：number0.out number9.out 推广的哈夫曼编码 题目描述：推广的哈夫曼编码.doc输入数据：Huffman0.in Huffman9.in 输出数据：Huffman0.out Huffman9.out 计算表达式 题目描述：计算表达式.doc输入数据：expression0.in expression9.in输出数据：expression0.out- expression9.out分数树题目描述：分数树.doc输入数据：Tree0.in Tree9.in输出数据：Tree0.out- Tree9.out 选拔赛第一轮 组数 number .pas/c/cpp 输入文件名：number.in 输出文件名：number.out 【问题描述】用1、2、3三个数字组成一个n位数。要求不能有两个2和两个3相连。例如：下面的一些数是合理的12113、2312、1212而下面的一些数是不合理的2213、133321、23221问题：给出一个n，求出合理的n位数的个数【输入文件】一个整数n (1n100)【输出文件】符合要求的n位数的个数【样例输入】2【样例输出】7输出说明：7个二位数为11、12、13、21、23、31、32。 选拔赛第一轮推广的哈夫曼编码 Huffman.pas/c/cpp 输入文件名：Huffman.in 输出文件名：Huffman.out 【问题描述 】 【问题描述】将哈夫曼编码中的0、1编码方案，推广到0、1、2、. p ，要求使输入的字符串编码长度最小。 例如： 输入字符串 a b c d a b c a b a a和 p=2 有编码方案： a _ 0 b _ 1 c _ 20 d _ 21此时，该字符串的编码长度为14 (编码方法不唯一，但总长度最小值唯一) 【输入文件】第一行一个整数p (1p9) 第二行为一个字符串（全是由小写字母组成，长度100） 【输出文件】输出一个数（满足条件的编码长度最小值）【样例输入】2 abcdabcabaa【样例输出】 14 选拔赛第一轮 计算表达式 expression.pas/c/cpp 输入文件名：expression.in 输出文件名：expression.out 【问题描述】 表达式的语法定义如下： 例：表达式：32.44E312（43-22.7/16E-2）其中：E+3表示103 ， 32.44E332440E-2 表示 10-2 ， 16E-20.16【输入文件】一行 ；字符形式表达式【输出文件】一个实数，保留小数2位。【样例输入】3 E+2 +12（9-6）+1/3【样例输出】 336.33 选拔赛第一轮 分数树 Tree.pas/c/cpp 输入文件名： Tree.in 输出文件名：Tree.out 【问题描述】【问题描述】树的分数定义为：左子树分数乘右子树的分数再加上根结点的数，若缺左（右）子女时，缺少的左（右）子树分别定义为1。例如，对于下列二叉树： 12 12 8 3 5 7 6 4 (a) (b) 3 ( c ) 则： （a） 分数=12+35=27（b） 分数=12+71=19 （c） 分数=8+6(4+13)=50若给出n个结点的二叉树的中序遍历，此时可以组成许多二叉树。例如n=3，中序顺序为7 10 11，此时的二叉树有：10 11 7 7 11 10 10 7 11 (d) (e) (f)此时分数分别为： (d) 87(e) 28(f) 28问题：给出n个结点的中序序列，求出最大分数树的分数。【输入文件】第一行整数 n (1n20) 第二行n个整数，数之间有一个空格（表示一个中序序列）【输出文件】一个整数，即最大的分数【样例输入】 3 7 10 11【样例输出】87JSOI2007江苏省青少年信息学奥林匹克代表队组队选拔第一轮试题 参 考 答 案 组数 10*10=100分 1 2 3 4 5 6 7 8 9 10输入输出得分 推广的哈夫曼编码 10*10=100分 1 2 3 4 5 6 7 8 9 10输入输出得分计算表达式 10*10=100分 1 2 3 4 5 6 7 8 9 10输入输出得分分数树 10*10=100分 1 2 3 4 5 6 7 8 9 10输入输出得分 三、四、矩形面积，平面上有n个矩形。矩形的边平行于坐标轴，此时一个矩形可以用左下角和右上角的一对点表示。即 p(x、y)、 q(x、y)、 (1x、y100)例如 p (2、1)、q (6、3) 3 q 2 1 p0 1 2 3 4 5 6求出n个矩形占有平面的面积，（重合部分，只能算一次）例如 q1 6 q2 P25 p1 (2、2)、q1 (7、5)4 q13 p2 (6、4)、 q2 (10、6)21 P11 2 3 4 5 6 7 8 9 10 占有面积20+8-127 输入文件n第一行一个整数，表示矩形个数(1