寒冬暖炉

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})$ 。

代码

最后修改:2019 年 11 月 01 日 08 : 30 PM