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
閱讀(367)
評論(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
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
久久久久亚洲爆乳少妇无
|
a级成人毛片久久
|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区
|
国产69精品久久久久APP下载
|
99精品久久精品一区二区
|
久久精品成人国产午夜
|
久久久午夜精品
|
精品国产婷婷久久久
|
人妻精品久久无码区
|
欧美色综合久久久久久
|
国产成人无码精品久久久免费
|
国产精品99久久久久久宅男小说
|
久久亚洲AV无码西西人体
|
久久综合噜噜激激的五月天
|
看全色黄大色大片免费久久久
|
久久精品国产亚洲AV电影
|
久久人人爽人人爽人人av东京热
|
国产精品欧美久久久久无广告
|
性色欲网站人妻丰满中文久久不卡
|
99久久精品免费国产大片
|
久久精品人人做人人爽电影
|
国产高潮国产高潮久久久91
|
色妞色综合久久夜夜
|
日韩欧美亚洲综合久久影院Ds
|
久久国产精品99精品国产987
|
久久精品国产亚洲av麻豆图片
|
思思久久99热免费精品6
|
久久婷婷色综合一区二区
|
国内精品久久久久久麻豆
|
久久精品国产日本波多野结衣
|
色播久久人人爽人人爽人人片aV
|
久久久WWW免费人成精品
|
国内精品久久久久久久影视麻豆
|
亚洲午夜精品久久久久久人妖
|
狠狠干狠狠久久
|
天天久久狠狠色综合
|
99久久夜色精品国产网站
|
国产福利电影一区二区三区久久久久成人精品综合
|
99久久婷婷国产综合亚洲
|
精品乱码久久久久久久
|
国内精品久久久久影院优
|