六省联考 2017
期末考试 \((\texttt{Easy} \ 0 / 0)\)
枚举所有成绩出完的天数，贪心制定方案即可。
相逢是问候 \((\texttt{Easy} \ 2 / 3)\)
首先需要 这个题，那么本题再套一个势能线段树即可。
但是很繁琐，比较恶心（也可能是我的实现太差了），可以用光速幂，也可以设阈值。
组合数问题 \((\texttt{Easy} \ 2 / 0)\)
想到矩乘就简单了。注意 \(k = 1\) 的情况。
摧毁「树状图」
雷哥题，考前做。
分手是祝愿 \((\texttt{Medium} \ 4 / 0)\)
好神啊。
发现关灯的最优方案肯定是从大往小了关，所以我们可以确定最优方案中要关哪些灯，并且显然最优方案唯一，于是我们就可以把初始状态看作最优方案中要操作的位置为 \(1\) 其余的为 \(0\)；把每次操作看成单点修改，那么会终止当且仅当 \(1\) 的个数 \(\le k\)。然后就可以直接 dp 了。。。
设 \(f_i\) 表示 \(1\) 的个数为 \(i\) 到 \(1\) 的个数为 \(i - 1\) 的期望步数，有方程
\[f_i = 1 + \frac{n - i}{n} \times (f_{i + 1} + f_i) \]移项可得
\[f_i = \frac{n + (n - i)f_{i + 1}}{i} \]于是直接 dp 即可，时间复杂度 \(\mathcal{O}(n)\)。
寿司餐厅 \((\texttt{Medium} \ 4 / 1)\)
精妙的网络流，反正我是没想出来。
考虑把问题转化为最大权闭合子图问题。
对于每个区间建立一个点，发现若 \([i, j]\) 被选，则对于 \(\forall i \le i' \le j' \le j\)，\([i', j']\) 都会被选，所以可以连 \([i, j - 1] \to [i, j]\) 和 \([i + 1, j] \to [i, j]\)，边权为 \(\infty\) 的边。
再对于所有代号建立 \(\omega\) 个点，其中 \(\omega\) 指值域。那么对于 \(\forall i\)，我们需要令 \(d_{i, i} \leftarrow d_{i, i} - a_i\)，因为选择它还会带来 \(-a_i\) 的收益。然后我们连一条 \(a_i \to i\)，边权为 \(\infty\) 的边，表示选择了 \(i\) 意味着出现了第 \(a_i\) 种代号。
剩下的边按照最大权闭合子图的建图方法，非负的连 \(s\)、负的连 \(t\) 即可。