- coin
首先有个背包，是 \(n^2\) 的，然后我就不会了，很疑惑为什么不给背包的分儿，估计是大家都太厉害了，直接就能想到正解吧
然后你考虑一个贪心，设 \(a_i\) 就是选一个的，并设 \(b_i\) 为原来的 \(a_i + b_i\)，你发现这样你就解决了选三个的情况，也就是选一个再选两个就行了
然后你对于这两个数组直接从大到小排序，只选一个肯定就是 \(a_1\)，然后我们从两个的情况开始考虑，考虑多选一个的方案都有什么
1.从 \(a_i\) 没选的里选一个最大的
2.从 \(b_i\) 没选的里选一个最大的并且从 \(a_i\) 已经选了的里选一个最小的删除
这是对的，因为你每次都是对当前的能选到的最大情况考虑了，当前情况和前一个的情况差别最大的也就是退回一个选一个的操作并且选两个，所以这一定对
- string
赛时会了 \(50pts\)
\(A\) 性质是好做的
\(B\) 性质以及前面的暴力怎么做，你发现如果你把前面的贡献全都记录下来，那么新一轮的贡献只会有两个串拼起来和新加的 \(d\) 串的贡献
所以我们考虑记录下来每个串的前后 \(ls-1\) 的字符是啥，然后后面拼接的时候可以用 \(KMP\) 计算贡献，这样复杂度应该是 \(k|S|+\sum d\) 的，就能过 \(50\) 了
然后考虑正解