NOIP2012提高组初赛试题分析.ppt_第1页
NOIP2012提高组初赛试题分析.ppt_第2页
NOIP2012提高组初赛试题分析.ppt_第3页
NOIP2012提高组初赛试题分析.ppt_第4页
NOIP2012提高组初赛试题分析.ppt_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

NOIP2012提高组初赛试题分析,2013年9月,南京市复赛分数线68分，省控线（使用奖励名额）50分,1. 本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与“（）、”或“（v）、”非“（）三种布尔运算。如果无论p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(pVq)Vr和pV(qVr)等价，pVp和qVq也等价，而pVq和pq不等价。那么，两两不等价的布尔表达式最多有_个。 解答：对于p、q、r三个变量，每个变量可取0,1两种取值，共有8种组合。 对于每种组合，代入表达式只有0和1两种答案。 因此两两不等价的表达式只有28=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),1,2,3,4,5,f(i)=g(left_childi)*g(right_childi),g(i)=m(left_childi)*m(right_childi),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
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论