n373. 7. 鮭魚收藏家 - 高中生程式解題系統

內容

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

　　以下將以 $[a_{1}, a_{2}, \dots, 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 \leq N \leq 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

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

　　範例輸入 #2 的十筆操作，每本所包含的鈔票如下：
存 $5 \to {5}$
存 $2 \to {2} {5} \to {2 5}$
存 $9 \to {9} {2 5}$
存 $4 \to {4} {9} {2 5} \to {4 9} {2 5} \to {2 5 4 9}$
取 $1 \to {2 5 4 9} \to {5} {4 9}$
存 $32 \to {32} {5} {4 9} \to {5 32} {4 9} \to {4 9 5 32}$
存 $7 \to {7} {4 9 5 32}$
存 $3 \to {3} {7} {4 9 5 32} \to {3 7} {4 9 5 32}$
存 $8 \to {8} {3 7} {4 9 5 32}$
取 $3 \to {8} {3 7} {4 9 5 32} \to {8} {3 7} {9} {5 32} \to {8 9} {3 7} {5 32} \to {3 7 8 9} {5 32} \to {5 32} {3 7 8 9}$

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

標籤:

binomial heap 模擬

出處:

112學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

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