250204 to 250209

· · 个人记录

Senrenbanka

P11663

考虑 x 经过一段区间 [l,r] 满足条件的充要条件是对于任意 i\in[l,r] 满足 x+\sum_{j=l}^{i-1}b_i \ge a_i。可得 x \ge a_i-\sum_{j=l}^{i-1}b_i。

那么从 1 开始走你就会了。

再考虑从 v\ge 2 开始走，最终要返工 [1,v-1]。计算是差不多的，只是增益值要把 [v,n] 那些加上去。

然后对于每一个 i 两种情况 x 取 max 就可以了。然后所有 i 答案 min 即可。

P11664

考虑固定 l，设 r_l 为最小的 R 使得区间 [l,R] 满足题目条件。

然后可以双指针。

我刚开始做这道题的时候，不会判合法，用了某个比较抽象的东西断言这个加减边维护不了。

由此而出的总结：注意观察维护信息，不能盲目与已知情况断言等同，要观察维护信息的特点，是否有什么性质，更加简单之类的。

满足条件当且只当对于每个点，都有一条被标记的入边。

证明：必要性显然，充分性：考虑往回跳总会跳到 1。

然后你这个会了，然后一个询问就是问移动多少步才能合法。直接做即可。

Sekai

昨天的那道题

难绷，模拟赛竟然出了 JOI Final 的后三题。

【直接做即可】还是太魔怔了点，因为我发现我好像不会直接做。

重新整理一下。

大概就是你会发现那个限制式，按照我们能做的移动可以直接去掉绝对值，然后你给他移项就能发现对可抵达点的 l-r 的限制。

然后你再二分找一下那个所谓的最大的 l 使得其右端点小于询问的右端点，这样子的话你只需要左端点移动到那里就行了。不过这个点会导致右端点移动不符合上述规律，因此我们查找 l-r 限制时只在这个点到询问的 l 这个区间找。直接用 RMQ 找出来就可以了。

模拟赛 T1(???)

模拟赛 T2

模拟赛 T3

CF1878G

杂谈

糖题，太糖了。

卡常卡了我将近一个小时。

关键是，我没有想到 std 复杂度和我的这个做法一样。以为 std 的做法更加高妙。 其实大家写的代码都非常简洁，是我比较糖，写了 5KB。

正文

你会发现那个式子可以分为 “基本贡献” 和 “额外贡献” 两个部分。基本就是指的，无论中间点选什么都会造成的贡献，额外部分的贡献依照中间点决定。

然后自然重点是在计算额外贡献上。位运算相关可以考虑把每一位分开算。考虑对于每一位，能造成额外贡献的点：

这些点要满足左右两侧（指的是路径上的两侧）（可以包括自身）都要出现该位。

那我们可以发现不满足条件的点是从路径两端开始的两段长度，也就是说满足条件的点在路径上形成一个段，一个区间。

那么对于这个段的两个端点，可以使用倍增来找：每个点维护其祖先中第 2^k 个该位为 1 的点。

那么我们就可以大力树剖，对于每一位，把满足条件点的权值加1，最终路径上权值最大的点就是能造成的最大贡献。

时间复杂度是 O(n \log^2 n \log a_i)，过不了。

其实树剖是不必要的，我们可以按照每个点到路径的某一端点的距离把路径拍平成链，直接线段树维护，时空复杂 O(n \log n \log a_i)。会被卡空间。

考虑空间上把 O( \log a_i) 压掉。把询问离线下来，对于每个位，把所有询问跑一遍，这样子倍增数组可以重复使用。每个询问把需要线段树区间加的区间存起来，最后再对每个询问处理即可。空间复杂度 O(n \log n)。

以上只是本题目考察点的 20\%。你需要一定的卡常技巧。这里我通过优化函数调用，尽量复用数据以及从 OI 维基上面复制快读模板可以极限地通过本题。

Evidence of Existence

决策单调性。

决策单调性

定义函数 w(l,r)。

如果对于 a\le b\le c\le d 有 w(a,c)+w(b,d)\le w(a,d)+w(b,c) 则该函数满足四边形不等式，简记为交叉优于包含。

定义决策单调性：转移方程 f_i = \max _{1\le j< i}(f_j+w(j,i)) 如果满足：

那么 f 满足决策单调性。

定理： 如果转移方程 f_i = \max _{1\le j< i}(f_j+w(j,i)) 中 w(j,i) 满足四边形不等式，那么 f 满足决策单调性。

常见解决办法

分治法

适用于一层一层转移的动态规划，其中每层中的 dp 互不影响。

考虑函数 \textrm{solve}(l,r,ql,qr)。它表示，当前正在计算下标在 [l,r] 中的 dp 值，其最优决策点已经限制在了 [ql,qr]。如此我们可以通过直接枚举获得 dp_{mid} 以及其最优决策点 k。那么由于决策单调性，左右两侧的最优决策点就分别被限制在了 [ql,k] 和 [k,qr] 中。直接递归计算即可。这样的复杂度是 O(n \log n) 的。

二分队列法

考虑搞一个队列维护每个决策点对于后面 dp 的哪些位置是最优决策点。队列中存储三元组 (l,r,p) 表示下标为 p 的决策点是后续区间 [l,r] 的最优决策点。

具体策略如下，假设当前点为 i：

整个过程依赖于“决策点单调”。

其实你会发现这个东西和维护单调队列有那么一丝丝微妙地像。。。

P3515 [POI 2011] Lightning Conductor

通过移项可以得出 p \ge -a_i+a_j+\sqrt{|i-j|}。

对于那个绝对值，我们不妨让 j<i，最后再 rev 整个序列重新计算即可达成相同目的。

我们不妨就让这个 p 为 dp_i，这样子你会得到一个根本不是动态规划的东西：

dp_i =\max \{ -a_i+a_j+\sqrt{i-j} \}

你说得对但是虽然它好像不是动态规划，但是如果我们假装它是动态规划，你就会发现它满足决策单调性，也就是选择的那个 j 是单调的。

并且它又和前面的状态无关，直接分治即可。

因为证明比较简单就写一下

设 k<j<x,\sqrt{x-j}+a_j > \sqrt{x-k}+a_k

那么我们要证明：\sqrt{x+1-j}+a_j > \sqrt{x+1-k}+a_k

由于 k<j，也就是 x-k>x-j，并且因为根号函数 x 越大，导就越小，那么这次 x+1 造成的增量自然是 \sqrt{x-j}+a_j 更大，无法逆转局势！

体育馆103102A

不妨把它当做一个线段覆盖问题：你可以覆盖若干线段，但是某个点不能同时两次作为端点。

把原来的序列前缀和，然后从右往左扫。

类似于反悔贪心，和低买高卖几乎一模一样的套路，如果我们将其选中为右端点就丢进去候选，否则拿出堆顶配对利用前缀和算答案，此时相当于添加了区间 (l,r]，如果想要反悔操作也就是重新配对一个更大区间其实可以直接由另一个区间 (x,l] 并上去，所以我们再往堆中加入 sum_i 用以支持反悔即可。

CF833B The Bakery

经典题，设：dp_{i,j} 为直到 i 分了 j 段于是有方程：

dp_{i,j}=\max_{k<i}\{dp_{k,j-1}+w(k+1,i)\}

然后我发现好像其实有一堆方法直接计算啊。

理论：这个 dp 有完全单调性。证明：略

然后你把每个 j 看做一层（更直观一点可以把两个维交换一下）然后每层互相独立直接分治即可。

## LOJ6039 珠宝 /「NAIPC2016」Jewel Thief 背包问题，但是过不了。 那肯定存在可以乱搞的地方，我们发现重量只有 $300$ 种。直接按照重量分类。然后同类价值排排序。 设 $dp_{i,j}$ 为考虑前 $i$ 类，已经用了重量 $j$。可以得出方程： $$ dp_{i,j}=\max\{dp_{i-1,j-k\cdot i}+w_i(k)\} $$ 首先这个 $w_i(k)$ 表示种类 $i$ 拿 $k$ 个，看起来就挺凸的，实际上果然如此。 然后和上一道题非常类似，直接分治即可。 哦对了，实现需要一点点细节。你可以枚举每个模 $i$ 的余数然后对同种余数进行转移： $$ dp_{i,j\cdot i + b}=\max\{dp_{i-1,k\cdot i+b}+w_i(j-k)\} $$ 然后为了直观一点你可以开几个辅助数组存： $$ \begin{aligned} h_c&=dp_{i-1,c\times i+b} \\ g_c&=dp_{i,c\times i+b} \end{aligned} $$ 然后就是比较好看的转移了： $$ g_x = \max_i \{h_i+w(x-i)\} $$ 转移完毕之后再 copy 回去。 你会发现这就是 maxadd 卷积。 总之分治法已经足够解决这个问题了。 时间是 $O(n+c k\log k)$。 ## 吸烟算法 SMAWK 算法。 以下翻译自 CF1423M 的官方题解，加了一点点个人理解。**不保证正确。请尽量自行参阅原文，如本文有误还请指出。** 对于 $1 \le i \le n-1$ 满足 $L(i) \le L(i+1)$ 的矩阵被称为单调矩阵。如果对于它的每个子矩阵都这样，那么它就被称为完全单调矩阵。 考虑 $m\le n$ 的情况。我们可以找到所有偶数行的 $L(i)$。（请注意，根据定义，抽出这些行组成的子矩阵是完全单调的）将其作为一个子问题递归解决。 那么，对于奇数行的答案 $L(i)$，它满足 $L(i-1)\le L(i) \le L(i+1)$，两边都已经被计算过，你直接在这个范围内枚举即可。依此计算完所有的奇数行的答案，只需要枚举 $O(n+m)$ 个。 接下来考虑 $m>n$。我们可以通过一种算法（将其称为 $\textrm{reduce}$ 操作），将没用的列删去，使得最后的列数最多为 $n$。 对于同一行的两个元素 $M(i,j)$ 和 $M(i,k)$（这里设 $j<k$ ），考虑以下两种情况： - $M(i,j)\le M(i,k)$。此时 $M(i,k)$ 还有它上面的 $M(x,k)\textrm{ that }1\le x\le i$ 都不会是所在行 $L(x)$ 的候选项。 - $M(i,j)> M(i,k)$。相似地，此时 $M(i,j)$ 还有它下面的所有元素 $M(x,j)\textrm{ that }i\le x \le n$ 都不会是所在行 $L(x)$ 的候选项。 如果你对结论有疑问，别忘了 $L(i)\le L(i+1)$ 是对于每个子矩阵而言的。 如此就可以将某些列完全消除，进而开一个栈存储数量至多为 $n$ 的有用列。另外的，在栈中存储有用列中有用元素的顶端。 这个过程只会询问 $O(m)$ 次，之后便可使得 $m\le n$。 整个算法流程如下。 - 如果 $m>n$ 则执行上述 $\textrm{reduce}$ 操作。 - 递归查找由所有偶数行组成的子矩阵的所有 $L(i)$。 - 根据这些 $L(i)$ 在 $O(n+m)$ 内直接遍历查询，即可获得所有奇数行的 $L(i)$。 如上算法显然是在 $O(n+m)$ 的时间内完成的，对于询问次数也是如此。 以上算法被称为 SMAWK 算法（读音和 smoke 一样）。 更好的详细解释见 https://jeffe.cs.illinois.edu/teaching/algorithms/notes/D-faster-dynprog.pdf # kiminoEcho 以下字符串纯属随机生成 // 这里本来应该有点什么的来着 ## 闵可夫斯基和 对于两个序列 $f,g$ 的 $(\max,+)$ 卷积，当 $g$ 是凸序列时，可以使用如下计算方法： ### 分治法 对于卷积结果 $h$，在 $g$ 中的决策位置是单调的。采用分治法解决即可。$O(n\log n)

SMAWK

同理可以采用 SMAWK。（其实这玩意常数有点太大了，可能不如分治）O(n)

特别的，如果 f,g 都是凸序列，那么可以使用如下方法：

闵可夫斯基和

对于 f 和 g，我们获得其差分序列 \Delta f 和 \Delta g。特别的， (\Delta f)_0=f_0,(\Delta g)_0=g_0。

引出序列 v，v_0=(\Delta f)_0+(\Delta g)_0，后面的元素为 \Delta f 和 \Delta g 归并排序的结果（不包含各自的第 0 个元素）。

#### Example 这里为了方便，只保留前五项。 $$ \begin{aligned} f&=\langle 1,5,7,8,2\rangle\\ g&=\langle 2,7,9,6,1\rangle\\ \Delta f&=\langle 1,4,2,1,-6\rangle\\ \Delta g&=\langle 2,5,2,-3,-5\rangle\\ v&=\langle 3,5,4,2,2\rangle\\ f*g &=\langle 3,8,12,14,16\rangle\\ \end{aligned} $$ ## [ABC383G] Bar Cover 先将每个 $b$ 作为区间起始能造成的贡献预处理一下，于是我们获得 $n-k+1$ 个数，不妨将其转化为在其中选择但是相邻间隔 $\ge k-1$。那么你很容易写出 dp。 另外这个选择的过程怎么看都是凸的，于是我们发现对于如此的 dp 可以通过 max-add 卷积 $O(n)$ 合并。考虑一下分治。 先改一下状态，设 $dp_{p,l,r}$ 为分治节点 $p$ 上，左边至少预留 $l$ 个位置，右边至少预留 $r$ 的位置的答案序列。 容易写出合并。最终的答案序列就是 $dp_{1,0,0}$。 ## 原神 QOJ9737. Let's Go! New Adventure 列出 dp $dp_i=\max_{j<i}\{dp_j+w(sum_i-sum_j)-c\}

题目都把单调性条件贴你脸上了，所以不难想象这个 dp 是凸的。

然后我们就直接使用所谓的队列优化决策单调性即可。

这里要注意的是，有一些小问题会导致基于整数域下决策出现问题，解决方法是将 w(x) 扩展为实数域上的函数：设 B 为 b 前缀和，i 为最后一个位置满足 B_i\le x，那么本来 w(x)=i，将其根据后面的扩展一下：

w_{\textrm{ext}}=i+\dfrac{x-B_i}{b_{i+1}}

就不会使得决策有问题了，当然你 dp 可别用浮点数哈。这个只是用来维护决策，dp 还是使用正常的代价函数。

Suizhixiaozhen

模拟 T0

给你一个括号串，说一个下标集合是好的当且仅当你任意重排集合内元素后可以使得括号串合法。问好集合个数。

( 使得权值加 1，) 使得权值减一。

设 dp_{i,j,0/1} 为直到第 i 个位，权值为 j，这一位是否在集合内的方案总数。直接转移即可。

赛时脑瘫了没有想出来怎么去重。

模拟 T1

模拟 T2

模拟 T3

ABC281G

考虑因为边权为 1，所以我们可以得知，对于每个 <d_N 的距离至少存在一个点。于是我们对着这个距离分层进行 dp，同层 dp 代表同一距离。那么设 dp_{i,j} 为当前给 i 个点分了层，最后一层有 j 个点的方案数。可得转移方程：

dp_{i,j}=\sum_k dp_{i-j,k}\times \binom{n-(i-j)-1}{j}\times 2^{j\times (j-1)\times\frac{1}{2}}\times (2^k-1)^j

详细解释一下：枚举上一层的点数 k，从 dp_{i-j,k} 转移，系数分别为：

然后直接做即可。

[ABC077D] Small Multiple

Re: 从零开始重新表示每个数

不妨搞一个无限大的图，其中点 i 向 10i 连边权为 0 的边，然后点 i 向 i+1 连边权为 1 的边。（特别的，0 不参与，后面你就知道原因了）

然后这样子，因为每个数都能被如此 *10, +1 操作表出，并且你会发现到那个点的路径就是它的数位和。

那么问题就转化为了到任意一个 k 的倍数的点的最短路。

但显然是做不了的，因此我们把值域压缩到 k 以内，按照模 k 同余重新建图，这样子的话我们只需要知道 1 到 0 点的最短路就行了，复杂度已经足够被接受。

当然你是从 1 开始的，所以最后不要忘记把 1 本身的代价加上去。

Milutin's Plums

解释一下 LG 题解区的做法中 reduce 为什么是正确的：

删右边的显然。删左边的是因为左边的上面早就确定没用了，而现在下面又被确定没用，自然可以删去。

OinochiChoudai

CF1707E

首先显然有一个 nn\log n 的倍增暴力做法。

结论 1：f(l,r)=\cup_{i\in[l,r)}f(i,i+1)。证明：显然。

这个结论非常简单但又非常关键，它使我们猜想出下列结论：

结论 2：f^k(l,r)=\cup_{i\in[l,r)}f^k(i,i+1)。证明：略。

首先区间有交是肯定可以证的，然后我不会了。

于是我们直接维护 rmq 以及倍增维护 f^k(i,i+1)，然后直接做即可。

大厅定理

定理：对于一个二分图左部点数量为 n，右部点数量为 m，n\le m，二分图如果存在一个左部点都能匹配上的匹配，当且仅当对于左部点的任意子集（不妨大小为 k），与该子集点有连边的右部点数量不少于 k。

证明：

必要性显然。

充分性：