October 21, 2021
贪心
做法有很多，比赛时用的是线段树合并。
小数据贪心模拟一下，大数据需要用数据结构维护这个贪心过程。
虽然题目叫 String Concatenation，但是是个背包问题，和字符串完全木有关系。
做法是暴力乱搞，乱搞的方法貌似有很多。假设 k 可以无穷大，那么根据鸽巢原理（pigeonhole principle），在 n >= 25 的时候就一定有解，考虑 k 很小，那么也可以根据生日悖论（birthday paradox）可以设计 n <= 1000 的解法。
然后一般情况下再搞一些剪枝，归约到 n <= 1000 以内即可。这种利用生日悖论的题好像以前 gcj 喜欢出。。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。