0%

Description

每張信封上面最多可以貼上h張郵票,請設計k種面額,並求出能組成的連續面額最大值。
例如當$h=3, k=2$,1和3元的面額最多可以連續從1組到7。

Read more »

Description

Jimmy的辦公室在森林的一邊,而他的家在森林的另一邊。
Jimmy想要每天都走不同的路徑回家。但是他也不想要回家太晚,所以他總是選擇一條可以朝他家「前進」的路徑來走。所謂「前進」指的是他會選擇從A點走到B點如果B點存在一條到他家的路徑長度比A點到他家任一路徑的長度都來的短的話。請你算出Jimmy共有多少種不同的路徑可以走。

Read more »

Description

題目有三種操作:
1 p s: 在當前字串位置p後插入s字串。
2 p c: 將當前字串位置p後面連續c個字符移除。
3 v p c: 在版本號v的字串中,在位置p之後印出c個字元。

由於怕離線處理,因此輸入的數值會進行加密:
每個數字會增加數值d,其d為當前打印字符c的個數。

Read more »

Description

Erin是一個開火車工程師。他喜歡把車廂按照其重量來安排,重的車廂排在前端。
不幸的是,把車廂排序並不是一件容易的事。你只能將一節車廂加在一列火車的前端或後端。
各個車廂來到火車站的順序及其重量是已經知道的。當每節車廂來到的時候,Erin可以把它加到火車的兩端,或者不加進去。最後,火車的總車廂數是越長越好,不過要記得車廂得按照重量大小排列。
給你按照出現順序各車廂的重量,Erin最長可安排車廂的長度是多少?

Read more »

可持久化線段樹適用於查詢不同版本的線段樹,其運作方式非常簡單,就是將要更改的點先複製一遍,未更改的點則不動。而且每新增一個節點,就建立一個新的root,所以我們就可以透過不同的root來讀取不同版本的值。

Read more »

Description

給定一張無向圖,有三種操作:

  1. D x :刪除第x條邊
  2. Q x y :查詢x所在集合裡面第y大的數字,若查詢失敗,則此次查詢的結果為0
  3. C x y :將第x點的值改成y

最後輸出所有查詢的平均值。

Read more »

第一次DFS,son():先紀錄所有點的子節點(含)數目、深度等資訊。
第二次DFS,build():依據上次DFS的結果,優先選擇子節點最多的點構成重鏈。

Read more »

使用倍增法的做法來計算LCA。
先製作dp表,$dp[i][j]$代表$i$的第$2^j$祖先是誰,若不存在則為-1。
在查詢時,先將點$a$和$b$調整到相同高度,再一起慢慢往上移動尋找LCA。
時間複雜度:$O(N log N)$

Read more »