11.24 口胡 + 做题 | yijan's Blog

后面是某 $dp$ 讲义的习题，前面是前两天讲的题。

APIO 2018 New Home 新家

考虑按照年份枚举一下，相当于在 $l_i$ 加入 $i$ ，在 $r_i + 1$ 删除 $i$ 。然后询问就是二分一下答案，考虑 $[a-m,a+m]$ 是否存在所有类型的商店，也就是是否存在某个 $(a+m,\infin)$ 的数的 $pre$ 小于 $a-m$ ，是否存在某个 $(-\infin ,a-m)$ 的数的 $nxt$ 大于 $a+m$ 。

线段树维护，在线段树叶子结点开个 set 即可。复杂度俩 $\log$ 。开始在每个节点都开了 set 三个 $\log$ 就直接 T 没了。

submission

CSacademy Light Count

考虑每 $64$ 个放到一个 ull 里面，这样直接开内存是 $6\text M$ 左右，然后块间用 BIT 维护，这样内存是 $3\text M$ ，因为每个位置只需要一个 int 。时间复杂度可以是 $O(q(64 + \log n))$ 或者通过__builtin_popcount 做到 $O(q\log n)$ 。

submission

读到的一种高维前缀和的优秀理解方式

自己以前写的高维前缀和的理解没有资料上写的对劲。

考虑要求

F(S) = \sum_{s \sube S} f(s)

我们设 $g(s,i)$ 表示与 $s$ 的最长公共前缀长度是 $i$ 的子集 $s$ 的 $f$ 的和。

考虑转移，如果 $s$ 在第 $i$ 位上是 $0$ ，显然我们有

g(s,i) = g(s,i+1)

因为所有 $s$ 的子集在这一位一定都是 $0$ 。

如果 $s$ 在第 $i$ 位上是 $1$ ，那么我们只需要讨论一下子集在这一位上是否为 $1$ ，也就是两个部分的和：

g(s,i) = g(s,i +1) + g(s \setminus \{i\},i + 1)

这两种情况明显不会有交。

首先，我们可以通过倒序枚举一下集合，然后就可以滚动掉一维。

不难发现，做这个东西的时候，枚举位的顺序不重要，因为先处理哪一位其实是一样的。而且由于影响关系一定是这一位有的集合影响这一位没有的集合，所以集合本身的枚举顺序其实也是不重要的。

同理，逆的 $\text{FMT}$ 的这两个顺序也是不重要的，所以变加减号即可。

但是 $\text{Dirichlet}$ 前缀和不太一样，不能任意改变顺序，虽然维度的枚举仍然不重要，但是因为本质上是个每个位置是质因子次数的高位前缀 / 后缀和，而质因子次数的贡献非 $01$ ，所以贡献是需要考虑一个加减的顺序的，所以正逆 $\text{Dirichlet}$ 前缀和的枚举数的顺序需要颠倒。

wqs 二分

以前学的时候学的很水，只是水过了几个模版题，大概再来写一下。

大概的例题就是比如我们要给一个数组分正好 $k$ 段，使得某个函数尽量小。

我们设 $f(x)$ 表示分成恰好 $x$ 段的时候的最优代价。如果我们证明了或者假装它是凸的，同时我们可以方便地计算 $f(x) - px$ 的最大值以及此时的 $x$ 的取值，我们就可以通过二分这里的 $p$ 的方法来确定 $f(k)$ 。具体操作大概是二分一个 $p$ ，看看决策点和 $k$ 的大小关系，再进行二分。

为什么这样是对的？

我们考虑图上这种凸函数，不难发现 $f(x) - px$ 最大的时候其实就是在拿一个 $y=px+b$ 切凸包，不难发现切点关于斜率单调，所以可以二分。

往往斜率都是整数，所以可以直接整数二分。因为很多时候两个凸包上的点的横坐标差都是 $1$ 。

但是有些时候，有可能最优解的位置是平的，比如图中 $EFG$ 三点， $F$ 作为最优点，但是你二分斜率后会求到 $E$ 这个点。这种时候往往有两种处理方法：

最为简单粗暴的：
$f(K) = f(V(p)) + \frac{f(V(p+1)) - f(V(p))}{V(p+1) - V(p)} (K-V(p))$
从来没见到人写过。
好写的做法：
$f(V(p)) - pV(p) = M(p) = f(K) - pK \Rightarrow f(K) = M(p) + pK$
所以可以发现，直接加上 $pK$ 就是对的了。

然后大概还学到了一个时间换空间的方法，写在后面 2-3 了。。

2-1 Cats Line Up

如果考虑从小到大往排列里面插入，大概 $x$ 只能插入到 $x-i,x-j$ 之间，其中 $i,j \le k$ ，不然的话大于 $k$ 的那一边就永远无法满足条件。

于是感觉可以考虑大力维护一下每对 $x-i,x-j$ 是否存在以及每个 $x-i$ 是否在边界，转移看起来是 $O(1)$ 。复杂度大概是 $O(2^6 n)$ 。

2-2 垂阝局设置问题

由于不知道标题读啥，下面就说成是建立灯塔。

这题 $n,k \le 3\times 10^5$ ，找不出什么比较好的优化思路，于是假装考虑答案关于灯塔个数凸，wqs 二分一下给建立灯塔定个权。然后用一个 $dp$ 来算覆盖所有点的最小花费。建立一个灯塔来覆盖一段区间肯定会建立在中位数的位置上最优。这个东西显然具有决策单调性。所以大概可以再套一个决策单调性，复杂度是 $O(n\log^2n)$ 。由于证不来这个是不是凸的而且这个复杂度跑 $3 \times 10^5$ ，感觉有些不稳。

2-3 Criminal

空间限制 1MB

考虑如果不输出路径咋做，我们设 $dp[i][j]$ 当前序列上在 $i$ ，这个信号是 $j$ 城市发出的，然后发现可以滚动一下，空间就被压下去了。但是发现输出路径肯定是做不到的。

然后考虑输出路径，前面的资料给了一种时间换空间的办法。我们考虑对于一个中点 $mid$ 算出最优路径下在 $mid$ 这个信号是在什么城市。这个东西可以从 $L$ 向中点做一次 $dp$ 过去，再从中点向 $R$ 做 $dp$ ，沿途记录的是来自中点的哪个状态。然后递归考虑左右即可。

这样复杂度是 $O(nS\log n)$ 的，但是空间由于滚动数组变成了 $O(n\log n)$ 。

2-4 Machine Works

考虑一个显然的 $dp$ ，设 $dp[i]$ 表示直到 $t_i$ 天的最大收益。然后由于我们肯定会尽量让每天都有机器工作，显然的转移是 $O(n)$ 的：

\begin{aligned} dp[i] &= \max\{dp[j] + (t_i - t_j)g_j - p_i + r_j\}\\ &= \max\{g_j t_i - t_jg_j+dp[j]+r_j\} - p_i \end{aligned}

显然，这就是维护一个直线 $f(x) = g_ix - t_ig_i + dp[i] + r_i$ ，横坐标不单调，不太能单调栈，拿李超树或者 cdq 一下就可以做了。

2-5 Fabricating Sculptures

最后可以看成一个塔的形状，所以考虑一层一层放东西。然后可以设计一个 $O(n^2)$ 状态， $O(n)$ 转移的东西，设 $dp[i][j]$ 表示目前还剩 $i$ 个石头，最下面最多只能放长度为 $j$ 的时候的答案，转移就是枚举最下层放多少个，然后乘一下可以放在多少个位置即可。

可以把问题转化成，需要把 $n$ 分成一些数 $a_i$ ，设 $a_0 = k$ 且 $a_i$ 不能超过 $k$ ，求排序后的 $\prod (a_i-a_{i-1} +1)$ 这个东西。

考虑 $dp$ 式子：

dp[i][j] = \sum_{k\ge j} dp[i+j][k] \times (k-j+1)

感觉处理出 $S[i][t] = \sum_{k \ge t} dp[i][k] \times k$ 和 $s[i][t] = \sum_{k \ge t} dp[i][k]$ 即可。

##2-6 Identificationg of Protein

考虑先把所有数写成 $aP+bQ$ 的形式，然后对应一个点 $(a,b)$ 。

然后考虑把所有 $a + b > \frac n 2$ 的点都转成小于一半的点，设整个序列的和是 $(x,y)$ ，我们可以直接转化成 $(x-a,y-b)$ 这个东西。

然后就成了一个前面讲过的经典的问题，有两个人在网格上走，使得走到的格子尽量多，都走到过不算数。这个可以直接做， $dp[d][i][j]$ 表示两个人分别走了 $d$ 步，某个坐标分别是 $i,j$ 。转移 $O(1)$ ，获得了一个 $O(n^3)$ 的做法。可能 $n$ 为奇数还需要特判一下。

2-7 Escape Through Leaf

做过。大概是斜率优化，然后发现写个李超树合并即可。曾经写的题解

李超树合并的做法就是直接把另一个节点的线段丢到合并到的节点上，然后向下递归即可。

2-8 Gerald and Giant Chess

经典容斥题。容斥成经过了 $k$ 个障碍，要算的就是走到终点乘上容斥系数 $(-1)^k$ ，然后设 $dp[i]$ 为走到第 $i$ 个障碍点的所有方案乘上容斥系数的和。转移就是 $dp[i] = \sum_j -A_{i,j} \times dp[j]$ ，这里的 $A_{i,j}$ 是从 $i$ 走到 $j$ 方案数，不难发现是个组合数。

2-9 Aliens

考虑按照每个 $y = x + b$ 来给格子分类，然后发现每类都一定是最上面的点如果被覆盖，下面的一定可以，我们只保留下来最上面的点。

然后就转化成了一个序列问题，选择一个位置 $a_i$ 会让它左右的 $a_j < a_i - (i-j)$ 的都被覆盖到，同时花费大概是类似 $a_i^2$ 的东西。如果没有至多选 $k$ 个的限制，大概每个位置都会选最靠上的。可以感受一下这个题得 wqs 二分一下，然后转成一个斜率优化的形式。

还没细想，但是感觉大致思路就是这样了。~~毕竟这种段数和长度同级的东西大概也就只能 wqs 二分了吧~~

2-10 Elevator

考虑 $f_i$ 表示前 $i$ 个人都被送好的最小的坠地时间。

f_i = \min_{f_j \le t_i}\{f_j + \max_{j + 1 \le k \le i}\{a_{k}\}\}

不难发现一个位置 $t_i$ 能转移过来的是一段前缀。把能转移到的点放到一个线段树维护这个东西。最大值的维护拿个单调栈，然后问题变成了区间加，求全局最小。单调栈只会 pop $O(n)$ 次。

2-11 Strongly Connected Tournament

不会。

2-12 黑白生成树

经典题。wqs 二分一下黑色边额外的权值。

2-13 Funny Card Game

假装它有决策单调性，于是就可以做了。

尝试去证明了一下，感觉不是很会，至少直接上四边形不等式不太行。

2-14 Span Covering

不会。

2-15 Paint

思考一下发现，最后求出来的红边一定是一个匹配，不然肯定可以通过调整红边更优。比如，一个点同时和两个红边相连，可以把其中某一个红边给变成连向另一个点，更优秀。如果两个都连向度数是 $1$ 的点，直接丢掉一个即可。

直接最大匹配看着就不是最优的。可以考虑 $dp$ 一下，设 $dp[sta]$ 表示 $sta$ 里的点都已经有一个红边相连，每次新加入一个边进去，这个边必须满足两端都没有被覆盖。大概可以再计算下蓝边的贡献，就可以做了。复杂度大概是 $O(m2^n)$ 。

2-16 Ciel and Gondolas

做过。

画下图，可以发现这东西有决策单调性，然后分治一下就做完了。

2-17 New Year and Handle Change

如果 $Lk \ge n$ 那么显然可以覆盖完。

否则，一定会正好整 $k$ 段，并且一定没有交，如果有交可以往右调整一下。

因为 $k,n \le 10^5$ 感觉只能假装是凸的 wqs 二分一下。

转移就是之前一段的前缀 $\min$ ，于是就变成了一个 $O(n)$ 状态 $O(1)$ 转移的 $dp$ ，复杂度 $O(n\log n)$ 。

dp[i] = \min_{j \le i - k}\{ dp[j] + S_{i-k} - S_{j} \} + w

2-18 盩僰麌之心國人皆知

开始以为 $C$ 是块的大小。。然后感觉看着就很决策单调。后来翻了一下原题发现 $C$ 是给定的。

考虑这个 $dp$ 方程，我们先设 $B[i] = A[i]\times i$

然后

dp[i] = \max\{dp[j-1] + \sum_{k \ge j} A[k](C - (k - j+1))\}\\ dp[i] = \max\{dp[j-1] + \sum_{k \ge j} A[k](C + j - 1) - \sum_{k \ge j} B[k]\}\\ dp[i] = \max\{dp[j-1] + \sum_{k \ge j} A[k](C - 1) - \sum_{k \ge j} B[k] + j\sum_{k \ge j} A[k]\}\\ dp[i] = \max\{dp[j-1] + (S'[i] - S'[j-1]) + j(S_a[i] - S_a[j-1]))\}\\

其中 $S'$ 是个常数，然后这个式子看着就可以斜率优化一下。实现细节就不想了。