20241022 总结

贪心专场，一道都不会

贪心思维太差了，以后对于数据的范围要仔细计算不要再出现数开小了的情况

预期：150 实际：50

P8161 [JOI 2022 Final] 自学 (Self Study)

二分秒了，记得开 int128

P4144 大河的序列

贪心，考虑按位贪心，我们尽可能地让最大位最大

那么考虑什么时候最大位最大，很明显当只选这个的时候可以让这一位达到 2 倍的贡献，而最大位最大时，不存在一个最大位比这个小的但是比这个答案优秀的情况，以此类推我们会发现，我们是在做一个多关键字排序，而排出来最大的，其实就是所有数中的最大值

结论：最大值 * 2

P2326 AKN’s PPAP

和 P4144 的思路很想，都是往按位贪心去想，不过这个题不存在 2 倍贡献，所以贪心的选择这一位所有为 1 的，当这些为一的数的数量不为 1 那么我们可以合成一个当前为一的，那么我们肯定优先合并这些，所以将其他的删掉，否则我们跳过这一位

P10334 [UESTCPC 2024] 饮料

考试的时候其实想出来了，但是不会处理，设计程序能力有待加强

首先一杯饮料肯定是越后制作越优秀，所以考虑如何安排制作序列

我们可以倒着做，将每一位从交货时间开始平铺过去，如果有饮料占了位，那么自己就再往前放

我们会发现一个问题，比如样例，当我们做完 2 体积饮料后，在本该取 2 的人的时候制作 4，那么本该取 2 的人将会取 4 导致后面的不满意，所以我们得将 2 放大到 4

考虑如何实现，首先得倒这做，我们只要每次在加饮料的时候和上一个未被取走的饮料取最大值即可

P9235 [蓝桥杯 2023 省 A] 网络稳定性

我们发现因为只要联通，所以我们不管怎么跑，都是合法的走法，所以问题转化为选出一些边，让其变成一棵树，使得路径的最小值最大，我们考虑用最大生成树然后跑两点路径即可

为什么一定是两点路劲呢？

因为要求的是最小路径最大，那么必经路外的不会产生更优秀影响。

总结

贪心确实很差，以后遇到贪心题可以多分析一些性质，也许性质可以帮助我们确定正解。

可以用贪心来解决一些类似于限制了操作的一些问题