注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI17 stage3 补充(Ones)  

2013-03-09 09:46:48|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
过年时的遗憾,最后的两道题目,决定还是搞一搞算了
POI17 最变态的应该就是这两道题了,lamp和Ones。

题意:一个数的sks值,为其二进制表示中,位于最左端和最右端的且没有和1相连的1的个数(相同的不算),统计1-n,sks的和。输入给出二进制,是将连续的1或者连续的0压缩成了一个数字
题解:可以参见代码中的注释。思想就是分别统计左端的1是独立的个数和右端是独立的1的个数。
答案的计算:
设B的长度为len
左边独立的1的个数:
如果是11...
那么所有10开头且小于B的都可以(而且其一定小于B)
设1出现位置为第k位,2^(k-1) //2^长度
答案:sigma(2^1,....,2^len-2)=2^(len-1)//还要加上1
如果是10...
位数小于len的答案为2^(len-2)-1
否则为B-2^(len-1)+1
答案:B-2^(len-1)+2^(len-2)+1 //最后的1就是答案1
右边独立为1的个数:
设第i位为最后位
....01....
此时答案为B[len-1,...,i+2]-[B[i+1]==B[i]==0]+1//这个比较显然
统计其和
连续0的个数可以分开算,设答案为p
否则对于每i(i>=2)位的1,其会被算:
sigma( 2^0,...,2^(i-2) )=2^(i-1)
另外前缀为0的情况有sum种
即将B除去后两位并减少一位
只有1的个数:
B的位数

然后是写这种奇葩的高精度。关键是进位,耐心点。不过我是没过的,莫名其妙在最大的点RE了,只有90分。。。
不想浪费时间了。
  评论这张
 
阅读(206)| 评论(7)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017