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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4279  

2012-09-09 22:53:11|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今年天津网络赛的第二题,找规律的题
(两天的网络赛和党课冲突了,所以都没能完整参加上,下午三点上完课马上去了机房,看了下题,开始做第二题……)
刚开始以为是数位dp,但是后来分析发现不对,索性就打表找规律了,和team一起找了一会儿就发现规律了,然后仔细分析了下,就开始写代码了……
代码写完,debug了好久,在最后两分钟终于AC了!
有个bug之前都没遇到过,求闭区间个数时,若进行右边界减左边界,一定要注意左边界会被减掉,处理方法就是先把左边界减一
具体规律如下:
hdu 4279 - fudq - fudq的博客
 
规律分析:
给出区间[a,b],求出前a-1个数的和,求出前b个数的和,相减就是最后结果
按上图分行分好,规律很明显了

AC代码参考如下:

#include<iostream>
#include <math.h>
using namespace std;

__int64 make(__int64 a)
{
__int64 step,b,last_num,tot_num,sum,res;
if(a<=5)
return 0;
if(a<=7)
return 1;
b=a-7;sum=1;
tot_num=(__int64)sqrt(9.0+b)-3;
last_num=2*tot_num+5;

//res=b-(7+last_num)*tot_num/2;
res=b-(6+tot_num)*tot_num;
if(tot_num%2==1)
{
//0,0,0
step=tot_num/2;
sum+=(step+1)*(step+5);
sum+=step*(step+2);

//sum+=(res-3)/2;
if(res>3)
{
if((res-3)%2==1)
sum=sum+(res-2)/2;
else
sum=sum+(res-3)/2;
}
}
else
{
//1,1,1
step=tot_num/2;
sum+=step*(step+4);
sum+=step*(step+2);


if(res<=3)
sum+=res;
else
sum=sum+3+(res-3)/2;

}
return sum;
}

int main()
{
int T;
__int64 a,b;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d",&a--,&b);//!!!一定要注意边界问题
printf("%I64d\n",make(b)-make(a));
}
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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