集训队作业winsock3beta解题报告_第1页
全文预览已结束

付费下载

下载本文档

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

文档简介

1、湖南长郡中学 王俊Winsock 3 Beta解题报告问题简述 给定的一个非负整数M，确定是否有且仅有唯一的K使得K+1.2K之间恰好有M个数的二进制表示中恰好有3个数位为1。分析该题给出虽然题目仅一句话但由M关系到K，又到K+1.2K的数，再到每个数的二进制表示法，转了多个弯。要想直接从M来思考，感觉无法入手，没有突破口。不妨先从最简单的单独的数开始分析：定义S数为二进制表示中恰有3个数位为1 的数。下表是一些正整数的二进制表示：十进制数二进制表示二进制表示中1的个数111210171113810001910012101010211101131211002131101314111031511

2、114再来看看K+1.2K中S数的个数KK1.2K中S数的个数10203041516273似乎看不出太多规律，还是来进行一定的理论分析吧！设Pn表示n的是否为S数，如果是则Pn = 1，否则Pn = 0。设Cn表示n+1 . 2n中S数的个数，即有：观察发现：因为2n的二进制表示只是在n的二进制表示后多一个0，其所含1的个数和n相同，所以n和2n或者同为S数，或者均不是S数，即P2n = Pn所以 又因为 , 所以 所以当对于某个M，有唯一的K满足条件，则必满足即 设L为2k-1的二进制表示的位数， 即 (L3) Ai表示2k1的二进制表示中位权为2i-1的位。Bi表示2k1的二进制表示中位权

3、为2i-1的位。因为2k1为奇数, 所以A1 = 1，又因为AL = 1，所以A2 . AL 1中有且仅有一个为1, 设At = 1 ()。假设， 因为2k + 1 = (2k 1) + 2, 所以 与2k+1的二进制表示中恰有3个数位为1矛盾， 所以t = 2。即 。所以 ， 即那么k+1.2k中的数可分为两类：k+1.2k-5即 ，包含所有长度为L1的S数。因为首位必为1， 所以剩下的L2位中有2个数位为1，那么S数的个数为。2K4.2K即，这一类仅有5个数，其中只有这一个S数。 即对于M， 如果方程 有唯一一个大于3的正整数解，则满足题目条件，否则不满足。 因为，且为整数， 所以 , 且8m7为完全平方数。 所以当8m7为完全平方数且时满足题目条件，即有且仅有唯一的K使得K+1.2K之间恰好有M个数的二进制表示中恰好有3个数位为1。问题得到完满解决。看似毫无头绪的题目，经过一步步的分析，简化，最后得到了算法即只是一个简单的数学式子，时空复杂度均为O(1)。【题目来源】Petrozavodsk Summer Training Sessions 20

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论