-
P8817 [CSP-S 2022] 假期计划
首先把 ， 转换成两点距离 考虑到枚举四个点不行，但是 可以，我们考虑枚举两个点，然后 找出剩下两个点 首先 预处理每个点 之内的点，并求出这些点中到 距离 的权值最大的点 ，注意不要选到自己了 我们考虑答案为 但是则海洋 可能与 重复，这样是不合法的，所以我们每个点要预处理前三大的点权点，因为至多为第一大第二大都被 占掉 ， 123456789101112131415... -
P6064 [USACO05JAN] Naptime G
考虑不是环怎么做 我们只用考虑当前选不选 考虑前 个数，选了 个，当前数选/不选我们考虑跨过 的情况，一定强选了 睡觉，我们再钦定 强制睡觉，这样就可以得到等效的情况 即 ，答案取 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354... -
浅谈随机堆
Here’s something encrypted, password is required to continue reading.
-
P9378 [THUPC 2023 决赛] 物理实验
字典序/次幂贪心模型 显然从 ，我们选择的答案是一个前缀状态，保住一个胜过后面所有的 问题等价于，当前有答案集合 ，求加入元素 是否合法 判定就是枚举每一轮宇宙射线 我们考虑到已经有 了，我们可以直接找出来每轮宇宙射线轰掉哪个，即未被轰掉，未被保护的第一个元素 此时可以得到另一个性质 ， 中的每一个元素都必须要在被轰掉之前做完，判定时候即可求出每一个元素最晚的做掉时间， 问题等价于，我们... -
P7789 [COCI2016-2017#6] Sirni
显然是 的优化建边题 优化的原则就是 就没必要建 显然要把所有数去个重，重复的边权都是 我们考虑到这个边和值域有关，可以接受 的复杂度，显然想到枚举倍数，因为这样做是 的 我们考虑到为什么枚举倍数最优，即怎样在枚举倍数后建边不劣 我们设倍数为 ，当前数为 ，枚举每个 区间内第一个数建边 考虑区间内两数 首先我们讨论 的大小可以得到 的边等价于 123456789101... -
P7249 [BalticOI 2012 Day1] 移动网络
离最近的点最远的距离 考虑二分答案，问题转化为线段是是否有一个点到每个点的距离都 但是我们肯定不能枚举线段只能枚举点，我们考虑怎么把问题转化到点上面 每个点相当于画了一个 的圆，问题等价于是否存在于一个线段上的点没有被任何圆覆盖到 由于已经排好序了，我们从 考虑即可 每个点可覆盖的范围是 直接区间做并即可 1234567891011121314151617181920212223... -
CF708C Centroids
先考虑以 为根的情况 考虑到至多只有一个 的子树 ，我们肯定找是 中那个最大的 的子树 ，然后扣下来接到 上面，再判断能否成为重心，即 我们考虑如何维护这个过程，我们先维护最大的儿子 ，然后求每个 内最大的 的子树 ，记为 和 这样就把问题转化成 我们考虑换根解决剩下的部分，我们还需要维护 的补树中的 ，传给 ， 的 此时显然为 中的次大子树 中的 ，所... -
P5426 [USACO19OPEN] Balancing Inversions G
考虑到答案的上界为逆序对的数量 证明：考虑每一次操作都是有效操作，否则数组必然已经不减 也可以考虑先将最大数交换到最后，由于是相邻两个数交换，需要交换的次数为最大数后面的数的个数（可以看做是最大数的逆序数），然后，交换过后，去除最大数，再考虑当前最大数也需要其逆序数次交换 则每个数都需要交换其逆序数次操作，则总最少交换次数为序列总体的逆序数 注：考虑无序数组交换任意两个元素，最少交换次数 ... -
浅谈单调序列绝对值和最小化
我们考虑尽可能让 ，即让 序列中的每一个数都在 中出现，这样就相当于把值域压缩到了 即，在满足答案最小的情况下，一定存在一种方案使得 考虑数学归纳法， 成立 若 ，则令 否则，必然存在 ， ，由中位数的性质即可推得 具体来说，线性 肯定是要分段划分序列做 连续上升段 ，则 连续下降段 ，则 $b_i=a_i \sim a_j$ [P2893 USACO08FEB] Mak... -
P8365 [LNOI2022] 吃
我们先贪心全选乘，考虑把乘集合 元素加入加集合 首先 的肯定加入 ，此时 其次我们至多加入一个元素，否则考虑这两个元素 令 则 的贡献从 考虑加入 元素的贡献， 直接取后面那个式子的最大值 注意计算 的时候不要取模，否则后面那个就错了，用 long double 算那个分数 123456789101112131415161718192021222324252627282...
