Yuan
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯系
|
聚合
|
管理
zoj 3293 數位統(tǒng)計
/**/
/*
序列 2 4 4 6 8 8 8 10 12 12 14
即每一項都是偶數,而且復制k次,a[i] = b*2^k b%2 != 0
列一下,發(fā)現有規(guī)律
a[2^k - 1] 是最后一個 2^k
寫一下二進制表示,發(fā)現當前段(按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] 用逐位統(tǒng)計去做
*/
#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
;
}
發(fā)表于 2010-11-08 22:55
_Yuan
閱讀(362)
評論(0)
編輯
收藏
引用
所屬分類:
OJ解題報告
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
相關文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以邊為狀態(tài)bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥寫法 ★★★★
CodeForces 57D
CodeForces 55D 數位統(tǒng)計 記憶化搜索 跟pre有關 ★★★★
CodeForces 55E Very simple problem
zoj 3455 統(tǒng)計出現次數 判斷相等 用l[i]記錄字母出現i次的個數 ★★★★
zoj 3354 映射 環(huán) 計數 ★★★
網站導航:
博客園
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判負環(huán)
寫得好!
--ipqhjjybj
5.?re: Poj 1066
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
久久婷婷五月综合成人D啪
|
色婷婷综合久久久久中文一区二区
|
久久强奷乱码老熟女网站
|
亚洲国产精品一区二区三区久久
|
久久香蕉国产线看观看99
|
狠狠综合久久综合中文88
|
中文字幕久久亚洲一区
|
国产V综合V亚洲欧美久久
|
久久精品国产国产精品四凭
|
97视频久久久
|
国产成人综合久久久久久
|
精品久久久中文字幕人妻
|
色综合久久中文综合网
|
亚洲精品美女久久777777
|
久久青青草原精品影院
|
无码人妻精品一区二区三区久久
|
亚洲一区中文字幕久久
|
伊人久久无码中文字幕
|
久久久久久亚洲精品无码
|
AAA级久久久精品无码片
|
久久成人国产精品免费软件
|
久久久久九国产精品
|
国产高清美女一级a毛片久久w
|
色综合久久久久无码专区
|
亚洲色欲久久久久综合网
|
国内精品久久久久久久涩爱
|
久久久精品2019免费观看
|
久久综合久久美利坚合众国
|
欧美性猛交xxxx免费看久久久
|
久久青草国产精品一区
|
国内精品伊人久久久久
|
久久久久久无码Av成人影院
|
99久久99久久精品国产片果冻
|
久久精品国产亚洲AV大全
|
久久久无码精品亚洲日韩京东传媒
|
久久99精品久久久久久动态图
|
中文字幕热久久久久久久
|
一本色道久久综合亚洲精品
|
一本一本久久A久久综合精品
|
久久婷婷五月综合色奶水99啪
|
性做久久久久久久久老女人
|