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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4577 X-Boxes  

2013-08-10 21:17:51|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4577
杭州邀请赛第二题,有n个球(编号从1到n),要放入k个box,要求是如果第i个box里如果有编号为x的小球,则第i+1个box里必须要有编号为x*2的小球,第i-1个box里必须要有编号为x/2的小球。最后的得分是第一个box里的小球个数,问怎么放得分最高。
题解:
可以按照题意先写出几个符合条件的序列:
1,2,4,8,16,32,64……
3,6,12,24,48,96……
5,10,20,40,80,160……
7,14,28,56,112,224……
……
不考虑n,如果k=3,为了在第一个box里多放球,第一个box里可以放的小球除了1,3,5,7……还可以是8,24,40,56,64……
可以发现,第一个box里的小球编号都是奇数(2*a-1),如果不是奇数一定是2^(k*t)*(2*a-1), t=1,2,3,4……
于是可以发现第一个box的小球编号满足这样的公式:(2*a-1)*2^(k*t-1),a和t取1,2,3,4……
于是可以把问题化简成求有多少组解(a, t)符合式子:(2*a-1)*2^(k*t-1) <= n
比赛时,推到这里,我就开始打代码了,因为n很大,所以用Java打了,从1开始枚举t,然后求出有多少个a符合条件,把所有结果累加,结果TLE了;
于是看能不能优化,发现求2^p可能会超时,还是循环求的(不超时才怪)。。。于是又改成快速幂,还是TLE;
继续看,发现不用枚举t,因为t每次加1,相当于给2^(k*t-1)乘上2^k,换个想法,改成每次对n除2^k,但是第一次是除2^(k-1),这样就避免了求2^p。交上去发现还是TLE。。。;
这时候已经快不行了,觉得这样做可能还是太慢了,或许可以O(1)的方法过,于是和队友一起找规律去了,但是迟迟没能发现好的规律,最后这题也没A掉……
赛后,和其它队讨论发现大家都是这么做的,公式都是大同小异,突然想到可能是取整的地方多此一举了,我中间结果用了BigDecimal来操作,最后才对结果取整,仔细想想发现中间过程完全可以取整,对最后的结果没影响,于是回去把所有的BigDecimal都换成了BigInteger处理,然后交上去终于A了!

/*
* fudq.cpp
*
* Created on: 2013-08-10
* Author: fudq
*/
import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
int i,t,k;
BigInteger n,tt,k1,k2;
BigInteger tmp=BigInteger.valueOf(2);
BigInteger ans;
t=cin.nextInt();
while(t-- > 0)
{
n=cin.nextBigInteger();
k=cin.nextInt();
k1=BigInteger.ONE;
for(i=0;i<k-1;i++)
k1=k1.multiply(tmp);
n=n.divide(k1);
ans=(n.add(BigInteger.ONE)).divide(tmp);
k2=k1.multiply(tmp);
for(i=1;;i++)
{
if(n.compareTo(BigInteger.valueOf(1)) < 0)
break;
n=n.divide(k2);
tt=(n.add(BigInteger.ONE)).divide(tmp);
ans=ans.add(tt);
}
System.out.println(ans);
}
}
}


  评论这张
 
阅读(640)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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