noip2012初赛第3题解析

《noip2012初赛第3题解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP2012初赛试题解析（第3题问题求解）上传：朱全民浏览：144时间：10-15http://www.091edu.com/news/view/id/2931.本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与“（^）、”或“（v）、”非“（~）三种布尔运算。如果无论p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(pVq)Vr和pV(qVr)等价，pV~p和~qVq也等价，而pVq和p^q不等价。那么，两两不等价的布尔表达式最多有_______个。解答：对于p、q、r三个变量，每个变量可取0,1两

2、种取值，共有8种组合。对于每种组合，代入表达式只有0和1两种答案。因此两两不等价的表达式只有2^8=256种。2.对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如图1有5个不同的独立集（1个双点集合，3个单点集合，1个空集），图2有14个不同的独立集，那么，图3有_____________个不同的独立集。解答：设m(i)为以i个为根结点的树的独立集总个数f(i)为选i的总个数g(i)表示不选i的总个数，显然有m(i)=f(i)+g(i)对于二叉树，如果根节点选，则儿子节点不能选，有f(i)=g(left_child[i])*g(

3、right_child[i])如果根节点不选，则解与根节点无关，直接为左右儿子的解相乘，有g(i)=m(left_child[i])*m(right_child[i])具体用动态规划求解如下（计算的时候是从下往上算，这里设树的节点总数为根节点编号），显然该题就是求m(17)，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

4、(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(4)=m(1)*m(2)=2*3=6m(2)=f(2)+g(2)=3f(2)=g(1)=1g(2)=m(1)=2m(1)=2f(1)=1g(1)=1长沙市雅礼中学朱全民2012年10月15日