NOIP2012提高组初赛试题分析课件

1、NOIP2012提高组初赛试题分析NOIP2012NOIP2012提高组初赛试题分析提高组初赛试题分析2013年年9月月南京市复赛分数线南京市复赛分数线6868分，省控线（使用奖励名额）分，省控线（使用奖励名额）5050分分NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析1. 本题中，我们约定布尔表达式只能包含本题中，我们约定布尔表达式只能

2、包含p,q,r三个布尔变量，以及三个布尔变量，以及“与与“（）、）、”或或“（v）、）、”非非“（）三种布尔运算。如果无论）三种布尔运算。如果无论p,q,r如何取值，如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，两个布尔表达式的值总是相同，则称它们等价。例如，(pVq)Vr和和pV(qVr)等等价，价，pVp和和qVq也等价，而也等价，而pVq和和pq不等价。那么，两两不等价的布尔表不等价。那么，两两不等价的布尔表达式最多有达式最多有_个。个。解答：对于解答：对于p、q、r三个变量，每个变量可取三个变量，每个变量可取0,1两种取值，共有两种取值，共有8种组合。种组合。 对于每种组合

3、，代入表达式只有对于每种组合，代入表达式只有0和和1两种答案。两种答案。 因此两两不等价的表达式只有因此两两不等价的表达式只有28=256种。种。NOIP2012提高组初赛试题分析对于一棵二叉树，独立集是指两两互不相邻的节点构成的对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如图集合。例如图1有有5个不同的独立集（个不同的独立集（1个双点集合，个双点集合，3个单个单点集合，点集合，1个空集），图个空集），图2有有14个不同的独立集，那么，图个不同的独立集，那么，图3有有_个不同的独立集。个不同的独立集。请分析图请分析图2的的14个是怎样得来的？个是怎样得来的？1空空+5单单+6双双

4、+2三三 14NOIP2012提高组初赛试题分析使用使用DP求解求解设设 m(i)为以为以i号点为根结点号点为根结点 总个数总个数 f(i)为选为选i的总个数的总个数 g(i)表示不选表示不选i的总个数，显然有的总个数，显然有 m(i)=f(i)+g(i)12345f(i)=g(left_childi)*g(right_childi) g(i)=m(left_childi)*m(right_childi) 12345f11114g114110m225214NOIP2012提高组初赛试题分析NOIP2012提高组初赛试题分析m(17)=f(17)+g(17)=1936+3600=5536f(17)=g(8)*g(8)=44*44=1936g(17)=m(8)*m(8)=60*60=3600m(8) =f(8)+g(8)=16+44=60f(8)=g(1)*g(6)=1*16=16g(8)=m(1)*m(6)=2*22=44m(6)=f(6)+g(6)=6+16=22f(6)=g(1)*g(4)=1*6=6g(6)=m(1)*m(4)=2*8=16m(4)=f(4)+g(4)=2+6=8f(4)=g(1)*g(2)=1*2=2g(