NOIP2011普及组初赛（Pascal）参考答案
一、BBCCB DCBCC BACCC DAAAC
二
(1) 128
(2) 3(ABCDEFG BCDEFG BADEFG BADECG)
三
(1) 165(n..m的自然数求和)
(2) 22366472011(手机键盘输入CCFNOIP2011要按什么键)
(3) 3(中位数)
(4) 20(杨辉三角)
四.1
(1) read(b[i][j]);或 read(b[i,j])
(2) m1 - m2 + 1
(3) good := true;
(4) m2
(5) haveAns := true;
四.2
(1) ans.num[i + j - 1]
(2) ans.num[i]:= ans.num[i] mod 10
(3) ans.num[i] + a.num[i] + b.num[i]
(4) ans.num[i] mod 2
(5) inc(ans.len)
(6) a.len < b.len
(7) 48
(8) times(middle, middle), target
NOIP2011初赛提高组试题参考解答
一、单项选择
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
B
|
B
|
A
|
D
|
B
|
A
|
C
|
D
|
B
|
A
|
二、多项选择
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
CD
|
ABCD
|
AB
|
BC
|
BC
|
ABD
|
CD
|
A
|
BCD
|
ABC
|
5. C是显然要选的，本题因为有300+400=700的情况，所以B也是可以的。
7．首先要知道逆序对的定义：序列A[1..n]里，对于i<j的A[i]>A[j],则称A[i]与A[j]为一对逆序对。将给定的序列中所有逆序对列出来，统计其中数字只出现过3次的。
8．阶码肯定是要选的，D较长的尾数也是浮点数的一个特点，它只是保正了浮点数一定的精度，并不是它可以表示很大或者很小的数的原因。
9．本题描述有点含糊，它的本意可能是在计算S到B点的距离时出现有值。
三、问题求解
1．9
开始就想到就是在5个点里选择2个点的组合数，得到10，没有考虑到不能相交的情况，平面里对于一个封闭区域，不相邻的两个点在此区域内的边将此区域划分为两个封闭的小区域，两个小区域里其它的点不可以再有跨区域的边。
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
m
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
……
|
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
2
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
3
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
|
|
4
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
|
|
5
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
|
|
6
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
|
|
7
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
|
8
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
|
|
9
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
|
|
……
|
|
|
|
|
|
|
|
|
|
128
|
1
|
1
|
1
|
1
|
1
|
1
|
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<b.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的后面还有数据（有右子树）则再以此方法处理右边的数据；
|
