某島

… : "…アッカリ~ン . .. . " .. .
October 21, 2021

Facebook Hacker Cup 2021 Round 2

A
貪心

B
做法有很多,比賽時用的是線段樹合併。

C
小數據貪心模擬一下,大數據需要用數據結構維護這個貪心過程。

Problem D. String Concatenation
雖然題目叫 String Concatenation,但是是個背包問題,和字元串完全木有關係。
做法是暴力亂搞,亂搞的方法貌似有很多。假設 k 可以無窮大,那麼根據鴿巢原理(pigeonhole principle),在 n >= 25 的時候就一定有解,考慮 k 很小,那麼也可以根據生日悖論(birthday paradox)可以設計 n <= 1000 的解法。
然後一般情況下再搞一些剪枝,歸約到 n <= 1000 以內即可。這種利用生日悖論的題好像以前 gcj 喜歡出。。