Yuan
|
首頁
|
發新隨筆
|
發新文章
|
聯系
|
聚合
|
管理
POJ 2828 經典 逆推即可 ★★★
/**/
/*
題意:一些人,相繼插入到pos[i]之后 問最后的情形
解題報告:
本題的算法是利用線段樹進行倒推。基本思想是拿一個N個1的序列,從最后一次插入開始倒推。
設當前插入的是Pos Val,那么找到從左邊數第Pos + 1個1的位置就是最終需要插入Val的位置,
然后把那個1改成0。
我用樹狀數組寫
*/
#include
<
cstdio
>
#include
<
cstring
>
const
int
MAXN
=
200010
;
int
c[MAXN];
int
pos[MAXN],val[MAXN],ans[MAXN];
int
N;
inline
int
lowbit(
int
x)
{
return
x
&
(
-
x);}
void
dec(
int
p)
{
while
(p
<=
N)
{
c[p]
--
;
p
+=
lowbit(p);
}
}
int
getK(
int
K)
{
int
ans
=
0
,cnt
=
0
;
for
(
int
i
=
18
;i
>=
0
;i
--
)
//
i>=0
{
ans
+=
(
1
<<
i);
if
(ans
>=
N
||
cnt
+
c[ans]
>=
K)ans
-=
(
1
<<
i);
else
cnt
+=
c[ans];
}
return
ans
+
1
;
}
int
main()
{
for
(;
~
scanf(
"
%d
"
,
&
N);)
{
for
(
int
i
=
1
;i
<=
N;i
++
)
{
scanf(
"
%d%d
"
,
&
pos[i],
&
val[i]);
c[i]
=
lowbit(i);
}
for
(
int
i
=
N;i;i
--
)
{
int
pp
=
getK(pos[i]
+
1
);
ans[pp]
=
val[i];
dec(pp);
}
for
(
int
i
=
1
;i
<=
N;i
++
)
printf(
"
%d
"
,ans[i]);
puts(
""
);
}
return
0
;
}
發表于 2010-07-28 23:16
_Yuan
閱讀(1029)
評論(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
久久久久久毛片免费播放
|
99久久免费只有精品国产
|
国产亚州精品女人久久久久久
|
亚洲国产另类久久久精品黑人
|
亚洲日韩欧美一区久久久久我
|
一本大道加勒比久久综合
|
…久久精品99久久香蕉国产
|
亚洲AV无一区二区三区久久
|
无遮挡粉嫩小泬久久久久久久
|
7777精品久久久大香线蕉
|
日本国产精品久久
|
伊人 久久 精品
|
久久婷婷激情综合色综合俺也去
|
久久婷婷五月综合97色
|
久久国产精品久久
|
久久精品人妻一区二区三区
|
久久亚洲精品国产精品婷婷
|
人妻少妇久久中文字幕一区二区
|
久久久久久久人妻无码中文字幕爆
|
国产精品福利一区二区久久
|
国产L精品国产亚洲区久久
|
久久天天躁狠狠躁夜夜2020
|
97精品伊人久久久大香线蕉
|
国产精品一久久香蕉国产线看观看
|
94久久国产乱子伦精品免费
|
久久久久97国产精华液好用吗
|
亚洲国产成人久久精品99
|
日韩精品久久无码中文字幕
|
欧美777精品久久久久网
|
色悠久久久久久久综合网
|
奇米综合四色77777久久
|
91精品国产91久久
|
久久精品国产久精国产一老狼
|
久久午夜电影网
|
亚洲αv久久久噜噜噜噜噜
|
99久久国产亚洲高清观看2024
|
久久综合久久美利坚合众国
|
久久精品国产99国产精偷
|
久久99国产精品久久99小说
|
亚洲午夜久久久精品影院
|
亚洲AV无码久久精品色欲
|