Yuan
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
zoj 3293 数位统计
/**/
/*
序列 2 4 4 6 8 8 8 10 12 12 14
即每一项都是偶数,而且复制k次,a[i] = b*2^k b%2 != 0
列一下,发现有规律
a[2^k - 1] 是最后一个 2^k
写一下二进制表示,发现当前段(按k划分段)的总和可用到之前的结果
定义dp[k]表示a[1]到第k段结束之和
如dp[1] = a[1]
dp[2] = a[1] + a[2] + a[3]
dp[k] = a[1] +
+ a[2^k - 1]
这个可以预处理出来
然后对于一个x,要得到sum[x] 用逐位统计去做
*/
#include
<
cstdio
>
#include
<
cstring
>
#include
<
algorithm
>
using
namespace
std;
long
long
dp[
32
];
void
init()
{
dp[
1
]
=
2
;
for
(
int
i
=
2
; i
<=
31
; i
++
)
{
dp[i]
=
2
*
dp[i
-
1
]
+
((1LL
<<
i
-
1
)
+
1
)
*
(1LL
<<
i
-
1
);
}
}
long
long
cal(
long
long
x)
{
if
(x
==
0
)
return
0
;
int
k
=
0
;
while
( (1LL
<<
k)
<=
x ) k
++
;
long
long
k2
=
1LL
<<
k;
if
(k2
-
x
<=
k)
//
在最后k个数中
{
return
dp[k]
-
(k2
-
1
-
x)
*
k2;
}
return
dp[k
-
1
]
+
(x
-
k2
/
2
+
1
)
*
(k2
/
2
)
+
cal(x
-
k2
/
2
+
1
);
}
int
main()
{
init();
long
long
x, y;
while
(
~
scanf(
"
%lld %lld
"
,
&
x,
&
y) )
{
printf(
"
%lld\n
"
,cal(y)
-
cal(x
-
1
));
}
return
0
;
}
发表于 2010-11-08 22:55
_Yuan
阅读(346)
评论(0)
编辑
收藏
引用
所属分类:
OJ解题报告
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以边为状态bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥写法 ★★★★
CodeForces 57D
CodeForces 55D 数位统计 记忆化搜索 跟pre有关 ★★★★
CodeForces 55E Very simple problem
zoj 3455 统计出现次数 判断相等 用l[i]记录字母出现i次的个数 ★★★★
zoj 3354 映射 环 计数 ★★★
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
Dp(27)
(rss)
OJ解题报告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
计算几何(2)
(rss)
枚举(4)
(rss)
数据结构(6)
(rss)
数论(5)
(rss)
搜索(2)
(rss)
贪心(4)
(rss)
图论(10)
(rss)
学习笔记(6)
(rss)
学习总结(19)
(rss)
组合数学(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新评论
1. re: 双向BFS[未登录]
博主,只用一个队列不就可以解决你第一个问题了吗
--jason
2. re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登录]
cscdcuis
--1
3. re: zoj 3436 逆推 搜
评论内容较长,点击标题查看
--ZH
4. re: zoj 2318 计算几何 spfa判负环
写得好!
--ipqhjjybj
5. re: Poj 1066
@杨书鉴
你写的排序好像不对啊。。。
--小猊