NOIP2012提高组初赛试题分析

NOIP2012提高组初赛试题分析

ID:45331771

大小:516.00 KB

页数:14页

时间:2019-11-12

NOIP2012提高组初赛试题分析_第1页
NOIP2012提高组初赛试题分析_第2页
NOIP2012提高组初赛试题分析_第3页
NOIP2012提高组初赛试题分析_第4页
NOIP2012提高组初赛试题分析_第5页
资源描述:

《NOIP2012提高组初赛试题分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、NOIP2012提高组初赛试题分析2013年9月南京市复赛分数线68分,省控线(使用奖励名额)50分1.本题中,我们约定布尔表达式只能包含p,q,r三个布尔变量,以及“与“(^)、”或“(v)、”非“(~)三种布尔运算。如果无论p,q,r如何取值,两个布尔表达式的值总是相同,则称它们等价。例如,(pVq)Vr和pV(qVr)等价,pV~p和~qVq也等价,而pVq和p^q不等价。那么,两两不等价的布尔表达式最多有_______个。解答:对于p、q、r三个变量,每个变量可取0,1两种取值,共有8种组合。对于

2、每种组合,代入表达式只有0和1两种答案。因此两两不等价的表达式只有2^8=256种。对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如图1有5个不同的独立集(1个双点集合,3个单点集合,1个空集),图2有14个不同的独立集,那么,图3有_____________个不同的独立集。请分析图2的14个是怎样得来的?1空+5单+6双+2三=14使用DP求解设m(i)为以i号点为根结点总个数f(i)为选i的总个数g(i)表示不选i的总个数,显然有m(i)=f(i)+g(i)12345f(i)=g(left

3、_child[i])*g(right_child[i])g(i)=m(left_child[i])*m(right_child[i])12345f11114g114110m225214m(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(

4、6)=6+16=22f(6)=g(1)*g(4)=1*6=6 g(6)=m(1)*m(4)=2*8=16m(4)=f(4)+g(4)=2+6=8f(4)=g(1)*g(2)=1*2=2 g(4)=m(1)*m(2)=2*3=6m(2)=f(2)+g(2)=3f(2)=g(1)=1 g(2)=m(1)=2m(1)=2 f(1)=1 g(1)=1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。