Colythme

首先每次买卖一定是在某天 $k$ 以当时的最大收入买入，再到第 $i$ 天卖出，那么易得方程： $$f_i = \max \{\frac{A_iRate_kf_k}{A_kRate_k + B_k} + \frac{B_if_k}{A_kRate_k + B_k}\}$$ 再令 $$\left\{\begin{aligned} x_k = \frac{Rate_kf_k}{A_kRate_k + B_k} \\ y_k = \frac{f_k}{A_kRate_k + B_k}\end{aligned}\right.$$ 则有 $$\begin{aligned} f_i &= \max \{A_ix_k + B_iy_k\} \\ y_k &= - \frac{A_i}{B_i}x_k + \frac{f_i}{B_i} \end{aligned}$$ 那么现在需要找到一个点 $(x_k, y_k)$ 使得直线的截距最大 由于斜率和横坐标皆不满足单调性，可以用平衡树等维护，这里使用CDQ分治实现 实现过程如下： Ⅰ 将数据按照斜率$\frac{A_i}{B_i}$降序排 ...

后面发现这是某次考试的原题来着 怕是太久没打过状压然后连 $k \le 5$ 可能要状压这么明显的提示都给无视了然后就随便敲了个矩阵树骗了 $50$。。。 好所以这题是一道状压 令 $state$ 表示对于 $i$ 点（包括它本身）的前 $k$ 个点的连通状态，$e.g. \{1, 1, 2\}$ 表示 $\{1, 2\}, \{3\}$ 点分别连通 注意为了去重要用最小表示，于是即使当 $k = 5$ 时状态数也不过就 $52$ 个而已了 再令 $f_{i, j}$ 表示前 $i$ 个点且 $i$ 点连通状态为 $j$ 时的方案数，$g_{i, j}$ 表示状态 $i$ 转移到状态 $j$ 时的方案数，则有方程$$f_{i, j} = \sum_k f_{i - 1, k} * g_{k, j}$$可以发现这就是一个矩阵转移式，故直接矩阵乘法即可 那么至于计算 $g_{i, j}$ 则枚举 $i$，及当前点与前面点的连通状态 $state$（二进制表示），然后并查集维护一下，判断当前 $state$ 是否会与之前冲突（连边后无环且原状态中的最前点（即会被刷掉的点）与当前的 $k$ ...

首先普通 $DP$ 式子很好列 令 $f[i][j]$ 表示 $i$ 个小朋友分 $j$ 个糖果且每人至少一颗的答案，则有$$f[i][j] = \sum\limits_{k = 1}^j f[i - 1][j - k](Ok^2 + Sk + U)$$接下来用生成函数优化该式 令 $g[k] = Ok^2 + Sk + U$，则$$f_i(x) = f_{i - 1}(x)g(x)$$其中 $f_0(x) = 1$ 所以答案即为$$[x^M] \sum\limits_{i = 0}^A f_i(x) = [x^M] \sum\limits_{i = 0}^A (g(x))^i = [x^M] \frac{1 - (g(x))^{A + 1}}{1 - g(x)}$$ 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 ...

挺有趣的一道 $dp$，两问实际上就相当于是第一问是第二问的部分分 第一问一开始以为要 $dp$，然而并不用 对于这种高度然后求方案数的题，可以只考虑其相对位置，因为只要所有相对位置确定了，那么整个序列就唯一确定了 首先肯定要先将它们以高度为第一关键字（由大到小），关键值为第二关键字（从小到大）排序 那么对于第 $i$ 座山，它就会有 $\min (i, key_i)$ 个相对位置可以占，因为有相同高度的山峰，所以还会多出 $same$ （$i$ 前面与其高度相同的山峰的个数）个位置 那么 $ans_1 = \prod\limits_{i = 1}^n min (i, key_i + same)$ 第二问症结还是在于相同高度的山峰会产生重复 但是显然如果一次性确定好所有相同山峰的位置是不会产生重复的，故考虑将每一组相同高度的山峰放在一起处理 为了避免重复，需要强制令这些相同高度的山峰放置有序，即后放的一定在先放的后面，那么就可以令 $f_{i, j}$ 表示（当前组相同高度山峰）前 $i$ 个放在前 $j$ 个位置上，并且第 $i$ 放在第 $j$ 个位置的方案数，则有（下示方程表示区 ...

显然直接 $01$ 背包会超时并且超空间 套路：分层 $DP$ 「考虑将每个子结构看作一层（也就是包含了不止 $1$ 个物品的信息），并且大层不会对小层造成影响，可以考虑先进行每一层的自我更新（即用当前层物品更新当前层答案），再进行层的合并，此时考虑低层对高层的影响」 正题 那么这题有一个特殊性质： $V_i = a \times 2^b$ b值大的物品不会影响零碎剩余的重量上限。 将物品按b值分阶段处理。 那么就是分层 $DP$ 先通过普通的 $01$ 背包更新当前层自身最优解 再进行层合并： 令 $g_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$ 的最优解，$f_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$，并且再加上 $V_{total}​$ 的 $1…i - 1​$ 位的最优解 那么对于第 $i$ 层，枚举当前 $j$ 对于转移，枚举在自身层内消耗的空间 $(j - k) \times 2^i$，那么还剩下 $k \times 2^i + V_{total}\{1…i - 1\}$ 的空间，分配给上一层，那么可得转移方程为 （注：$w_i ...

这题一直往 $\text{dp}$ 去想，然后就没了 所以其实并不用注意之前的可看见的建筑的最大值是多少，若把那些能够被看见的建筑之间构成的区间看作一个小组，那么能够被看见的建筑不过是在当前小组中选择一个最大值最为代表排在左（右）边罢了 所以现在问题转化为将 $n - 1$ 个建筑分在 $A + B - 2$ 个盒子，然后盒子内可以随意排列的个数 然后上述问题实际上可以将每个盒子看作一个圆，故问题又转化为 $n - 1$ 个建筑构成的 $A + B - 2$ 个圆排列方案数，即斯特林数 $S (n - 1, A + B - 2)$ 然后要在其中选择一些放左（右）边，故答案即为$$ans = S (n - 1, A + B - 2) \times \dbinom{A + B - 2}{A - 1}$$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream> ...

题意求一个 $n$ 点 $m$ 边的 $DAG$ 的最长反链，在第二行输出构造的其中一种方案，在第三行输出在保证最长反链的前提下，每个点是否能够设置为反链中的点 题解反正证明也不会，就记录一下具体方法 最长反链：对 $DAG$ 点集 $V$，最长反链为一个集合 $S \subseteq V$，满足 $\forall u \in S, v \in S$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$ 根据 $\text{Dilworth}$ 定理，一个 $DAG$ 的最长反链大小等于其最小可重链覆盖大小 对 $DAG$ 传递闭包后，最小可重链覆盖大小可转化为最小不可重链覆盖大小，即最小路径点覆盖 最小路径点覆盖：将 $DAG$ 用若干不相交的链覆盖，即每个点最多被经过一次，最小使用链的个数 那么最小可重链覆盖则是类似，不同之处仅在于每个点可被经过多次 最小路径点覆盖大小 $=$ $n$ $-$ 该 $DAG$ 拆点二分图的最大匹配大小 那么 $\text{Subtask1}$ 就做完了 把 $DAG$ 拆点后最小路径点覆盖就相当于是求该拆点二分图的最大独立集 接下来开始 ...

题意即为带修（临时）最短路 先随便提一条最短路出来，那么修改可分为四种情况： 该边在最短路上，且数值变小 该边在最短路上，且数值变大 该边在最短路外，且数值变小 该边在最短路外，且数值变大 那么对于情况 $1, 3, 4$，显然是十分容易处理的，那么问题就在情况 $2$ 设最短路经过点 $e_1, e_2, e_3, …$ 考虑到新的最短路必定与原最短路有相同的一段前缀与后缀（可以为空），设 $dis2_{i, j} (i < j)$ 表示不经过路径 $e_ie_j$ 的最短路，所以答案即为 $\min \{dis2 (e_ie_j) (i < j)\}$ 那么便两遍 $Dijstra$ 分别求出 $1, n$ 到每个点 $p$ 的最短路 $pre_p, suf_p$，并且对于最短路上的点 $e_i$，求出其在最短路上的前驱边 $from_{e_i}$ 与后继边 $nxt_{e_i}$，对于每个不在最短路上的点 $p$，求出点 $1$ 至 $p$ 中最后一个在原最短路上的点的后继边 $from_p$ 及点 $p$ 至 $n$ 中第一个在原最短路上的点的后继边 $nxt_ ...

题意给定 $n$ 个线段，每个线段有一个权值 $w_i$，每次取轴上一点，获得的权值为选择的覆盖在当前点上的线段的最大权值，求最终覆盖所有线段后需要的最小权值 题解好吧是一道非常水的区间 $dp$ 然而我并没有想出来所以我是真的绝望 先把 $l_i, r_i$ 离散化后令 $f_{l, r}$ 表示完全覆盖区间 $[l, r]$ 的线段的最小权值，设完全处于 $[l, r]$ 的线段中权值取最大值的线段 $p$，则有转移方程$$f_{l, r} = \min \{f_{l, k - 1} + f_{k + 1, r} + w_p\} (l_p \le k \le r_p)$$所以注意一定要完全覆盖，$[l, k - 1], [k + 1, r]$ 才不会对 $[l, r]$ 造成影响，于是我就卡这儿了 谨以此文纪念我逝去的智商 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 ...

首先因为点数不多，可以考虑先在 $4r \times c$ 时间内将每个点朝每个方向可以到达的位置预处理出来，建成图 那么现在容易看出是斯坦那树问题，所以考虑将问题简化一下： 现在给定 $n$ 个不同级别的机器人，将两段级别的机器人合并需要花费 $c_i$，那么将所有机器人合并的最小花费是多少 这个问题显然使用区间 $DP$ 可以解决，那么扩展到斯坦那树上即可 令 $f[l][r][i]$ 表示区间 $l, r$ 的机器人合并后位于位置 $i$ 的最小花费，则有$$f[l][r][i] = \min \{f[l][k][i] + f[k + 1][r][i]\}$$以及$$f[l][r][i] = \min\limits_{p link to i} \{f[l][r][p] + 1\}$$第二个式子直接 $SPFA$ 会超时 但是观察每条边的贡献都为 $1$，所以可以将 $SPFA$ 优化成 $BFS$ 的复杂度 类似堆优化的思想，开两个队列，一个存初始的经过 $f$ 排序的点，一个存被松弛的点，由于边的性质及 $que1$ 经过排序的原因，所以 $que2$ 一定也是按 $ ...