Comment on Problems

2024 March (Spark.md)

本部分是从古老文档 Spark.md 里摘录的，其余的部分过于像流水账，就不贴了

原属于三月的部分下午考题

P2573 [SCOI2012] 滑雪

注意到题目是求一个特殊有向图的最小生成树。

考虑 Prim 与 Kruskal 算法的精髓，实际上是考察了所有可能扩大生成树的转移，所选择的最小的一个可以扩大生成树的转移。

让我们考虑直接按照边权选取会发生的事情， 1-4-5 会被选择，实际上，答案应该是 1-5-1 。这是因为，这种算法并没有考虑最下面那个节点的所有可能转移，实际上最下面 1 的那条边是不可以反向使用的，在正常的图里它可以扩大生成树，这个图里不能。所以前面我们这个转移是没有考虑完善的，我们没有考虑所有转移就草率地做出了决策，这就有问题了。所以，MST贪心的正确性，就是在于已经考虑了所有可能转移。

P4516 [JSOI2018] 潜入行动

是一道大背包

但是比较关键的Trick就是要利用子树的大小来限制转移的上下界，背包问题就是合并子树的贡献，跟启发式合并类似的，利用大的不会多的原理保证了合并的复杂度。

P8575 「DTOI-2」星之河

关键思想是把子树限制用DFN的大小关系来表达，然后转换成偏序问题，使用 cdq分治解。

由于DFN序是只有可能包含或者不交的，所以DFN大小的四维偏序可以转换成三维

P2466 [SDOI2008] Sue 的小球

关键技巧是 费用提前计算 。应该在作出当前决策的时候把对后续决策的负面影响计算在当前决策的费用中，避免了难以表出损耗的问题。

以上就是所有的书中对该技巧的解读。

我觉得，其实还不是能不能表的出这个问题，考虑暴力这个问题，在没有加入时间到状态时，你做的所有决策都是一个贪心式的纯考虑当前最优不顾全局最优的一种决策，之后你没办法用这种决策转移，因为它很可能不是全局最优的。把费用提前计算，就相当于加了一个状态，把它压到答案里，相当于是贪心了，把各个状态之间的干扰去掉了，比如我之前这个时间是要影响下一个转移的代价的，现在我先计算了，下一个状态可以看作是基于某个转移之后所在的一个新起点开始转移。对于DP，你子问题要有依赖关系，但是不能有干扰，就是要保证有最优子结构性质。

所以我认为不能叫做提前计算，因为这本来就是这个转移带来的代价，是后续要选择这个转移的代价，是在当前综合了全局的最优决策，这样做保证了有最优子结构性质，所以这个Trick更像贪心（所以这个题加一个时间维应该也是有正确性的）。

P3224 [HNOI2012] 永无乡

FHQTreap+启发式合并

总结两种可以把不可合并数据结构换成可并或者把不可在线数据结构换成在线的方法：

• 不可并换可并：启发式合并，复杂度多一个log

• 不可在线换在线：二进制分组

所以我们所说的暴力数据结构，就是在平衡操作次数和数据结构大小，而前者常与这个数据结构的数量有关（这令人想到根号分治），这种通常是元素数量是固定的时候才是对的（想想线段树合并）。

关键就是：

大的不会多，小的不会大

P7150 [USACO20DEC] Stuck in a Rut S

本题是按照“拓扑序”模拟。

这样就不必考虑已经转移的状态再被影响，这就是更新成环的情况。这个就是“无后效性”，其实上面第一题也有这样类似的想法。

P4211 [LNOI2014] LCA

首先把所有的贡献叠在一张图上可以看出答案就是 \(path(i\to root)\cap path(z\to root)\)

在信息可差分的时候，可以通过前缀和避免从数据结构中删除

P8903 [USACO22DEC] Bribing Friends G

这道题的关键在于要发现性质。。。

当问题困难的时候，思考通过枚举答案的方式转换成判断问题或者帮助发现性质。

可以发现如果确定了答案的集合，那么考虑调整答案的集合能否更优，发现答案集合中 \(x\) 较大的如果用了冰淇淋就完全可以把冰淇淋用在 \(x\) 更小的奶牛上面置换出一个mooney，这样既没有改变mooney的总数又节省了一部分冰淇淋，所以就可以推出冰淇淋一定是集中使用在 \(x\) 更小的奶牛上。

P6005 [USACO20JAN] Time is Mooney G

这道题体现了DP与SSSP问题之间的关系。

首先时间肯定是非常重要的一个状态（这点通过思考暴力容易得出），所以如果建成分层图就是分出若干时间层，此时已经可以做了，然后转成DP，也是自然的。

典中典 P2802 回家 和去年没做出来的 P9751 [CSP-J 2023] 旅游巴士

P3899 [湖南集训] 更为厉害

题面amazing啊

线段树合并的做法显然。

用DFN序转化为序列上问题，就得到了一个特殊的三维偏序问题，正如上面“P8575 「DTOI-2」星之河”的第一篇题解所说，DFN序的这种特殊的n维偏序是可以看作n-1维偏序做的。

P7300 [USACO21JAN] No Time to Paint S

本题中有贪心结论如下：

• 考虑最优方案是将整个区间先全涂上最小的颜色，然后再按照最小颜色分治

• 考虑证明：

• 如果不是先涂最小颜色，那么还有操作可以选择：

  • 可以涂更浅颜色，这完全没有用

  • 可以选择涂更深颜色，你不能跨越这些最小颜色的点

    这时候的合法操作集是和上面最优策略操作之后的大小一样的，选择先涂最小颜色，这是具有决策包容性的

  • 可以选择涂这些最小颜色的点，那还不如直接涂一整个区间

  • 证毕

• 故可以分前后缀来考虑

然鹅之前的 P4170 [CQOI2007] 涂色 ,就是没有颜色深度限制的此题中，就没有这个性质。

这是因为题目的限制不够强，可能的转移决策不止这些，就是说你是可以跨越最小颜色的点，就是不满足了上面的决策包容性。仍然考虑可以节省操作次数的方法，就是要大段地涂上一个颜色把整个区间同一颜色的覆盖，可以发现先给一段区间涂上一个底色是没有影响的，之后答案不会变劣，还会变好，这里就颇有一种DP的感觉，就像上面那个 “P2466 [SDOI2008] Sue 的小球” 中我说的这样，这就是一种状态，做出这个决策之后不影响之后做出的决策，所以又想到DP就是优化搜索的枚举顺序，我可以先涂一个底色然后再进入小区间涂色，这不影响，然后小区间涂色的答案又能够组合成大区间的答案，只要我给他提供所有的可能性，枚举了所有的小区间划分，就行了，还有要注意到无后效性，我最少就只要2个区间就能拼成一个大区间，如果分三个那就可以组合其中任意两个，这就是为什么区间DP里面都是枚举断点。这就是递归地分析。

写不下去了，这个只能自行领会。抱歉用了太多逗号。

P3163 [CQOI2014] 危桥

其实这个交换两个点的方法可以这样理解：

• 第一次 \(a_1\to b_2\) ，错误的

• 第二次如果还是乱流，就是 \(b_2\to a_2\) ，那我就可以把第一次乱流的流量通过这条路径送到正确的 \(a_2\) ，这样不就行了吗？你可能会觉得万一路可以走的次数不够呢？那显然把两条路径合成一下就没必要重复走一段路了，就是这样：

P8900 [USACO22DEC] Barn Tree S

简单贪心，显然子树内如果能够自己补充自己那最好，基础的思想就是尽量堆积到一定量之后再移动干草。

P6573 [BalticOI 2017] Toll

可以发现每一次走一步肯定会到达下一层，所以要走几步到达目标层的步数是固定的，走一步是可以到哪里是可以知道的，这种一个大的转移目标可以由若干小的决策步数拼起来的，就可以适用倍增优化，当然，如果空间允许，这个问题也可以在层数上分块