n373. 7. 鮭魚收藏家
標籤 : binomial heap 模擬
通過比率 : 2人/6人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-11-11 11:23

內容

  2021年初,知名壽司連鎖店在台灣舉辦促銷活動,凡是名字內包含「鮭魚」兩字者,皆可免費享用鮭魚大餐,許多人跟風紛紛改名。某天好吃懶做的小明驚奇的發現,不用改名,一張印有鮭魚的鈔票也能換到一份免費的鮭魚餐,從此小明便開始了收集鮭魚鈔的習慣。
  小明使用一種特殊的方式來整理他收集的鮭魚鈔,所有鈔票將分成數本,從左到右由鈔票數量少排到鈔票數量多的,如果有兩本鈔票數量一樣,小明會在不拆開原本兩本鈔票的封條的情況下,用一個新封條將它們綁成新的一本。

  以下將以 $[a_1,a_2,\cdots,a_m]$,表示當下有 $m$ 本,第 $i$ 本有 $a_i$  張鈔票,並且每次收集到一張新的鈔票,會將其視為獨立的一本。
  舉例來說,在小明收集到第二張鈔票時,因為兩本都只有一張鈔票 $[1,1]$ ,所以他會將這兩本鈔票捆成新的一本 $[2]$;收集到第三張鈔票時兩本分別有一張與兩張 $[1,2]$;收集第四張時,因為有兩本都只有一張 $[1,1,2]$,所以會被捆在一起,而後變成兩本都是兩張 $[2,2]$,它們將會被再次困在一起 $[4]$,以此類推。
  綑綁兩本鈔票時,小明會做簡單的比對,他會根據兩本最上面那張鈔票的編號,較小的那一本放在上面。
  當小明餓了,他會選擇其中一本最上面的一張鮭魚鈔拿去換免費的鮭魚,假如小明選定的那本共有 $16$ 張鈔票,拆開了所有有綁住最上面那一張鈔票的封條並拿走那張鈔票以後,那一本將會變成 $[1,2,4,8]$ 四小本,小明會再依每本張數由小到大分別將其與原本有的幾本整理在一起(先將 $[1]$ 加入原有的幾本,做完所有合併後,再將 $[2]$ 整理進去,如此往復將張數由少到多的本與原有的幾本做合併)。

輸入說明

  輸入的第一行有一個正整數 $N$($1\le N\le 3\times 10^5$),代表有 $N$ 筆操作,接下來有 $N$ 行,每行有一個整數 $x$($x<10^9$),當 $x$ 為非負整數(不會重複),代表小明收集到了一張編號為 $x$ 的鈔票;當 $x$ 為負數時,代表小明打算使用第 $-x$ 本最上面那一張鮭魚鈔去飽餐一頓,可以假設所有操作都是合法的。
  小明一開始沒有任何鈔票。

輸出說明

   共輸出 $N$ 行,代表在執行每一筆操作以後,鈔票收藏的狀態。每行請先輸出一個整數 $m$,代表當前的收藏共有 $m$ 本,再依照每本的張數由小到大,輸出每一本最上面那張鈔票的編號。每個整數用一個空白隔開。

範例輸入 #1
2
123456
-1
範例輸出 #1
1 123456
0
範例輸入 #2
10
5
2
9
4
-1
32
7
3
8
-3
範例輸出 #2
1 5
1 2
2 9 2
1 2
2 5 4
1 4
2 7 4
2 3 4
3 8 3 4
2 5 3
測資資訊:
記憶體限制: 512 MB
提示 :

  範例輸入 #2 的十筆操作,每本所包含的鈔票如下:
存 $5\rightarrow\ \ \{5\}$
存 $2\rightarrow\ \ \{2\}\{5\}\rightarrow\{2\ 5\}$
存 $9\rightarrow\ \ \{9\}\{2\ 5\}$
存 $4\rightarrow\ \ \{4\}\{9\}\{2\ 5\}\rightarrow\{4\ 9\}\{2\ 5\}\rightarrow\{2\ 5\ 4\ 9\}$
取 $1\rightarrow\ \ \{\color{red}2\color{black}\ 5\ 4\ 9\}\rightarrow\{5\}\{4\ 9\}$
存 $32\rightarrow \{32\}\{5\}\{4\ 9\}\rightarrow\{5\ 32\}\{4\ 9\}\rightarrow\{4\ 9\ 5\ 32\}$
存 $7\rightarrow\ \ \{7\}\{4\ 9\ 5\ 32\}$
存 $3\rightarrow\ \ \{3\}\{7\}\{4\ 9\ 5\ 32\}\rightarrow\{3\ 7\}\{4\ 9\ 5\ 32\}$
存 $8\rightarrow\ \ \{8\}\{3\ 7\}\{4\ 9\ 5\ 32\}$
取 $3\rightarrow\ \ \{8\}\{3\ 7\}\{\color{red}4\color{black}\ 9\ 5\ 32\}\rightarrow\{8\}\{3\ 7\}\{9\}\{5\ 32\}\rightarrow\{8\ 9\}\{3\ 7\}\{5\ 32\}\rightarrow\{3\ 7\ 8\ 9\}\{5\ 32\}\rightarrow\{5\ 32\}\{3\ 7\ 8\ 9\}$

本題共有 $3$ 個子題,每個子題有多筆測資。
第一子題: $N\le 3\times 10^2$,全部解出可得 $20$ 分。
第二子題: $N\le 3\times 10^4$,全部解出可得 $30$ 分。
第三子題: $N\le 3\times 10^5$,全部解出可得 $50$ 分。

標籤:
binomial heap 模擬
出處:
112學年度新北新莊高中校內資訊學科能力競賽 [管理者: liaoweichen1 ... (M_SQRT) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」