寒冬暖炉
同 CF1110B Tape。
先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。
美术展览
显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。
设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。
因此我们从后往前扫，维护 $sum_i-a_i$ 的最大值即可。
团子制作
注意到仅有 / 形的对角线上会互相影响。因此我们把每条 / 形的对角线拿出来 DP 一次。
设 $dp_{i,0/1/2}$ 表示前 $i$ 个位置，当前位置不放/横放/竖放最多能放多少个。这个很容易转移。
然后答案就是每条对角线上 $dp$ 的最大值的和。
月票购买
先跑若干遍最短路得到 $U$ 到所有点的最短路、$V$ 到所有点的最短路、$S$ 到 $T$ 的最短路 DAG。
显然从 $U$ 到 $V$ 的路径上免费部分是连续的一段，因此我们只需要拓扑排序求出某个点免费某一段后到达 $U/V$ 的最短距离，然后加上 $V/U$ 到它的距离取个 $\min$ 即可。
注意最后的答案要和原图 $U$ 到 $V$ 的最短路取个 $\min$，因为可以不经过免费的部分。
毒蛇越狱
一个做法：枚举 ? 选什么，然后算答案。这样子是 $\mathcal{O}(Q2^{cnt?})$ 的。
另一个做法：考虑没有 1 的话，我们只需要算 ? 的子集和。现在有了 1，我们只需要将其容斥掉即可。这样子是 $\mathcal{O}(Q2^{cnt1})$ 的。
还有一个做法：考虑没有 0 的话，我们只需要算 ? 的超集和。现在有了 0，我们同样只需要将其容斥掉即可。这样子是 $\mathcal{O}(Q2^{cnt0})$ 的。
我们用 FWT 预处理出子集和和超集和，然后哪种字符少就用哪个做法即可。时间复杂度 $\mathcal{O}(L2^L+Q2^{\lfloor\frac{L}{3}\rfloor})$ 。