2025.6.2 问我怎么挂的今天做题。
[洛谷 P2833] 等式 & [SGU 106] The equation
板子题啊，可是改了好久。主要死在向下、向上取整时没用 double（因为有负数）。
[SPOJ NWERC11A] Binomial coefficients
这道题自己想到了枚举 ，二分 ，也想到了会爆 long long，可是没想到枚举。
对于 ，进行二分；...
一眼题啊。设 左侧第一个不比它小的数的位置为 ，它右侧第一个比它大的数的位置为 。（这样可以保证既不漏算又不重复计算。）那么对于 ，它可能作为最大值的极长区间显然是 。这个区间又被 分为左右两段。设两段中较短的一段长度为 ，较长一段长度为 ，总长度为 。那么 可以带来以下贡献：
；
；
。
将第三组式子拆为：
。
于是维护两个差分数组即可。第一个差分数组 维护的实际值就...
本文提供一种另类做法。虽然我的代码从实现以及常数上都更劣一些。
考虑原式的几何意义，即在数轴上的 个区间内各选一个点使得这 个点两两距离之和最小。
考虑什么时候距离之和最小，显然是所有点都尽量向某一个位置靠拢时。所以钦定中心点，让其它所有点都尽量向这个点靠拢，再暴力计算贡献。时间复杂度 。
注意到，中心点取在非端点显然时不会更优，所以可以离散化。时间复杂度 。
现在考虑优化计算原式的过...
本文是一篇 CQ CCPC 流水帐游记，想了解题目做法的请移步。
Day 和 qcz, jmr 分到一组了。赛后一结算，jmr 是 MVP，hyc 是躺赢狗。
队名叫作 grass8cao。
Day 时间安排出来了，结果是当天坐高铁往返，早上 6:20 就出发呜呜呜。
Day 0早上 5:50 就起床了。
9 点左右高铁到达重庆西。
10点过一点到考场开始比赛。策略是 jmr 和 qcz 轮...
想必大家都会积木大赛。
若修改 ，考虑如何让它带来的贡献最小。根据积木大赛的结论，只需让 ，这个位置就不会带来任何的贡献，可以认为我们删除了第 个位置。显然，，总存在 满足以上条件。
那么问题就变成了，原本有 个位置，可以删除最多 个位置，求最小答案。于是自然而然地想到了 DP。
设 表示现在在第 个位置，删除了 个位置，上一个没有被删除的位置是 的最小答案。转移方程：
时...
好题啊好题。记 表示矩阵的第 行的内容（用 bitset 维护）。
考虑什么时候有 。因为与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。所以有 或 ，前者对应 是 的祖先，后者则对应 是 的祖先。容易证明这是一个充要条件，那么若 ，则一定不存在 与 。
接下来考虑一种特殊情况：，此时 在一条没有任何分岔的一条“链”上，那么这条链上的节点的位置就...
2025.5.5 了跟了一样今日歌曲：Fifteen
又断更了半个月。
前几周学了一下 AC 自动机，但是学了跟学了一样。
前几天终于把那套题出完了，但是出了跟出了一样。
昨天考试，听了评讲，但是改了跟改了一样。
晚上打 ARC，但是打了跟打了一样。
[Atcoder ARC197C] Removal of Multiples
唐题啊，但是赛时一直在想整除分块之类的，结果没想出来。
但是这...
假设 是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 大的数（记作“较大数”）的和减去前 小的数（记作“较小数”）的和。
容易发现，当我们只能选相邻的数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。
当 是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶...
考虑正难则反。问题转化为：
一个环上有 个物品，颜色分别为 ，每次操作选择两个数 使得 ，将 中的每个物品的颜色都设为 。（下文将这种操作称为“漂白”。）一次操作的代价为 。求将整个环漂白的最小总代价。
先断环为链。设 表示将 漂白的最小代价，那么显然有 。
设 表示使 能够漂白的最小代价，那么显然有 。当 时，有 。
答案即为 。
确简单的啊，可是自己就是想不到。
考虑计算一个数的斑马值。贪心地，尽量选大的斑马数减即可。
考虑 DP，设 表示 中斑马值为 的数的个数。那么显然有 ，其中 是不大于 的最大的斑马数。具体地， 表示 中斑马值为 的数的个数， 表示 中斑马值为 的数的个数。
记搜即可。
