0103abc 的网站

先考虑暴力怎么做。容易想到 dp。先按照 $x$ 为关键字升序排序。根据经典套路可以设 $f{i,j}$ 表示当前执行了前 $i$ 个操作，当前一只手在位置 $yi$ 另一只手在位置 $j$，最少需要花费的代价。容易观察到不需要区分两只手，因此这个状态设计正确。 转移则分为下面的两个情况：...

为什么我不喜欢函数交互： image 其实这个题很简单。注意到限制给的很松，所以随便排除一些一定不合法的位置就可以过。考虑把相邻两个元素分为一组比较，把大的那个放到 $v1$ 数组中，小的那个放到 $v2$ 数组中。 此时 $v2$ 数组中所有元素都一定不是最大值，$v1$...

先观察题目的性质，可以发现： 拿到货物之后一定是将其直接运回到 $1$ 位置（可能会在别的地方再上货物，但是不会把已经上过的货物再拿下来）。 继续观察还可以发现：除了走的距离最近的那一次以外，其余每一次拿货物都把车厢拉满一定是最优的。 于是可以考虑 dp。设 $f_{i,j,k}$ 表示当前考虑了...

从某个 OJ 上 copy 过来一个简要题意： 给一个 $n$ 个节点 $m$ 条边的无向图，有 $k$ 轮操作，每轮操作选择尽量多的边删除。如果有多种方案，那么选择边权和最大的那个，但是要求删除的边中不存在环。 对于每条边，输出它在第几次操作被删除，如果这条边最后都没有被删除那么输出 $0$。...

先交换 $l,r$ 使得 $l\le r$。 此时想要从 $l$ 移动到 $r$，找到区间中最高的位置 $id$，高度为 $h{id}$，则显然在 $id$ 这个时刻移动到恰好 $h{id}$ 高度是最优的，而在每个位置往上走的花费都是定值 $4$，因此考虑在最开始就移动到 $h{id}$...

板子题，考虑平面图转对偶图，然后两个点连通的充要条件就是连接这两个点的边两侧在对偶图上对应的两个点不连通，一次断边操作就可以理解为是把这条边左右两侧在对偶图上对应的两个点连通起来，显然可以拿 dsu 简单实现。 一个细节是根据对偶图的定义，所有格点之外的区域也应该被整体单独编号。 总时间复杂度为...

选自 11 月做题笔记。 ~~NTT 练的不少了，换点反演练（）~~ 事实上可能不太算反演（） Subtask 1 注意到 $g(n)=d(n)$，此时有 $f(n)=\sum\limits_{d\mid n}\mu(d)d(\frac nd)=1$。 考虑证明该结论。上面这个东西是 $\mu$...

这我哪会啊 因为 $ai$ 时刻为奇数，所以考虑把 $ai$ 表示成 $2bi+1$ 的形式。此时区间 $[l,r]$ 的乘积即可以表示为 $\prod\limits{i=l}^r(2bi+1)$ 的形式。又因为答案是对 $2^{20}$ 取模的，且有 $2\mid...

选自 11 月做题笔记。 039. [P6012 [P5087] 数学 加强版](https://www.luogu.com.cn/problem/P6012) 这是不是生成函数板子啊/yun，容易发现答案就是 $[x^k]\prod\limits{i=1}^n(aix+1)$，这个东西形如 $n$...

先考虑比较暴力的做法。枚举选择的子序列最中间的位置 $i$，这样一来根据经典贪心结论，左右两侧都分别需要选 $\frac k2$ 个（对 $2\mid k$ 的情况需要处理左边多选一个还是右边多选一个）。对每个值不和 $i$ 相等的值，求出 $i$ 左右两侧第一个和其值相同的位置...