新NOIP提高组初赛历年试题及答案求解题篇.docx

NOIP提高组初赛历年试题及答案求解题篇
NOIP提高组初赛历年试题及答案求解题篇
问题求解题〔每次2题，每题5分，共计10分。每题全部答对得5分，没有局部分〕注：答案在文末
提高组的问题求解题的知识点大多涉及计数问题、鸽巢原1两种值，共有2^3=8种组合；任意一个变量组合代入表达式，只有0和1两种值。因此两两不等价的表达式最多有2^8=256种。
NOIP2022-2 图的独立集问题
图1的独立集：{∅}{1}{2}{3}{2,3}
图2的独立集：{∅}{1}{2}{3}{4}{5}{1,4}{1,5}{1,4,5}{2,3}{3,4}{3,5}{3,4,5}{4,5}
图3可使用DP求解：设m(i)为以i号点为根结点的总个数；f(i)为选i的总个数；g(i)表示不选i的总个数，那么有：m(i)=f(i)+g(i)
f(i)=g(left_child[i])*g(right_child[i])
g(i)=m(left_child[i])*m(right_child[i])
m(17)=f(17)+g(17)=1936+3600=5536
f(17)=g(8)*g(8)=44*44=1936
g(17)=m(8)*m(8)=60*60=3600
m(8)=f(8)+g(8)=16+44=60
f(8)=g(1)*g(6)=1*16=16
g(8)=m(1)*m(6)=2*22=44
m(6)=f(6)+g(6)=6+16=22
f(6)=g(1)*g(4)=1*6=6
g(6)=m(1)*m(4)=2*8=16
m(4)=f(4)+g(4)=2+6=8
f(4)=g(1)*g(2)=1*2=2
g(4)=m(1)*m(2)=2*3=6
m(2)=f(2)+g(2)=3
f(2)=g(1)=1
g(2)=m(1)=2
m(1)=2
f(1)=1
g(1)=1
NOIP2022-1 方程求解问题
同普及组求解题，略。
NOIP2022-2 随机概率问题
假设n = 2 下一步无非跳到1或跳到2再跳到1
f(2) = [ 1 + ( 1 + f(2) ) ] / 2 ，所以 f(2) = 2
假设n = 3 ，那么有f(3) = [ 1 + ( 1 + f(2) ) + ( 1 + f(3) ) ] / 3 =5/2……
假设n=5，那么有f(5) = [ 1 + …… ( 1 + f(5) ) ] / 5=37/12
也可设n个荷叶时的答案为an，那么有an=1+(a1+a2+…an)/n，可得：an=(a1+a2+…+an-1+1)/(n-1)，其中a1=0。可以推导出公式：
an=1+1/1+1/2+…+1/(n-1) (n>1)，那么a5=37/12
NOIP2022-1 排列组合问题
第一种情况：四位数中有两位数字相同，如：1124、1128、1148、1288、1488、2488，共六种组合，每种有A(4,2)=4×3=12种排列方法，共有12×6=72种。
第二种情况：四位数中没有相同的数字，如1248，只有一种组合，排列方法共有A(4,4)=4×3×2×1=24种。
第三种情况：四位数中各有两个数字相同，如1188，只有一种组合，A(4,2)/2