某岛

… : "…アッカリ~ン . .. . " .. .
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 喜欢出。。