A
题意：\(n\) 块饼干，每块饼干有温度 \(t_i\)，吃一块饼干的代价等于 \(\vert t_i - lst\vert\)，\(lst\) 表示吃/喝的前一样饼干/水的温度。
给出初始水温 \(w\)，现在先喝一口水，以任意顺序吃掉 \(n\) 个饼干，求最小和最大的代价分别是什么。
最小：\(\max (w, \max t) - \min(w, \min t)\)。
如果 \(w \in (\min t, \max t)\)，由于喝水是没有代价的，可以从 \(w\) 先到 \(\min t\)，再回到 \(w\) 直接到 \(\max t\)；其他情况显然。
最大：从 \(w\) 在排完序的数组上左右横跳，枚举一下是 \(\to 1 \to n \to 2\) 还是 \(\to n \to 1 \to n - 1\)，最优性不会证明，反正很优。
B
题意：求 \(n\) 个点 \(m\) 条边的无向图定向成 DAG 的方案数。\(n \le 20, m \le \frac{n(n - 1)}{2}\)。
\(f(S)\) 表示 \(S\) 导出子图的方案数，枚举子集 \(T\) 作为入度为 \(0\) 的点，满足每个点互相独立：
\[f(S) = \sum_{T \subseteq S\land T \text{ 是独立集}}g(T) \cdot f(S \setminus T) \]直接累加会算重，\(g(T)\) 表示集合 \(T\) 的容斥系数。
\(f(S \setminus T)\) 实际意义表示钦定集合 \(T\) 入度为 \(0\) 的方案，我们要让他变成入度为 \(0\) 的集合恰为 \(T\) 的方案数。
显然钦定 \(T\) 的方案会被所有 \(T\) 的非空子集恰好算一遍，容斥系数需要满足：
\[1 = \sum_{i = 1}^{\vert T\vert}\begin{pmatrix}\vert T\vert\\ i\end{pmatrix}g(i) \]不难发现 \(g(T)\) 只与 \(\vert T\vert\) 有关，直接用 \(g(\vert T\vert)\) 表示。手算一下前几项：\(g(1) = 1, g(2) = -1, g(3) = 1 \cdots\)。
猜测 \(g(i) = (-1)^{i + 1}\)：
\[\sum_{i = 1}^{n}\begin{pmatrix}n\\ i\end{pmatrix}(-1)^{i + 1} = \bigg(-\sum_{i = 0}^{n}\begin{pmatrix}n\\ i\end{pmatrix}(-1)^{i}\bigg) + 1 = 1 \]符合条件。直接枚举子集 \(O(3^n)\)，在线集合无交并卷积优化到 \(O(n^22^n)\)。submission
C
题意：
标签：12,饼干,vert,min,max,sum,CSP2024,pmatrix From： https://www.cnblogs.com/Luxinze/p/18391678