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
狠狠色婷婷综合天天久久丁香
|
亚洲国产精品无码久久一线
|
久久久久亚洲AV无码专区首JN
|
少妇久久久久久被弄高潮
|
久久九九有精品国产23百花影院
|
久久久青草久久久青草
|
亚洲精品WWW久久久久久
|
久久国产亚洲精品无码
|
亚洲国产成人久久综合区
|
亚洲中文字幕久久精品无码APP
|
亚洲国产成人久久综合碰碰动漫3d
|
久久www免费人成看国产片
|
伊人久久综合精品无码AV专区
|
91精品无码久久久久久五月天
|
欧美久久久久久
|
久久久国产一区二区三区
|
国产亚洲综合久久系列
|
亚洲综合伊人久久综合
|
久久亚洲AV无码西西人体
|
99久久精品免费看国产一区二区三区
|
国产精品欧美久久久天天影视
|
人妻中文久久久久
|
久久国产精品免费一区
|
久久精品国产影库免费看
|
久久亚洲AV成人无码国产
|
久久人搡人人玩人妻精品首页
|
久久亚洲国产成人精品性色
|
久久婷婷五月综合色奶水99啪
|
久久影院午夜理论片无码
|
国产精品熟女福利久久AV
|
久久婷婷综合中文字幕
|
久久精品国产免费
|
久久久精品免费国产四虎
|
99久久精品毛片免费播放
|
狠狠88综合久久久久综合网
|
A狠狠久久蜜臀婷色中文网
|
久久婷婷五月综合97色
|
国产精品对白刺激久久久
|
精品综合久久久久久97超人
|
久久精品成人国产午夜
|
久久青青草原综合伊人
|