内容发布更新时间 : 2024/12/27 11:16:58星期一 下面是文章的全部内容请认真阅读。
NOIP2011初赛提高组答案详细解析
一、单项选择
1 B 2 B 3 A 4 D 5 B 6 A 7 C 8 D 9 B 10 A 二、多项选择
1 CD 2 3 ABCD AB 4 BC 5 BC 6 ABD 7 CD 8 A 9 BCD 10 ABC 5. C是显然要选的，本题因为有300+400=700的情况，所以B也是可以的。
7．首先要知道逆序对的定义：序列A[1..n]里，对于i
8．阶码肯定是要选的，D较长的尾数也是浮点数的一个特点，它只是保正了浮点数一定的精度，并不是它可以表示很大或者很小的数的原因。
9．本题描述有点含糊，它的本意可能是在计算S到B点的距离时出现有值。 三、问题求解 1．9
平面图中点数n与边数m之间的关系是：m<=3n-6，当n=5时，m的最大值为9。 2． 4
求出给定的长度为n的字符串的最长上升序列的长度m，最小的操作次数为n-m。 四、阅读程序题 1． 3
先是统计出各个数字出现的次数存放在a数组里，然后I从1开始累加a[i]，直到总数超过n的一半，最后输出i。 2．1 2 5 13 34
斐波那契数列间隔输出 3．150
求遍历图中各个点所有边长的和的最大值。本题4个点，求3条不同边的边长和的最大值。
4．57344 （213*7）
n 1 2 3 4 5 6 7 m 1 2 3 4 5 6 7 8 9 …… 128 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 …… 本题稍有些难度，观察m*n的0-1矩阵，可以看出m=2n，此矩阵其实就是所有7位的二进制数。每一列中有2n-1个1和个0，在一列里每个1都有2^(n-1)个0与它不同，同样每个0也有2^(n-1)个1与它不同，即每列的结果为22n-2*2=22n-1,n列的结果为n*22n-1，所以本题的结果为213*7.
此题也可以从递推的角度来求解：
f(n)=4n/(n-1)*f(n-1) (因为列增加1时行变为原来两倍，01的个数也对应为原来2倍) f(1)=2
由此递推式子也可以得到通项公式：f(n)=n*22n-1。
再分析此题，发现就是从0开始由小到大每次增加1构造出所有n位二进制数，如果将低位写在右边更符合平常习惯，更易看出结果。 五、完成程序题
1．①ans.num[i+j-1] ②ans.num[i]:=ans.num[i] mod 10 ③a.num[i]+b.num[i] ④ans.num[i] mod 2 ⑤inc(ans.len) ⑥a.len ⑦ord(‘0’)或48 ⑧times(middle,middle),target 此题为简单高精度运算的大杂烩，加减乘除几乎全有。 乘法中要注意的是i位乘以j位的数据结果加到i+j-1位里，乘完以后再考虑进位； 加法是对应位相加，可以同步处理进位。 除法本题只是除以2，一位一位除2的时候，余数的情况要先处理。 另外还有一个比较两个以数组形式存储的大数据大小的子程序over，先从长度来考虑，谁长谁大，相等长度时从高位向低位依次比较，只要出现有大的情况就认为它大。 2．①inc(num) ②j:=i ③solve(left,j-1,deep+1) ④solve(j+1,right,deep+1) 基本算法是： 如果当前深度deep超过最大深度maxdeep，则maxdeep?deep且将叶子数sum记为1; 如要当前深度deep=maxdeep，则将sum数加1； 找到当前序列的最小值，并记录它的位置j，以它作为当前子树的根； 如果序列中位置j的前面还有数据（有左子树）则再以此方法处理左边的数据； 如果序列中位置j的后面还有数据（有右子树）则再以此方法处理右边的数据；