2019-Sp053-lyk

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(1.png,700px)]]

[[Image(3.png,700px)]]

[[Image(2.png,700px)]]

[wiki:2019-team2 返回Runespoor]


[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001434 contest]

== 流水账 ==


== 总结 ==

'''zqq: ''' 连续几天都没有打好。

            今天我们犯了很多错误。比如D题因为是原题没有相对正确的方向。J题博弈没有去翻板子，打表打了很久。

            更多的我觉得是我们没有足够重视训练，显得有些松散。

            最近有好多题我们一开始方向都是错的，在错误的方向上挣扎了很久。还有好多知识我们没有掌握牢，比如我的数据结构其实很多东西早就忘了，用什么技巧做什么题已经非常不熟练了，导致我经常在错误的方向上想很久。比如昨天的D题（时间分块），前天的B题（均摊线段树）。

            可能也有最近连续训练大家比较疲惫的原因。

            我们也需要把以前见过的题目进行一些整理，梳理一下知识点，有些时候凭记忆是不靠谱的，经常被带偏。

            训练和比赛仍然需要注重策略，不能太随意。

            然后我需要更加静心，特别是在查代码的小错误上。减少调试时间和卡题！

=== 题解 ===

* D ： 分治背包。因为只会有一个物品不选满限制个数。一个很好写的写法是一开始先加入这种没有选满的物品，然后分治合并上去。复杂度O(nmlogn)

       也可以大力线段树维护凸包（李超树）。二次函数拆出来就是标准的斜率优化。但是要卡常，线段树要zkw才能过。因为每次转移限制长度相同，可以分成m / c段每次在一段的前缀和一个后缀上查询。复杂度O(nm)

       '''主要是一开始想到是ByteDance原题，一直在想convex hull trick，但是其实这个模型很难那样维护。感觉对这道题理解非常不深入！'''

=== 补题 ===

 * C : 

 * D ： zqq

 * G :