LWLAymh的备忘录

动态规划的设计

分析状态

Example1

给定一个序列,初始为空,进行多次操作,每次在序列末尾等概率加入一个\([ 1 , m ]\)中的数字,然后进行以下判断:

1. 如果当前序列末尾两个数字相同且小于\(t\),假设都是\(x\),那就将它们都删去,加入一个\(x + 1\).

2. 如果当前序列没有可以删的数字,并且序列长度为\(n\),终止操作.

给定\(n , m , t\),求最终序列的元素和的期望.

\(n , m \leq 10^3 , t \leq 10^9\).

首先\(t \leq 10^9\)显然是没用的,因为它最多也就能这么凑:\(m + n - 2 , m + n - 3 , \cdots , m , m\),合成一个\(m + n - 1\),因此我们令\(t = \min \{ t , m + n - 1 \}\)即可.

然后我们发现一个事实:如果这个序列某一个位置\(i\),有\(a_i < a_{ i + 1 }\),那么无论后面怎么做,这里的\(a_i\)都必不可能被删除.以此,我们不妨设\(f_{ i , j }\)表示序列长度为\(i\),序列开头元素为\(j\)的期望.然后发现中间的枚举巨大麻烦,完全不可以转移.

题解的思维顺序感觉很乱,于是我来马后炮一下重整一下顺序.

首先,我们的限制一共有两种:一个是数的大小不能超过\(t\),另一个是序列的长度不能超过\(n\).我们不妨设\(ans_{ n , t }\)表示在上述两种限制下的答案.接下来我们要做的,无非是开始分析转移\(ans\)需要求出哪些量,这些量又可以如何转移即可.

分析一下\(ans_{ n , t }\),考虑枚举一下开头元素是什么,那么第二个位置就不能是这个元素,然后后面再计算贡献,因此我们自然有\(ans_{ n , t } = \sum_{ x = 1 }^t E ( n 个 位 置 , 第 一 个 位 置 是 x 并 且 没 有 被 删 去 )\).

然后你就会发现这个问题真正难做的地方:我们这么顺着做,每次把第一个元素抠出去,但是这个元素是会影响后面的操作的!举个栗子:

如果插入的数是:\(3 , 3 , 3\),最终的答案应该是\(4 , 3\).

但如果我们一开始把第一个位置扣出去,就变成了\(3 , [ 3 , 3 ]\),最终的答案就变成了\(3 , 4\).也就是说,这里的动态规划问题在转移子问题的时候,需要前面的那个位置作为信息.不妨设\(g_{ i , j }\)表示当前后面还有\(i - 1\)个位置,当前前面已经放好了一个\(j\),这个\(j\)不能被删掉的期望,显然有\(ans_{ n , t } = \sum_{ x }^t g_{ n , x } P ( 最 终 序 列 中 , 这 里 是 k )\),问题只在于如何求\(g\).这个\(g_{ n , k }\)是钦定了这个位置放\(k\)的期望,后面我们需要将它乘上这个位置放\(k\)的概率才能得到真实的答案.这很合理,因为我们通常的一切概率与期望的递推通常都是有一个隐含的条件概率乘法的.

可能第一反应是,这个\(g_{ n , k } = ( k + \sum_{ j \ne k } g_{ n - 1 , j } )\).但是实际上这个是不对的.这里的\(k\)不能删掉不意味着后面的\(j\)不能删掉,事实上后面的\(j\)爱怎么删怎么删,只要不搞出一个\(k\)来就可以.因此我们需要设\(f_{ i , j }\)表示当前后面还有\(i\)个位置,第一个位置不能是\(j\),也不能曾经是\(j\)(因为这里只要是\(j\)都应该与前面合并),剩下的乱选的方案数.这个东西看上去它就不好转移,因为它限制太强了.我们正难则反!设\(f_{ i , j }\)表示后面还有\(i\)个位置,第一个位置现在或曾经是过\(j\)的期望.那么全集是什么呢?全集是\(ans_i\).

还没完啊,我们还需要求一下这里是\(k\)的概率,由于还有一个类似的\(f\),我们还要求一下这里曾经是\(k\)的概率.设前者为\(q_{ i , k }\),后者为\(p_{ i , k }\).我们来强调一下这里设计的原则:这里的\(p\)其实还蛮奇怪的,因为它设计的是:只要我当前在队首拿到了\(k\),我立刻停止后面的操作.这很好理解,因为后面无论怎么玩,这里都曾出现过\(k\)了.但是这个理解方式可以帮助我们写出下面的转移方程.

对于前者,我们发现这里是\(k\)等价于这里是\(k\)并且后面没有出现过\(k\),也就是\(q_{ i , k } = p_{ i , k } ( 1 - p_{ i - 1 , k } \times [ k < t ] )\).这里加一个限制是因为有不能超过\(t\)的限制.

对于后者,这里的\(k\)有很多种可能出现过,一种是直接加入,一种是合并而来,于是\(p_{ i , k } = \frac{ 1 }{ m } [ k \leq m ] + p_{ i , k - 1 } p_{ i - 1 , k - 1 }\).

因此我们几经辗转,终于得到了\(g\)的转移式子:

\[ q_{ i , k } g_{ n , k } = p_{ i , k } ( k + ans_{ i - 1 } - f_{ i - 1 , k } p_{ i - 1 , k } ) \]

就差\(f\)了.\(f\)有两种可能:要么最后仍然是\(k\),要么这个\(k\)已经被杀掉了.于是:

\[ p_{ i , k } f_{ i , k } = q_{ i , k } g_{ i , k } + ( p_{ i , k } - q_{ i , k } ) f_{ i , k + 1 } \]

Example2(CF1007E)

首先我们需要发现一个很强的性质:作用到了第\(i\)个站台就会清空前面所有站台.清空后就和\(a_i\)无关了,而如果还没涉及到一定和\(a_i\)有关,那么涉及到了一半怎么办呢?我们考虑这里涉及到了一半,那么前面一定被清空了,我们根据前面的清空情况现场计算这里的答案.

这启发我们:我们可以对这个做文章,我们设\(f_{ i , j }\)表示只考虑前\(i\)个站台,要撑\(j\)个单位时间需要的最少火车数量.\(g_{ i , j }\)表示只考虑前\(i\)个站台,要撑\(j\)个单位时间,并且\([ 1 , i - 1 ]\)全部清空需要的最少火车数.另外,这两个dp数组都要求不能有火车漏到后面,也就是火车不能坐上后面的人,不然设为\(+ \infty\)表示无法满足(对于全局,我们在\(n + 1\)处放一个\(a = + \infty , b = 0 , c = + \infty\)来保证一定会满载).为什么需要\(g\)作为辅助dp数组呢?我们先对着\(f\)分析.

考虑\(f_{ i , j }\)的转移,根据上面的分析,我们有两种可能:

第一种,前\(j\)轮中根本没接走站台\(i\)的人.此时需要满足\(f_{ i - 1 , j } \ne + \infty \land a_i + j \times b_i \leq c_i\).那么这里怎么更新\(g\)呢?设\(L = sa_{ i - 1 } + sb_{ i - 1 } \times j\),显然\(g_{ i , j } = \lceil \frac{ L }{ K } \rceil\),并且需要保证此时没有用到\(i\)以后的站台,因此需要保证\(\lceil \frac{ L }{ K } \rceil K \leq sa_{ i } + sb_i \times j\).注意到由于这里保证了\(f_{ i - 1 , j }\)是可以取到的,因此我们可以撑到第\(j\)秒,剩下的火车在\(j + \varepsilon\)秒全选.

第二种,前\(j\)轮中有火车接走站台\(i\)的人.设最后一次是在\(r\)时间接走的站台\(i\),那么此时必然清空了\([ 1 , i - 1 ]\),这里用了\(g_{ i , r }\).然后为了防止这里在\([ r + 1 , j ]\)这段时间中爆掉,因此还需要\(w = \lceil \frac{ \max \{ 0 , rem + ( j - r ) b_i - c_i \} }{ K } \rceil\),其中\(rem\)是\(r\)时刻\(i\)剩下的人数.这些火车都要在\(r\)时刻之前解决(因为我们设了最后一次在\(r\)时间接走),不难发现我们其实不在乎前面具体怎么解决的,而只要在\(r\)这里保证没出问题就行.另外还要保证这个过程没有走到后面,也就有\(wK \leq rem\).但是,接下来在\([ r + 1 , j ]\)时刻就只需要对前面做操作,不过和一开始不一样的是,此时被清空了,因此我们设\(f_{ i , j , 0 }\)表示只考虑前\(i\)个站台,要撑\(j\)个单位时间需要的最少火车数量,但是\([ 1 , i ]\)都被清空为\(0\)过.

每一步看上去都很合理,但是如何想到可以这么dp的呢?说到底,dp是解决一个最优子问题的,我们发现我们知道时间,以及前面是否清空,就可以得知目前的状态.另外,由于我们是枚举目前的状态,因此中间的转移过程是易知的.

这个题的启发性大概有以下几点:

1. 设计状态的时候,只考虑记录经过的时间/前面的初始值/目前考虑到第几位,由上面三点可以还原出所有状态.

2. 由于我们确定了当前考虑到了第几位,我们就可以进行递推:原因很简单,只要我们考虑到某一位,就一定会影响前面所有的位置(全部清空以至于到达这里).一开始我犯了一个错是将\(g_{ 1 , t , 0 / 1 }\)全部设为\(0\),因为我觉得无论如何\(0\)位置都是清空的,但实际上这是错误的!因为在\(t\)时刻的\(1\)位置不一定合法.这就是这个设计巧妙的地方:它时刻保证了前\(i\)个的合法性,并且如果我们想要让\(i\)位置合法,一定要求让\([ 1 , i - 1 ]\)合法.

3. 转移的时候,由于钦定了某一时刻是否选,因此我们可以直接算出从\(r \rightarrow t\)这个过程中会积累的量,这些量必然要在\(r\)时刻清理掉.由于钦定导致限制加强,因此这里就容易处理了.

可删除dp

Example1

定义一个有根树为大菊花,当且仅当这棵树的根的度数\(\leq m \land \nexists x \ne root , \deg ( x ) > 2\).对于每一条边,求将这条边连接的两个点合并后,以新点为根的大菊花数量.\(( n \leq 5 \times 10^5 , m \leq 50 )\)

注意到以一个点为根的大菊花数量是一个关于树的大小的背包合并.这样通过前缀后缀做到\(O ( nm^2 )\).

注意到这个背包是可删除的,所以就能做到\(O ( nm )\).

dp分界点

Example1(2022zrtg十连测day7 Permutation)

首先注意到\([ 3 , n ]\)一定会被分成两段递减的序列,分别跟在\(1\)和\(2\)的后面,假设\(1\)在\(2\)前面,这样算出答案后乘以\(n\)即可.

注意到\(i + 1\)一定可以放到\(i\)的前面,设\(f_i\)表示在\(i\)和\(i + 1\)之间有分界点,这两个点后面分界合法的方案数.每次可以枚举下一个合法的分界点,不难发现这个分界点也即\(i\)的倍数\(\pm 1\)之类的,于是可以实现,复杂度\(O ( n \ln n )\).

基于贪心的dp

Example1(CF1666E)

先想一下别的东西怎么求.

如果我们要求最大值最小或者最小值最大怎么办?我们可以二分后贪心,而显然它们的差就是一个答案的下界,问题在于这个下界是否可以取到.

我们冷静一下,发现在可能的方案中,第\(i\)条线段的右端点的位置一定是一段连续的区间.

设\(f_i\)表示第\(i\)个分界点可能的最小值,\(g_i\)表示第\(i\)个分界点可能的最大值.假设我们目前二分的最大值要小于等于\(mx\),最小值要大于等于\(mn\),那么我们有转移:

$$ \[\begin{aligned} f_{ i + 1 } & = \max \{ a_{ i + 1 } , f_i + mn \} \\ g_{ i + 1 } & = \min \{ a_{ i + 2 } , g_i + mx \} \\ \end{aligned}\]

$$

注意到\(f\)与\(g\)的转移是无关的,而显然对于第\(i\)个分界点,它可以取\([ f_i , g_i ]\)中一个数,一定存在一个取法使得答案能取到下界.

为啥呢?只需让\(ans_{ i }\)表示第\(i\)条分界线是啥,那么我们\(ans_i\)是可以取\([ ans_{ i + 1 } - mx , ans_{ i + 1 } - mn ]\)中的任何一个数字的,我们将其和上面求出的\([ f_i , g_i ]\)求一下交集.如果交集为空,说明要么\(ans_{ i + 1 } - mn < f_i , f_{ i + 1 } < ans_{ i + 1 } < f_i + mn\),这是不可能的.另一种情况同理不可能,这就保证了一定可以取到答案.一定能使极差\(\leq mx - mn\).

数位dp

Example1([2022qbxt国庆Day3]string)

首先设\(f_{ i , j }\)表示长度为\(i\)的,以\(S [ n - j + 1 . . . n ]\)为子序列的字符串个数.

考虑按位处理,每次将\(T\)的一个后缀设为极大,然后不断地向前扩展这个后缀的长度,直到所到的位置再改为极大就会超出\(k\).这个时候我们停止更改,并且继续倒着修改,仍然修改每位,直到最后所积累的总数恰好为\(k\).

当然,做的时候一定要时刻铭记后面的部分设为的是极大字符串还是极小字符串,这里设为极大是简单的,因为可以直接继承上一位的枚举.

考虑这个过程,我们每将一个位置的值设为更大,相当于松弛了后面的所有序列,因此也就是一个数位dp.

Example2([CF1194G])

第一反应就是枚举\(x '\)和\(y '\),然后用数位dp枚举\(d\)使得\(x = dx ' , y = dy '\).

但是有一个问题在于如果\(\gcd ( x ' , y ' ) \ne 1\)怎么办,这样有可能会算重.我们发现我们只判断\(\gcd ( x ' , y ' ) = 1\)的情况就行,然后写一个\(2^8\)判断\(x ' , 2 x ' , 3 x ' , 4 x '\)以及对应的\(y '\)出现了没有.复杂度\(( 9^4 \times 2^8 \times \log_{ 10 } n )\),有点难过.

但是我们发现这个\(2^8\)可能大了点,注意到只要出现一个我们就不用再记了,因此唯一需要记的是一对都没出现过的情况,这里只有\(3^4 \times 2\)的状态量,就可以快一点.

树形dp

Example1([JLoi2016]侦察守卫)

首先第一反应是记录子树内到子树根节点的最远的未被覆盖的点和最近的监测站,但是这样是\(O ( nd^2 )\)的复杂度.冷静一下,发现这两个一定只会有一个值有意义,这样就是\(O ( nd )\)的了.

写的时候犯了个很蠢的错:树形dp由于需要合并,所以如果有多步转移,一定要先把所有dp值都会进行的dp转移写成赋值转移,把其它的写成取\(\min\)转移.

轮廓线dp(插头dp)

Example1

现在有一个\([ 1 , n ]\)的排列,现在要从中选出一个集合\(S\),满足\(\forall x \in S , 2 x \notin S , 3 x \notin S\),求方案数.

首先考虑将每个数分解为\(a \times 2^b \times 3^c\)的形式,显然\(a\)不相同的数之间互不干扰.

对于\(a\)相同的一群数,我们考虑将\(( b , c )\)作为它在矩阵上的位置,不难发现上面的要求其实也就是选一个数就不能选它右边的数和下边的数,可以使用轮廓线dp转移.

高斯消元处理后效性

Example1

\(n\)个点的树,一开始位于一号点,每个点有一个颜色(\(0\)或\(1\)),每次随机选择一个点\(v\),从当前所在点移动到\(v\)并将\(v\)的颜色取反(不是将这条路径上的颜色取反),当整棵树颜色相同时停止,求期望移动距离(每条边的长度为\(1\),当然不为\(1\)也能做).

\(n \leq 100000\).

首先我们发现这个树形结构很难搞,怎么办呢?

我会弱化问题!先考虑期望进行多少轮.

不难发现这个问题下,这个树没有任何意义,我们只需要看当前选中的点是\(1\)还是\(0\)就可以.不妨设\(f_{ i }\)表示当前有\(i\)个点是\(1\),最后全\(1\)或者全\(0\)所需要的期望步数,显然\(f_0 = f_n = 0\),\(f_{ i } = \frac{ 1 }{ 2 } ( f_{ i + 1 } + f_{ i - 1 } ) + 1\).欸,这不luoguP7099嘛.看来这个思路很对啊!

但是其实寄了,这个东西怎么想都很难拓展.一开始还想过计算每条边对期望的贡献,但也很难搞.

正确的做法是什么呢?正确的做法是我们统计每个点的贡献!你可能会很好奇这个点能有什么贡献,事实上,假设我们当前在\(u\),只要当前没有结束,我们还要选点\(v\),对答案的期望的贡献就是\(u\)到这棵树上所有点的距离之和除以\(n\),而这是一个定值.也就是说,只要我们统计一下到了每个点\(u\)多少次(要求不是最后一次),我们就可以全部加一加乘一乘得到答案.我们脱离了树的结构!

我们设\(f_{ i , j , 0 / 1 }\)表示当前场面上有\(i\)个\(1\),\(j\)号点这里是\(0\)还是\(1\),它在结束前能被期望选多少次,注意\(f_{ n / 0 , j , 0 / 1 } = 0\).但是这个转移显然有点垃圾,我们再冷静一下:似乎我们不在乎每个点具体编号,只在乎它当前的颜色,于是我们可以设\(f_{ i , 0 / 1 }\)表示当前有\(i\)个\(1\),\(0 / 1\)染色的点在接下来的操作中期望选择多少次.

我们可以写出以下转移:

\[ \begin{aligned} f_{ 0 / n , 0 / 1 } & = 0 \\ f_{ i , 0 } & = \frac{ i }{ n } f_{ i - 1 , 0 } + \frac{ n - i - 1 }{ n } f_{ i + 1 , 0 } + \frac{ 1 }{ n } ( f_{ i + 1 , 1 } + [ i + 1 \ne n ] ) \\ f_{ i , 1 } & = \frac{ i - 1 }{ n } f_{ i - 1 , 1 } + \frac{ n - i }{ n } f_{ i + 1 , 1 } + \frac{ 1 }{ n } ( f_{ i - 1 , 0 } + [ i - 1 \ne 0 ] ) \end{aligned} \]

为啥最后加上了\([ i + 1 \ne n ]\)呢?因为我们统计的是在没结束的情况下的答案.

乍一看这个转移成环并且极其复杂,可能需要高斯消元,但实际上不用,我们冷静观察一下:

我们假设我们已经求出了\(f_{ i , 0 / 1 }\)和\(f_{ i - 1 , 0 / 1 }\),我们发现我们可以用这两个方程求出\(f_{ i + 1 , 0 / 1 }\),然后就比较典了:我们将所有的函数表示成\(af_{ 1 , 0 } + bf_{ 1 , 1 } + c\)的形式(之所以这么表示,是因为我们架设了\(f_{ 1 , 0 / 1 }\)已经求出来了,虽然实际上没求出来),而由于我们有右边界,我们可以用它表示出\(f_{ n , 0 / 1 }\),而\(f_{ n , 0 / 1 }\)我们已知,这样就可以解一个二元一次方程组.

最短路处理后效性

Example1([2022qbxt国庆Day2]operation)

首先注意到,\(a_i = 1\)的时候和\(a_i \ne 1\)的时候其实没有太大区别,我们在操作完后也需要用各种方式抵消影响.我们设\(f_i\)为\(a_i = 1\),而其他\(a\)全都为\(0\)时的答案,不难发现最后的答案也就是\(\sum{ a_i f_i }\).

而上面的转移自然是:\(f_i = \min \{ b_i , w + \sum_{ j = l }^r f_j \}\).

但是,这个转移是有后效性的,不能直接进行dp,不过我们考虑用类似最短路的操作来处理.

换句话说,由于每次\(f_i\)最小的点不可能再被更新到,我们就把它设为已更新的点.当一个区间中的所有点都被标记为已更新后,我们就拿这个区间去更新别的点.

我们把每个线段挂到线段树上的节点,当我们把一个点标记为已更新,也就是检查这个点对应的线段树上叶子节点到根的路径上所有的线段树节点对应的区间是否全更新.均摊下来,一个区间只会被检查\(\log n\)次,这样就做完了.

组合意义

Example1([NOI2009] 管道取珠)

考虑组合意义,\(\sum a_i^2\)的意义也即满足操作序列\(u\)和操作序列\(v\)的最终结果相同的二元组\(( u , v )\)的数量.

不妨设\(dp_{ i , j , k }\)为第一个装置上方已经动了\(i\)个珠子,下放动了\(j\)个珠子,第二个装置上方动了\(k\)个珠子,下方动了\(i + j - k\)个珠子,并且两个装置截至目前的操作序列完全一样的方案数.显然\(dp_{ n , m , n }\)即答案.

Example2

求长度为\(n\)的排列的\(( \sum_{ i = 2 }^{ n - 1 } [ a_i < a_{ i - 1 } \And a_i < a_{ i + 1 } ] )^k\)的期望\(( n \leq 10^9 , k \leq 500 )\).

\(O ( n^2 k^2 )\)是显然的,枚举最小值在哪就行.

注意到我们要求的是\(\sum ans^k\),而加入\(1\)的时候,对于每个长度为\(n - 1\)的排列,有\(( n - 2 - 2 ans )\)个位置加入后会使答案加一,那我们要求的也就是:

\[ \sum ( n - 1 - 2 ans ) ( ans + 1 )^k + \sum ( 2 ans + 2 ) ans^k \]

推一推式子就可以做到\(O ( nk^2 )\),然后上拉格朗日插值就做完了.

等一下,这是noip模拟赛啊,哪来的拉格朗日插值?

注意到我们可以考虑组合意义,\(ans^k\)等价于从所有的地方中可重复地选出\(k\)个位置,如果随便选肯定可以钦定,问题在于可能会选出两个间隔为\(1\)的位置,这就比较麻烦了.所以我们不妨直接把所有被选中的位置求出来,能合并成一段波动序列的合并.这样,我们设\(f_{ i , j }\)表示已经选了\(i\)段波动序列,其中有\(j\)个谷的方案数.最后这些谷每个至少被选中一次,做一个辅助数组维护波动序列的数量即可,复杂度\(O ( k^3 )\).

二项式定理展开

Example1

求\(\sum_{ i = 1 }^n \sum_{ j = 1 }^n ( a_i \oplus a_j )^2\),\(n \leq 10^5\),\(a_i \leq 10^9\).

考虑设\(f_i\)表示只考虑前\(i\)低的位置,高位全部默认为\(0\)的方案数.如果我们设\(cnt_i\)表示\(a\)中第\(i\)位为\(1\)的数个数,那根据\(( a + b )^2 = a^2 + 2 ab + b^2\),我们只需要求出\(g_{ i }\)表示只考虑前\(i\)低的位置,第\(i + 1\)位是\(1\)的数和第\(i + 1\)位是\(0\)的数两两异或之和,显然有\(f_i = f_{ i - 1 } + 2 cnt_i \times 2^i \times g_{ i - 1 } + cnt_i 2^{ i + 1 }\).

\(g\)可以用\(O ( n \log a )\)的复杂度求,这样总复杂度\(O ( n \log^2 a )\).

线头dp

Example1([20zr普及组五连测day1]区间)

令\(dp_{ i , j , k }\)表示目前倒到第\(i\)个水杯,前面还有\(j\)个延续过来的未结束的线头,目前已经选定了\(k\)个人,转移的话需要枚举当前有几个人在此开始以及有多少人在此结束,这样是\(O ( n^5 )\)的复杂度,不太能接受.但不妨考虑先将有几个人在此开始以及前面的继承处理到目前的数组中,然后再选择若干个人结束,这样分开了两个过程,于是实现了\(O ( n^4 )\)的复杂度.

Example2([2022qbxt国庆Day6]rps)

首先三次询问的做法没区别,我们只考虑r的情况.

注意到我们肯定是想拿s去把p杀掉,不然p就会把r杀掉.考虑一个线头dp,设\(dp_{ i , 0 / 1 / 2 }\)表示前\(i\)个数,0:无接头;1:有接头无线头;2:有线头的情况.这样一个线头每延申就会使答案减少,而如果我们把一个?改为s也会使答案减少,大概做一做.

Example3([COCI2020-2021#2] Svjetlo)

首先发现,我们得到的序列不可能首尾相同,不然我们可以同时去掉开头和结尾.

然后发现,如果一棵子树内的点全部被点亮,这棵子树可以直接删去.这一步是必须做的,不然会多一步讨论.

我们设\(dp_{ u , 0 / 1 , 1 / 2 }\)为\(u\)的状态为\(0 / 1\),以\(u\)为根的子树内有\(1 / 2\)个线头的方案数.注意如果子树内有\(0 / 2\)个线头,那么会在\(u\)处存在两个接头;不然则会只存在一个接头.

通过不断将下方的点合并到当前子树的根节点上,我们可以完成整个过程.

注意到两个接头如果在相邻的两个节点就可以自动接起来,因此\(dp_{ u , s , 2 }\)的两个接头实际上一个位于\(u\),另一个位于\(u\)的随便一个儿子.

换句话说,做线头dp的时候一定要注意,线头的相接是自然的过程(即两个线头相邻就会相接)还是需要手动接起来的过程.

Example4(CF626F)

先按照权值排序,一个人可以选择新建一个组,加入一个组,加入一个组并删除这个组

设\(dp_{ i , j , k }\)表示目前走到\(i\),前面分成\(j\)组,总贡献不超过\(k\)的方案数.做的过程中是一个线头dp,每次每组的贡献都要加上当前位置和前面位置的差值.

Example5([XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan(openstrain contest 1489) J]Travel in Sugar Country)

一条线段上有\(n ( \leq 100 )\)个商店,要从中选出\(k ( \leq 10 )\)个不同的商店\(s_1 , s_2 , \cdots , s_k\),使得按顺序遍历这\(k\)个商店的路径长度是\(m ( \leq 30 )\)的倍数,求方案数.

这种来回走的也是一种线头dp的形式.

我们设\(dp_{ i , j , w , l }\)表示目前在判断了\(i\)个商店,选了\(j\)个,并且目前整个图有\(w\)条”路径”(连续走动),走过的路在\(\bmod m\)一意义下为\(l\)的方案数.最后的答案就是\(dp_{ n , k , 1 , 0 }\).

首先,我们对每个点求出\(D ( 1 , x )\),然后\(D ( x , y ) = | D ( 1 , y ) - D ( 1 , x ) |\),不难发现\(x\)越大\(D ( 1 , x )\)越大(不考虑取膜的问题),因此如果我们按照从左到右的顺序逐渐往里加入,那么我们就需要讨论这个新加入的点它的左右点的\(D\)和它的大小关系,也就是它左右点的加入时间,这显然可以使用线头dp实现.

我们先枚举一下起点和终点并将它们扔到图上,这样初始图上有一条路径(\(s_1 \rightarrow s_1\)),接下来,我们每插入一个点\(x\),我们考虑它的贡献:

1. 新建一条路径,此时这个点的左右端点必然都是在他后面加入,它对总长度的贡献是\(- 2 D ( 1 , x )\),对方案数的贡献为\(1\).

2. 插入到原来一条路径的开头/结尾.此时这个点有一个端点是比它早的,有一个会比它晚,对总长度的贡献为\(0\).

3. 作为中心点合并两条路径,此时对总长度的贡献为\(2 D ( 1 , x )\).

这样我们就做到了\(O ( n^4 km )\)的复杂度.如果我们加两维\(0 / 1\)表示目前起点和终点是否加入,就可以把复杂度优化到\(O ( n^2 km )\).

相对顺序不变

如果遇到一些会不断改变当前状态的题目,有时可以考虑改变前后的一些元素的相对顺序是否改变.以及如果有两个物体相遇后交换位置的题目,如果物体本质相同,同样可以考虑直接穿过而不是交换.

Example1([bzoj4621]Tc605)

注意到最终的序列一定是由若干个数字段组成,而数字段的顺序也即原本序列的顺序,于是此题显然.

拆分区间

有的时候,注意到一个区间可以通过某些方式拆分成两个区间(断点可能是需要枚举的,也可能是固定的),从而可以递归处理/区间dp.

Example1([22zr提高组十连测day4]零二)

先考虑数字两两不同的时候怎么做,我们先找到\(A\)中的全局最大值所在位置和\(B\)中的全局最大值所在的位置.由于从堆中取出全局最大值后,堆一定成为了空堆.因此我们注意到此时\(A\)取出的数量和\(B\)的长度一定是相等的.

进一步考虑,这意味着一个全局最大值将把\(B\)序列分成两部分,这两部分将由\(A\)中相等的两部分分别生成.不妨假设这个全局最大值的位置是\(x\),那么对于\([ 1 , x ]\)这一段的\(A\)生成的\(B\)数组,它的最大值一定在末尾位置,而前面任意,显然它的数量等价于直接删掉最大值后的\(A\)能生成的\(B\)的数量.对于\([ 1 , x + 1 ]\)则任意.

那么我们所需要做的就是求出\(A\)的某一段删掉若干次最大值后的序列所能生成的\(B\)的数量.不妨设\(dp_{ l , r , i }\)表示\([ l , r ]\)中所有\(\leq i\)的数字组成的序列所能生成的数量.

如果\([ l , r ]\)这段区间中没有数字\(i\),那显然\(dp_{ l , r , i } = dp_{ l , r , i - 1 }\),不然,我们可以枚举两端分开的位置,那这个位置一定在数字\(i\)的后面.于是可以转移.

至于可能出现相同数字的情况,我们只需要把每个数字的下标作为第二关键字即可,容易发现这样做之后转化为了两两不同的情况.

Example2([SDOI2010]地精部落)

注意到第\(n\)个元素一定是山峰.所以我们考虑用第\(n\)个元素分割整个区间为两部分.

设\(f_n\)为\(n\)个元素且开头为山谷的答案.枚举第\(n\)个元素在位置\(k\)(\(k - 1\)是奇数),则\(f_k f_{ n - 1 - k } \binom{ n - 1 }{ k } \rightarrow f_n\).

Example3

给定数组\(a\),每次可以选择一个数删掉并把两边的数接起来,要求操作过程中不能出现相邻的数相同,求方案数.\(n \leq 500\).

考虑枚举最后选的点,那么这个点左右一定互不相干.我们假设\(f_{ l , r }\)为将\([ l , r ]\)删干净后再去删\(a_{ l - 1 } , a_{ r + 1 }\)的方案数,然后枚举\([ l , r ]\)中最后删哪个点即可做区间dp.

Example4([AGC039E] Pairing Points)

注意到这么一个事实:如果场上已经有了一个叉,那么接下来的边不能再穿过这个叉了.

首先需要破环为链,考虑从\(1\)号点这里断开,枚举\(1\)号点连接哪个点,然后就可以让\(( 2 , 2 n )\)这些点断开了.我们设计\(f_{ i , j , k }\)或\([ i , j ] ( k )\)表示区间\([ i , j ]\)中的\(k\)向外连了一条边.答案是枚举\(1\)号点连了哪个点,也就是\(\sum_{ i = 3 }^{ 2 n - 1 } f_{ 2 , 2 n , i }\).

于是我们现在的问题在于如何求\(f_{ i , j , k }\).由于边要联通,所以与\(k\)相连的这条边必然被\([ i , j ]\)中的某两个点所连接的边穿过.我们考虑枚举最靠外的那条边,假设为\(x \leftrightarrow y\).这样整个区间被分为了两个部分:\([ i , k ] ( x ) , [ k , j ] ( y )\).但是问题并没有得到解决.因为\([ i , x ]\)和\([ y , j ]\)之间的确不可能出现连边了,但\([ x , k ]\)和\([ k , y ]\)之间仍然可能出现连边.但我们发现:在\([ i , k ]\)中一定存在一个分界线,使得分界线两侧是连到不同的两边的.

我们不妨再枚举一下这两个分界线,分别设为\(p , q\).现在整个区间被分为了三个部分:\([ i , p ] ( x ) , [ p , q ] ( k ) , [ q , j ] ( y )\),三个部分之间并没有连边,于是成功将区间拆分.

这个故事告诉我们:拆分区间的很重要的条件是:将一个区间拆分为若干相互无联系的区间,而我们的重点就是找到一种方式使得区间间相互无联系.

Example5([AGC035D] Add and Remove)

首先自然想到区间dp.但是难以处理的是如果一个区间\([ l , r ]\)中间删掉一个点\(p\)之后,\([ l , p - 1 ]\)和\([ p + 1 , r ]\)会拼起来,仍然会相互影响.

换一种方式,我们找到\([ l + 1 , r - 1 ]\)中最后删除的点\(p\),这样区间\([ l , r ]\)的答案就是最终三个数的答案.这么枚举的好处是,我们发现删除\([ l + 1 , p - 1 ]\)的时候,对\(p\)产生的贡献和删除\([ p + 1 , r - 1 ]\)的时候对\(p\)的贡献是完全独立的,他俩可以分开.

再看每个位置的贡献,我们考虑计算出这个位置会对答案贡献多少倍,不妨假设\(a_l\)贡献了\(x\)倍,\(a_r\)贡献了\(y\)倍,那么由于\(a_p\)会两边都贡献到,所以\(a_p\)会对答案贡献\(x + y\)倍.

于是设计一个dp是:\(f_{ l , r , x , y }\)表示删除\([ l + 1 , r - 1 ]\)后,\(xa_l + ya_r\)最小是多少.自然有\(f_{ l , r , x , y } = \min \{ f_{ l , p , x , x + y } + f_{ p , r , x + y , y } + ( x + y ) a_p \}\).

至于复杂度,前两维肯定是\(n^2\)的空间复杂度,而后两维则意味着每次向下会由两个转移而来,最多转移\(n\)层,因此是\(2^n\)的空间,于是时间复杂度不会超过\(O ( n^3 2^n )\),其实经过一些奇怪计算应该是不会超过\(O ( 2^n )\)的.

Example6([CF607B]Zuma)

这个题的关键在于拆分区间,因此一定要判断哪个点是最后删除的.

我们不妨设\(f_{ l , r }\)表示删除\([ l , r ]\)区间的代价.接下来我们无非要枚举\(k\),使得\(k\)是最后删的.但发现这很难处理.

所以我们怎么办呢?我们考虑判断边界是如何删掉的.比如\(l\),它要么是自己被删,要么一定是找到一个和它一样的点,这两个点一起删.我们注意到如果\(a_l = a_k\),那么这等价于\(f_{ l + 1 , k - 1 } + [ l = k - 1 ] + f_{ k + 1 , r }\).因此可以做区间dp了.

Example7(LOJ 3215)

首先考虑一下\(m = 2^k - 1\)的情况,首先我们要判断有几个数最高位是\(1\),然后接下来判断第二位哪些数字是\(1\).

我们发现这类似一个拆分区间的过程,因为当我们决定了最高位之后,最高位是\(1\)的就一定大于最高位是\(0\)的了,这两个区间就没有影响了.因此可以设\(f_{ l , r , k }\)表示\([ l , r ]\)这个区间,前面已经有了\(k\)个\(1\)的最大贡献.

那么对于\(m \ne 2^k - 1\)的情况我们怎么办呢?我们只需要类似数位dp那样在状态里加一个lim防止超过\(m\)就行了.

相互独立

Example1(2019zrtg十连测day1 origami)

看上去很不好做,先考虑宽为\(1\)怎么做.

这个时候放在最下面的显然是一段区间,不难发现有一个暴力做法是,我们枚举这段区间\([ l , r ]\),然后看\([ 1 , l - 1 ]\)和\([ r + 1 , m ]\)能不能折进来.也就是判断以\(r\)和\(r + 1\)为中心的回文串最大长度以及在这个范围内有没有已经折进来的区间.想到这一步,不难发现左右是独立的.

于是我们设\(f_i\)表示能不能折成以\([ 1 , i ]\)为最下层,\(g_i\)表示能不能折成\([ i , n ]\)为最下层,那\([ l , r ]\)能折出来当且仅当\(f_r = g_l = 1\),做个前缀和就可以知道有多少个区间能折出来.

通过上面的启示,我们不难发现横着折和竖着折也是相互独立的,于是分别算出答案后乘起来就好.

Example2(CF1616G Just Add an Edge)

我们来一点一点捋这个题:

首先,任意一条路径一定形如\(1 \rightarrow x \cup y \rightarrow n\),并且\(1 \rightarrow x\)和\(y \rightarrow n\)不交,然后添加边\(x \rightarrow y\).

那么什么时候\(1 \rightarrow x\)和\(y \rightarrow n\)没有交并且他们的并是\([ 1 , n ]\)呢?考虑将\(1 \rightarrow x\)这条路径上的点染色为\(0\),\(y \rightarrow n\)上的点染色为\(1\),由于边只有从前往后的,因此\([ 1 , y - 1 ]\)必然为\(0\),\([ x + 1 , n ]\)必然为\(1\).至于中间部分一定是一段一段地跳跃.

我们用dp做中间的跳跃过程,具体地,假设我们已经确定了\(y\),现在想要找到\(x\),我们现在假设染色的末尾是\(( i , i + 1 )\),也就是\(i\)染色和\(i + 1\)的染色不一样,然后不断向后接上就行.

那么怎么优化这个dp呢?我们找到任意一个\(p\),满足\(p \nrightarrow p + 1\),那么\(p\)和\(p + 1\)永远不可能染同种颜色,我们直接以它为断点,自然发现\(p\)的左右两部分独立.

然后就是这题的细节部分,首先是计数的时候有可能算上了\(p \rightarrow p + 1\)这条边,要特判.另外的问题是会发现首尾的位置很特殊,这里的做法是建立\(0\)和\(n + 1\)两个虚点,向所有点连边.

总之\(O ( nm )\)的dp是自然的,而且会发现这个是一个类似连续性的东西,因此想到了在中间找断点中间合并,进一步发现左右两部分无关.

费用提前/延后计算

有的时候,我们注意到一个费用是很难及时算到dp数组里的,但是这个费用可能可以早在之前题前算上或之后再补上.

Example1([22zr提高组十连测day3]多)

首先考虑已知一个序列,如何快速求它最后有几个位置不是\(0\).考虑从后往前枚举,每次判断当前数是否在以前已经枚举到过,如果枚举过就将其\(- 1\)并重复判断操作,直到为\(0\)或得到一个没有出现过的数.

考虑设计dp状态,判断一个位置是否能是\(0\)相当于判断后面的已知序列的\(mex\),这个要记入状态中,于是考虑设\(dp_{ i , j }\)表示当前到了第\(i\)个位置,后面的数的\(mex - 1\)是\(j\)的方案数.

但是如果直接这么设会发现,当前\(i\)的加入有可能会改变\(mex\)的值,而这个改变是很难处理的,因为如果\(i\)位置选择了\(j + 1\)这个数字,那么\(mex\)要向上伸展到某一个值,而如果不选择\(j + 1\),也有可能选择一个更大的值后不断落到\(j + 1\),这意味着我们转移时需要枚举补上\(j + 1\)这个数字后的\(mex\)并用刷表法转移.

不妨设这个数字是\(k\).如果我们插入一个数字后直接更新当前的答案,可以发现这个\(k\)是没有办法处理的.所以考虑延后计算费用,即当我们插入的数字并没有引起\(mex\)的改变的时候,忽略此时带来的组合数贡献(因为这个数字可以任选,可以理解为将其暂时存下来后来需要它的时候再把它乘入答案);当我们引起改变的时候,我们从之前存下来的那些数字中取出一些补全\([ j + 2 , k ]\)这些数字.

另外,注意到计算组合数的时候每个数字有两个,没有办法判断当前还剩下哪些数字,不妨直接认为两个相等的数字本质不同,算完答案后再整体除以\(2^{ n }\).

Example(2022zrnoip十连测day9-消失(vanish))

\(O ( n^3 )\)的暴力是显然的:设\(f_{ i , j , k }\)表示目前考虑到第\(i\)个位置,前面还有\(j\)个A,已经选了\(k\)个B的方案数,对A也类似做一做,最后枚举中点合并即可.

问题在于如何优化到\(n^2\).

第一反应是删掉一维,但是这三维好像哪一位都不能删:第二维要累积答案,第三维要最后做合并.但是,注意到第二维和第三维可以合并!换句话说,我们做一个费用提前计算,每次加入A的时候,枚举它接下来要杀掉几个B,那我们接下来就额外多需要一些B.于是我们设\(f_{ i , j }\)表示目前考虑到\(i\),还需要\(j\)个B才能凑齐\(c_B\)个B的答案,就可以实现了.

咋说呢,大概是发现答案和后两维有关,而且注意到后两维之和是不大的,于是考虑把它俩合并起来做费用提前计算.

建立双射

Example1([SDOI2010]地精部落)

设\(f_{ i , j }\)表示长度为\(i\),开头为山峰且高度为\(j\)的方案数;\(g_{ i , j }\)表示长度为\(i\),开头为山谷且高度为\(j\)的方案数.注意到这俩显然是一个双射,也就是\(f_{ i , j } = g_{ i , i - j + 1 }\).

首先我们可以插入一个数,假如插入的数是山峰,那原本的所有大于等于\(j\)的数都向上平移一格,于是自然有:\(f_{ i , j } = \sum_{ k = 1 }^{ j - 1 } g_{ i - 1 , k } = \sum_{ k = 1 }^{ j - 1 } f_{ i - 1 , i - k }\).

另外,这个式子可以稍微转化为:\(f_{ i , j } = f_{ i - 1 , i - j + 1 } + f_{ i , j - 1 } = g_{ i - 1 , j - 1 } + f_{ i , j - 1 }\).

上式可以这么理解:我们讨论一下\(j\)和\(j - 1\)是否相邻,如果相邻必然是\(j\)是山峰,\(j - 1\)是山谷,不然则交换它俩后也仍然是合法的序列.

Example2(2019zrtg十连测day1 group)

首先注意到\(2 k \leq n \land nk \leq 10^5\),不难发现\(k \leq 500\).

冷静一下,发现如果我们把所有组长列出来按照经验排序,再把所有组员列出来按照经验排序,然后按照顺序匹对一定是最优的.

再冷静一下,类似卡特兰数,这等价于先把所有人按照经验从小到大排序,然后任意前缀选择的组长数量大于等于组员,枚举这个差量和前面选的组长的总量就可以做到\(O ( nk^2 )\).当然其实只要控制组长的数量大于等于组员的数量即可.

注意经验相同的话要让想当组长的到前面.

另外当时还推了个性质:都可以的人群中一定存在一个分界点\(w\),使得成为组长的经验\(\geq w\),成为组员的经验\(\leq w\),但是没用上这个性质.

Example3(AGC056B)

双序列计数,考虑把\(x\)双射到某个东西上.

考虑最后的图一定是个\(DAG\),但同层之间没有啥限制,我们不妨假设同层的最左侧是最大值,这样就完成了映射.

设\(dp_{ l , r , mx }\)表示只考虑\([ l , r ]\)这一段的线段,然后最大值所在位置需要\(\geq mx\)的答案.转移的话枚举一手最大值扔哪,然后大概能做?

分维处理

简单来说就是如果问题有两维,我们找到简单的那一维处理.

Example1([CF1621G]Weighted Increasing Subsequences)

动态规划的优化

递进转移

瞎起的名,主要用于大量字符串算法.比如SA中的求height.

Example1

有\(m\)种礼物,每种礼物有无数个(有有限个也能做),\(n\)个朋友,第\(i\)个朋友喜欢第\(j\)个礼物的概率是\(p_{ i , j }\),\(\forall i , \sum p_{ i , j } = 1\).

现在你可以选\(n\)件礼物.购买完成后你会按照朋友的编号逐个进行以下操作:如果自己手上的礼物有他喜欢的那一个,就将那个给他.求一种策略,最大化拿到喜爱的礼物的朋友个数的期望值.

\(n \leq 3000 , m \leq 300\).

首先一个显然的想法是:不同礼物对期望的贡献是独立的,也就是和的期望等于期望的和,我们只需要算出每个礼物的贡献即可.进一步地,我们需要求出\(g_{ i , j }\)表示第\(i\)种礼物一共选了\(j\)个,被拿走的期望个数.然后我们只需要对其做背包就可以了.

那么\(g\)怎么求呢?这个是简单的,我们设\(f_{ i , j }\)表示喜欢第\(i\)种礼物的人有\(j\)个的概率,不难发现\(g_{ i , j } = \sum_{ k = 0 }^n \min \{ j , k \} f_{ i , k }\).递推式就有\(g_{ i , j } = g_{ i , j - 1 } + \sum_{ k = j }^n f_{ i , k }\).\(f\)同样是做一个背包.

但是,这两个背包的复杂度都是\(O ( n^2 m )\)的.我们需要对它们进行优化.

先看最后求答案的背包:自然的想法是,不难发现\(g_{ i , j }\)满足四边形不等式,而其转移是经典的\(k\)点最短路,因此可以用决策单调性优化.

但实际上有点多此一举,事实上我们这么考虑:由于\(g_i\)是上凸函数,它的斜率逐渐减少,那么我们就必然是能选小的就选小的.我们可以设计一个贪心来解决这个问题:记录下来当前每种礼物选了几个,设为\(c_i\),每次选当前\(g_{ i , c_i + 1 } - g_{ i , c_i }\)最大的那个即可,这可以用堆实现.为啥这个是对的呢?因为\(c_i\)越大,能有的贡献就越小,不可能出现为了后面的贡献而让前面吃亏的情况,这就可以贪心了.于是第一个背包得到了解决.这里复杂度\(O ( n^2 \log n )\),不太确定有没有\(O ( n^2 )\)的做法.

但是第二个背包,也就是\(f\)怎么求呢?我们发现我们没有必要把\(g\)全都求出来,只需要求目前需要的一部分就可以了,由于\(\sum f = 1\),因此后缀和可以改为前缀和,考虑到每往后推一位是\(O ( n )\)的,但是只会往后推总共\(O ( n )\)位,因此这里复杂度\(O ( n^2 )\).

Example2

给一个字符串,求一个最大长度\(L \leq \frac{ n }{ 2 }\),使得前\(L\)个字符与后\(L\)个字符循环同构.

不难发现循环同构一定长这样:

\[ ABSBA \]

我们枚举\(A\)的长度,然后就只需要求\(B\),设\(f_{ i }\)表示字符串去掉开头和结尾的\(i\)个字符后的border,有\(f_{ i - 1 } \leq f_i + 1\).然后就做完了.

反向操作

其实本质上是因为,DAG把边反向后仍然是一个DAG,这意味着我们大部分dp都可以进行反向操作.

Example1(CF1810G)

其实这题有一个很自然的容斥做法,但我们先略过.

一般而言先考虑对于每个\(k\)暴力做.那怎么维护最大前缀和这个东西呢?如果我们从左往右扫,其实是很难维护的.因为我们无法接受加一维以维护它.更进一步为什么无法维护呢?因为你新加一个元素,它是不会影响前面的前缀和的,只会影响一个.这导致你的取\(\max\)操作很艰难.但如果!我把这个dp反过来,我设\(f_{ i , j }\)表示从后往前dp到\(i\),当前的最大前缀和是\(j\)的概率是多少,这个dp的转移极其简单:

\[ P \times f_{ i , j } \rightarrow f_{ i - 1 , \max \{ 0 , j + a_{ i - 1 } \} } \]

最后在\(f_{ 1 , j }\)处乘上\(h_j\).

但是这样是\(O ( n^3 )\)的,怎么办呢?

考虑把这个dp反过来!我们设\(g_{ i , j }\)表示如果初始只有\(f_{ i , j } = 1\),dp到最后的答案是多少.于是只需要:

$$ \[\begin{aligned} P \times g_{ i - 1 , \max \{ 0 , j + a_{ i - 1 } \} } & \rightarrow g_{ i , j } \\ \end{aligned}\]

$$

我认真考虑过这个\(P\)应该乘在哪边.实际上确实应该在左边.原因比较简单,因为答案是一串乘法,你不能把这些\(P\)变成除法.但还有一个问题是,为什么反向的时候没有把这些反向呢?

原因是这类型dp比较特殊,我们要算的其实是一个类似DAG路径上的信息,因此边权无需改变.

矩阵加速

Example1(luoguP4007小Y和恐怖的奴隶主)

首先考虑直接将随从的状态压起来,拿组合数分析一下会发现状态数大概小于等于\(200\).也就是说转移矩阵大概是\(200 \times 200\)的,设状态数为\(S\).

继续考虑,如果直接做的话复杂度是\(O ( TS^3 \log n )\),过不了.

我们考虑将一个\(n\)在\(w\)进制下分解,然后预处理每一位所对应的矩阵,这样复杂度来到了\(O ( wS^3 \log_w n + TS^2 \log_w n )\),平衡一下复杂度即可,大概取\(w = 4\)会比较优秀.

Example2([NOI Online#3提高组]魔法值)

重新定义矩阵乘法:用\(\oplus\)替换原本的\(+\),然后用邻接矩阵作为转移矩阵.

直接做仍然过不了,不过可以用和上面那个题一样的方法来优化复杂度.

Example3([CF 1474F])

首先需要注意到,LIS的起点和终点一定在这条线的拐角处,也就是山谷和山峰处.

LIS的长度是好求的.问题在于计数上.

首先枚举一下LIS的起点和终点,但是接下来似乎怎么dp都需要和值域有关.而且如果从起点走到终点,判断中间具体的方案数,这个东西似乎也不能快速处理,一条线上的似乎也很难捆绑更新.

我们冷静一下,令\(f_i = \sum_{ j , a_j = a_i - 1 } f_j\),这个东西一条直线上的位置不能捆绑更新的原因在于,随着我们从左往右走,是需要不断更新后面的\(\sum\)的值的,这一点很难处理.每次移动需要加入一条横线上的点对应的\(f\).

再冷静一下,既然从左到右扫不行,我们能不能考虑从下往上扫呢?考虑设\(f_{ i , j }\)表示所有\(a_x = i\)的\(x\)中第\(j\)小的\(x\)的答案,我们仍然可以从下往上扫.

但是,这么扫的复杂度仍然和值域有关.这怎么办呢?这个加入可规律多了,注意到在经过一个山峰或山谷之前,我们需要处理的点的数量和相对顺序都是恒定的,而它们的转移也之和上一次转移(上一条横线)有关,于是可以直接拿矩阵加速这个过程.

Example4([CF 1152F2])

注意到\(m\)和\(k\)很小,这一定是突破口.

又注意到如果\(a_{ i + 1 } > a_i\),那么限制很强,反之很弱.而且又要求没有相同的数字.考虑从小到大加入数字,这样每加入一个数字\(x + 1\),我们考虑它只能插入\([ x + 1 - m , x ]\)后面,我们直接用一个二进制数\(S\)表示\([ x + 1 - m , x ]\)中的数字是否存在,然后就可以在转移上直接调用\(popcount ( S )\).设\(dp_{ i , j , S }\)表示目前考虑完了数字\(i\),插入了\(j\)个数字,存在情况是\(S\).直接对它做矩阵加速就可以做到\(O ( ( 2^m k )^3 \log n )\).

Example5([NOI2020] 美食家)

设\(dp_{ i , j }\)表示第\(i\)天走到城市\(j\)的最大收益,一眼矩阵加速.

但是有两个问题需要解决:

第一个问题是,怎么处理美食节.这个没什么,在两个美食节之间做矩阵加速,在美食节节点上特殊处理一下就行.不过这样复杂度要乘上\(k\).我们可以一开始就预处理出转移矩阵的二的幂次,然后这里就可以加快速度.

第二个问题是,怎么处理边权.一个自然的想法是拆边,但边很多,拆不过来.怎么办呢?我们可以拆点.将一个点拆成若干个点连起来,对于一条边就找到对应的点连过去就行.

分步合并

大概是有的时候如果询问比较多,我们可能需要处理前缀/后缀数组然后拼起来答案.

这个时候我们会发现,如果要拼起来答案就要枚举一个区间,但是实际上可以一步一步来.

Example([2022qbxt国庆Day6]permutation)

首先遇到排列先扔平面直角坐标系上.

考虑合法序列一定长什么样,如果我们把这个序列的若干个下降子段拿一个矩阵括起来,那这些矩阵显然横纵坐标都不能相交.

我们设\(f_{ l , r }\)表示\(a_l\)和\(a_r\)必选的前提下,\([ l , r ]\)这个区间的下降子序列个数.

然后,我们考虑枚举删掉点,对着剩下来的序列做dp.

考虑设\(dp_{ i , j }\)表示前\(i\)个点,最大值为\(j\)的方案数,不难发现最后一个矩阵的最小值一定是\(a_{ i }\).然后\(dp_{ a , b } = \sum_{ i < a , j < b } dp_{ i , j } f_{ i + 1 , a }\).

这个转移是\(n^4\)的,但是这显然是一个前缀和的形式,于是做一下二维前缀和就可以做到\(n^2\),这样我们就得到了一个复杂度\(O ( n^3 )\)的东西.

继续考虑,由于是多个点,我们考虑维护前缀后缀然后在这个点拼起来.注意到,如果我们想求这个点不选的方案数,那还需要枚举它左右两边选的点,很麻烦,所以我们求一下这个点必选的方案数.这样我们每次需要枚举这个点\(i\),它所在矩阵的最左边的点\(k\),最右边的点\(k\),然后此时的答案为\(pre [ j - 1 ] [ a [ k ] - 1 ] \times nxt [ k + 1 ] [ a [ j ] + 1 ] \times f [ j ] [ i ] \times f [ i ] [ k ]\).

冷静一下,这样一步枚举了两边的分界点,所以可能不是很优秀,我们一步一步来.

设\(g_{ i , j }\)为接下来我们要选\([ i , j ]\),\(i\)是矩阵左端点,\(j\)任意且这两个点必在矩阵中,左右两边的方案数.初始条件\(g_{ i , j } = pre [ i - 1 ] [ a [ j ] - 1 ] \times nxt [ j + 1 ] [ a [ i ] + 1 ]\).

然后我们不断转移右端点,将右端点往里缩,这一步可以使用树状数组优化,最后更新答案即可.

很厉害.

合并更新

Example(2022zrtg十连测day7 Zero)

设\(k = \max \{ i , j \}\),首先可以求出\(x , y , z\)分别表示:

1. \(x\):只包含第一行的格子的以\(k\)为右端点的和为\(0\)的最小矩形的左端点\(- 1\).

2. \(y\):只包含第二行的格子的以\(k\)为右端点的和为\(0\)的最小矩形的左端点\(- 1\).

3. \(z\):同时包含两行的格子的以\(k\)为右端点的和为\(0\)的最小矩形的左端点\(- 1\).

那么自然有转移:

\[ \begin{gathered} f ( i , k ) \leftarrow \max \{ f ( i , k - 1 ) , f ( i , y ) + 1 \} \\ f ( k , j ) \leftarrow \max \{ f ( k - 1 , j ) , f ( x , j ) + 1 \} \\ f ( k , k ) \leftarrow \max \{ f ( k , k - 1 ) , f ( k - 1 , k ) , f ( z , z ) + 1 \} \end{gathered} \]

转移正确的原因是两维转移顺序无所谓,所以可以乱转移.

冷静一下这个过程,我们先只考虑第一个转移:注意到\(f ( i , k )\)关于\(i\)不降,于是显然当\(f ( i , y ) \ne f ( i , k - 1 )\)的时候才会由\(f ( i , y ) + 1\)转移过来.我们不妨设\(p_i\)表示最小的位置满足\(f ( i , p_i ) = f ( i , k - 1 )\),那转移也就是\(f ( i , k ) \leftarrow f ( i , k - 1 ) + [ p_i \leq y ]\).并且每进行一次转移,都会满足\(p_i \leq y\)的\(p_i\)设为\(k\).

也就是说我们需要维护:我们令一个点为它对应的\(i\)在当前\(k\)的\(f\)值,将这个点放到\(p_i\)位置上.然后我们每次找到\(y\)并把所有在\(y\)位置前的点都合并到\(k\)这个点上,并打一个加法\(tag\),这显然可以并查集启发式合并.

把前两个转移这么一起做,然后用二分可以得到两个转移分别的\(p_k\).

最后还需要处理一下\(f_{ k , k }\),暴力转移即可.

有一个问题是为啥能想到按照\(\max \{ i , j \}\)为顺序进行转移,这里是由于转移顺序无区别,我们需要规定一个顺序进行转移,于是考虑到找到较长的那一部分进行转移.

交换状态和值

通常是dp值较小而状态较大的情况,而且二者间通常需要满足单调性.

Example1(CF1620F)

首先讨论一下最大值最小值之类的不难发现:这题是二分图的充要条件是\(\nexists 1 \leq i < j < k \leq n\),\(a_i > a_j > a_k\).

然后相当于是整个序列可以拆分成两个上升子序列,一个想法是\(dp_{ i , j }\)表示现在做到\(i\),另一个上升子序列的终点是\(j\),是否合法.然后继续做.但这样复杂度挂掉了.

咋优化咧?注意到dp状态很大而值很小,且显然在\(i\)一定的情况下,\(j\)的值越小越容易满足.所以设\(dp_i\)表示一个上升子序列的终点是\(i\),另一个上升子序列的终点最小是多少,这样就可以做了.

Example2(AGC033D)

首先自然的设计是\(dp_{ l , r , u , d }\),然后优化一下就是\(O ( n^4 )\).然后咋做?

注意到答案不超过\(\log\)级别,所以设\(dp_{ l , r , u , c }\)表示答案为\(c\)的时候,最大的\(d\)是多少.然后就\(O ( n^3 \log n )\).

Example3

给定一个序列,两个人博弈.Alice每次可以使序列最左边的数\(a_i\)减去\([ 1 , a_i ]\)中的一个数字,减成\(0\)就删掉.Bob可以对最右边的数做类似的操作,不能操作者输.问结果.\(( n \leq 2000 )\)

先考虑一个\(O ( n^2 a^2 )\)的dp,比较显然,因为一个人取数显然要么取\(1\)要么全取,又发现不可能两个人一起取一堆(先取的那个人取完就赢了),于是设\(dp_{ l , r , x , y }\)表示目前Alice在取第\(l\)堆,Bob在取第\(r\)堆,第\(l\)堆为\(x\),第\(r\)堆为\(y\)的情况下谁赢.直接转移.

诶,好像优化不动了,无论咋做都要知道当前这堆数字是啥啊,那就一定要把\(a\)存状态里诶.

能不能再更新一下策略,注意到最后Alice如果要全选的话,剩下的是\(1\)还是更大的数好像无所谓.那:如果\(a_1 = x\)的时候,Alice能赢,那\(a_1 = x + 1\)的时候Alice一定能赢.也就是这个东西满足单调性.又冷静一下,如果两个人不断一直持续选\(1\),那最后一定会选到一个人清空堆为止.而且清空堆的那个一定输了.因为如果清空了还赢了,那他一开始就直接清空了.不可能一开始选着选着一个人还没清空堆另一个人就跑了.这个性质启示我们或许后两维可以删掉一维,因为大部分情况下那一维都应该等于\(a_l\)或\(a_r\).

然后咧?另一维怎么去掉呢?

等一下,我们开一个四维的dp存\(0 / 1\)是不是太奢侈了?

所以我们把一个状态改为dp的值,设\(dp_{ l , r }\)表示当前Alice在\(l\),Bob在\(r\),Bob还没动\(a_r\)的前提下,\(a_l\)至少要是多少Alice才能赢,Bob做一个类似的dp.最后只需要比较\(dp_{ 1 , 1 }\)和\(a_1\)的大小就行.

问题来了,这玩意咋转移啊?

首先,如果当前Alice开始选\(l\),Bob开始选\(r\),那Alice的获胜条件显然是\(dp_{ l , r } \leq a_r\)

如果可以全选(也就是Alice开始选\(l + 1\),Bob开始选\(r\)的时候Alice能赢),就直接让\(dp_{ l , r } = 1\).不然,由于清空堆的人要输,所以Alice为了不输,必须要让\(dp_{ l , r - 1 }\)也满足条件,一个自然的想法是\(dp_{ l , r - 1 } + a_r + 1\),但是这个值好像没有必要:因为Bob并不是只有会不断清空\(a_r\)的,如果目前的\([ l + 1 , r ]\)这个状态,Bob的值已经赢不了了,那我Alice就可以直接把左边清空.所以一旦Bob走到了不能稳赢\([ l + 1 , r ]\)的值,Bob就必须全清空,所以如果我们设\(g_{ l , r }\)是Bob的\(dp\)数组,那其实这里应该是\(a_r + 1 + dp_{ l , r - 1 } - g_{ l + 1 , r }\),因为Bob的策略一定是一步一步走到\(g_{ l + 1 , r }\)后清空,这个情况我们已经杀了他了.

Example4(uoj708)

自然的想法是\(dp_{ i , j }\)表示\(i\)子树内划分成\(j\)个连通块是否合法,然后我们发现如果\(j\)满足条件,那么\(j + 2\)一定满足条件(判掉一些边界情况).

斜率优化

一般的斜率优化就略了.

值得一提的是,斜率优化还有一种理解方式是:将前面的点当作直线,后面的当作一条平行于\(y\)轴的直线进行查询.

Example1(Codechef TSUM2)

点分治+斜率优化,注意需要使用第二种理解方式的斜率优化.

不过第一种应该也可以用.

WQS二分

能用WQS二分解决的问题通常形如:需要在\(n\)个物品中选择恰好\(m\)个,使得最后答案最大.并且如果令\(f_i\)表示选了\(i\)个的最大答案,\(f_i\)必须是凸函数且是单调不降的.

遇到这种问题,我们通常二分一个数\(C\),每选择一个物品就减去\(C\)的答案.不难发现这样我们一定能逼近\(f_m\).

四边形不等式

对于定义在\(\mathbb{ Z }\)上的二元函数\(w\),若对定义域上任意\(a , b , c , d ( a \leq b \leq c \leq d )\)都有\(w ( a , c ) + w ( b , d ) \leq w ( a , d ) + w ( b , c )\),也就是交叉小于包含,则称函数\(w\)满足四边形不等式.如果等式成立,那么我们称其满足四边形恒等式.

不难发现这意味着:\(w\)所形成的矩阵中的任意一个子矩阵的差分(左上角+右下角-左下角-右上角)都小于等于\(0\).

如果它还满足\(\forall 1 \leq l ' \leq l \leq r \leq r ' \leq n , w ( l , r ) \leq w ( l ' , r ' )\)，我们称其满足区间包含单调性.

需要声明的一点是:四边形不等式只能处理\(\min\)型dp的问题,对于\(\max\)型dp需要取相反数改成\(\min\).

判定/性质定理

定理1

若二元函数\(w ( x , y )\)满足\(w ( a , b ) + w ( a + 1 , b + 1 ) \leq w ( a , b + 1 ) + w ( a + 1 , b )\).其中\(a < a + 1 \leq b < b + 1\),则\(w\)满足四边形不等式.

证明:

对于\(a + 1 < c\) 有

$$ \[\begin{aligned} w ( a , c ) + w ( a + 1 , c + 1 ) & \leq w ( a , c + 1 ) + w ( a + 1 , c ) \\ w ( a + 1 , c + 1 ) & \leq w ( a , c + 1 ) + w ( a + 1 , c ) - w ( a , c ) \\ \end{aligned}\]

$$

同时有:

$$ \[\begin{aligned} w ( a + 1 , c ) + w ( a + 2 , c + 1 ) & \leq w ( a + 1 , c + 1 ) + w ( a + 2 , c ) \\ w ( a + 1 , c ) + w ( a + 2 , c + 1 ) - w ( a + 2 , c ) & \leq w ( a + 1 , c + 1 ) \\ \end{aligned}\]

$$

联立得到:

\[ \begin{aligned} w ( a + 1 , c ) + w ( a + 2 , c + 1 ) - w ( a + 2 , c ) & \leq w ( a , c + 1 ) + w ( a + 1 , c ) - w ( a , c ) \\ w ( a + 2 , c + 1 ) + w ( a , c ) & \leq w ( a + 1 , c ) + w ( a + 2 , c + 1 ) \end{aligned} \]

同理可推至四边形不等式定义式.

事实上,这意味着一个\(2 \times 2\)的子矩阵的差分满足条件,那么自然满足四边形不等式,无需推导.

定理2

若\(w_1 ( l , r ) , w_2 ( l , r )\)满足四边形不等式(或区间包含单调性),则\(\forall c_1 , c_2 \geq 0\),\(( c_1 w_1 + c_2 w_2 )\)满足四边形不等式(或区间包含单调性).

证明显然.

定理3

若\(\exists f ( x ) , g ( x )\)使得\(w ( l , r ) = f ( r ) - g ( l )\),则\(w\)满足四边形恒等式.当\(f , g\)单调递增时,\(w\)还满足区间包含单调性.

证明显然.

定理4

设\(h\)是一个单调递增的下凸函数(一阶导数单调递增),若\(w ( l , r )\)满足四边形不等式和区间包含单调性,则复合函数\(h ( w ( l , r ) )\)也满足四边形不等式和区间包含单调性.

令\(l_1 \leq l_2 \leq r_1 \leq r_2\),由于\(w\)满足四边形不等式,于是有:

\[ \begin{aligned} w ( l_1 , r_1 ) + w ( l_2 , r_2 ) & \leq w ( l_1 , r_2 ) + w ( l_2 , r_1 ) \\ 0 & \leq w ( l_1 , r_1 ) - w ( l_2 , r_1 ) \leq w ( l_1 , r_2 ) - w ( l_2 , r_2 ) \end{aligned} \]

令\(t = w ( l_1 , r_2 ) - w ( l_2 , r_2 )\),我们有:

\[ \begin{aligned} w ( l_1 , r_1 ) & \leq w ( l_2 , r_1 ) + t \\ w ( l_1 , r_2 ) & = w ( l_2 , r_2 ) + t \\ h ( w ( l_1 , r_1 ) ) - h ( w ( l_2 , r_1 ) ) & \leq h ( w ( l_2 , r_1 ) + t ) - h ( w ( l_2 , r_1 ) ) \\ h ( w ( l_1 , r_2 ) ) - h ( w ( l_2 , r_2 ) ) & = h ( w ( l_2 , r_2 ) + t ) - h ( w ( l_2 , r_2 ) ) \end{aligned} \]

不妨令\(\Delta h ( x ) = h ( x + t ) - h ( x )\),由于\(h\)是下凸函数,所以\(\Delta h\)函数单调递增.

那么也就有:

\[ \begin{aligned} h ( w ( l_1 , r_1 ) ) - h ( w ( l_2 , r_1 ) ) & \leq \Delta h ( w ( l_2 , r_1 ) ) \\ h ( w ( l_1 , r_2 ) ) - h ( w ( l_2 , r_2 ) ) & = \Delta h ( w ( l_2 , r_2 ) ) \end{aligned} \]

由于\(w ( l_2 , r_1 ) \leq w ( l_2 , r_2 )\),所以\(\Delta h ( w ( l_2 , r_1 ) ) \leq \Delta h ( w ( l_2 , r_2 ) )\)于是:

\[ \begin{aligned} h ( w ( l_1 , r_1 ) ) - h ( w ( l_2 , r_1 ) ) & \leq h ( w ( l_1 , r_2 ) ) - h ( w ( l_2 , r_2 ) ) \\ h ( w ( l_1 , r_1 ) ) + h ( w ( l_2 , r_2 ) ) & \leq h ( w ( l_1 , r_2 ) ) + h ( w ( l_2 , r_1 ) ) \end{aligned} \]

证毕.

定理5

设\(h\)是一个下凸函数(一阶导数单调递增),若\(w ( l , r )\)满足四边形恒等式和区间包含单调性,则复合函数\(h ( w ( l , r ) )\)也满足四边形不等式.

证明类似定理4,因为满足四边形恒等式所以不必用到\(h\)单调递增的性质.

决策单调性

对于形如\(f_i = \min_{ 1 \leq j < i } \{ f_j + w ( j , i ) \}\)的状态转移方程,记\(p_i\)为\(f_i\)的最优决策.若\(p\)在\([ 1 , n ]\)上单调不降,则称\(f\)具有决策单调性.

值得一提的是,我们也可以把题目中的\(\min\)改为\(\max\),并且把\(+ w\)改为\(- w\),那么下面的结论同样成立.

最短路型dp

定理：对于形如\(f_i = \min_{ 1 \leq j < i }{ f_j + w ( j , i ) }\)的状态转移方程,若\(w\)满足四边形不等式,则\(f\)有决策单调性.

证明:

\(\forall i \in [ 1 , n ] , \forall j \in [ 0 , p_i - 1 ]\),根据\(p\)的定义,有:

$$ \[\begin{aligned} f_{ p_i } + w ( p_i , i ) & \leq f_j + w ( j , i ) \\ f_{ p_i } - f_j & \leq w ( j , i ) - w ( p_i , i ) \\ \end{aligned}\]

$$

而对于\(k \in [ i + 1 , n ]\),根据\(w\)的四边形不等式,有:

$$ \[\begin{aligned} w ( j , i ) + w ( p_i , k ) & \leq w ( j , k ) + w ( p_i , i ) \\ w ( j , i ) - w ( p_i , i ) & \leq w ( j , k ) - w ( p_i , k ) \\ \end{aligned}\]

$$

联立得到:

$$ \[\begin{aligned} f_{ p_i } - f_j & \leq w ( j , k ) - w ( p_i , k ) \\ f_{ p_i } + w ( p_i , k ) & \leq w ( j , k ) + f_j \\ \end{aligned}\]

$$

即:\(j\)对\(k\)的更新一定不如\(p_i\)对\(k\)的更新更优,因此\(p_k \in [ p_i , n ]\),因此\(f\)有决策单调性.

Example1(LOJ6039[雅礼集训2017Day5]珠宝)

首先发现代价很小但是物品很多,于是想到按照代价分类.然后同种代价要选肯定由价值从小往大选,这一段可以前缀和做.

于是我们设\(f_i\)表示价值为\(i\)的答案,自然有:\(f_i = \max \{ f_{ i - kc } + sum_{ c , k } \}\).

如果我们把\(c\)相同的分层,那这显然是一个最短路型dp,其中\(w ( i , j ) = sum_{ c , \frac{ i - j }{ c } }\).

显然这个转移只会让\(\mod c\)相同的相互转移,于是后面的\(w ( i , j )\)可以理解为一段数字的和,自然满足四边形不等式(\(\max\)也满足,因为交叉等于包含).

k点最短路型dp

对于形如\(f_{ x , j } = \min_{ i = 1 }^{ x - 1 } \{ f_{ i , j - 1 } + w_{ i , x } \}\)的状态转移方程,若\(w\)满足四边形不等式,则\(f\)有决策单调性.证明同上.

值得一提的是,如果形如\(f_x = \min_{ i = 1 }^{ x - 1 }{ w_{ i , x } }\),我们也可以看作\(k\)点最短路型的\(k = 1\)的特例.

Example1 基站选址

令\(f ( i , j )\)为在第\(j\)个位置建造第\(i\)个基站的代价最小值,那么我们有转移:

\[ f ( i , j ) = \min_{ 1 \leq k < j } \{ f ( i - 1 , k ) + \sum_{ l = k + 1 }^{ j - 1 } w_l [ d_l - s_l > d_k ] [ d_l + s_l < d_j ] + c_j \} \]

考虑后面的式子,不难发现满足四边形不等式(可能出现包含的时候中间部分贡献一次答案,交叉的时候中间部分不贡献答案的情况),于是可以使用四边形不等式优化.

考虑使用二分维护决策单调性,那么后面的是一个经典的二维数点.但由于维护决策单调性时\(d_k\)单调递增,更新答案时\(d_j\)单调递增,于是可以直接使用线段树维护,复杂度\(O ( nk \log n )\).当然也可以直接用一个主席树维护.

也可以考虑分治维护,更加好写,复杂度\(O ( nk \log^2 n )\).

另外,我们可以再使用WQS二分处理第一维,复杂度\(O ( n \log k \log n )\).

Example2(CF gym 102984F)

自然的设计是\(f_{ i , j , k }\)表示前\(i\)个,已经打了\(j\)个,末尾有连续\(k\)个的最大价值.但是这个状态都已经超了.

我们可以用一下经典套路,把它转化为\(f_{ i , j }\)表示前\(i\)个,目前打了\(j\)个且第\(i\)个没打中,然后每次枚举一个打中了的区间,这样看上去就有了优化的可能性.而如果我们把它改成\(f_{ i , j }\)表示前\(i\)个,目前有\(j\)个没打中而且第\(i\)个没打中,这就是经典的k点最短路dp.

接下来我们尝试证明决策单调性:\(dp_{ i , j } = \max \{ dp_{ k , j - 1 } + \sum_{ l = k + 1 }^{ i - 1 } C_{ l - k } A_l + P \}\).

令\(w ( l , r ) = \sum_{ k = l + 1 }^{ r - 1 } C_{ k - l } A_k + P\),接下来我们证明:\(w ( l + 1 , r ) + w ( l , r - 1 ) \geq w ( l , r ) + w ( l + 1 , r - 1 )\)即可.讨论一下每个\(A\)面前的系数就能发现这是成立的.

区间型dp

引理:在状态转移方程\(f_{ i , j } = \min_{ i \leq k < j } \{ f_{ i , k } + f_{ k + 1 , j } + w ( i , j ) \}\)中(通常\(f_{ i , i } = w ( i , i ) = 0 , f_{ i , i + 1 } = w_{ i , i + 1 }\)),如果\(w\)满足四边形不等式和区间包含单调性,那么\(f\)也满足四边形不等式.

证明:

只需证明\(f_{ i , j } + f_{ i + 1 , j + 1 } \leq f_{ i , j + 1 } + f_{ i + 1 , j }\)即可,考虑\(j - i = 1\)的时候,显然成立.

使用数学归纳,假设当\(b - a < k\)时,\(f\)满足四边形不等式,考虑\(j - i = k\)的情况:

设\(f_{ i , j + 1 }\)的最优决策为\(x\),\(f_{ i + 1 , j }\)的最优决策为\(y\),则有:

$$ \[\begin{aligned} f_{ i , j + 1 } + f_{ i + 1 , j } & = f_{ i , x } + f_{ x + 1 , j + 1 } + w ( i , j + 1 ) + f_{ i + 1 , y } + f_{ y + 1 , j } + w ( i + 1 , j ) \\ \end{aligned}\]

$$

对于\(f_{ i , j }\)和\(f_{ i + 1 , j + 1 }\)来说,\(x\)和\(y\)不一定最优,所以有:

$$ \[\begin{aligned} f_{ i , j } + f_{ i + 1 , j + 1 } & \leq f_{ i , x } + f_{ x + 1 , j } + w ( i , j ) + f_{ i + 1 , y } + f_{ y + 1 , j + 1 } + w ( i + 1 , j + 1 ) \\ \end{aligned}\]

$$

\(w\)和归纳假设都可以比较两个式子右边的大小,最终得到:

$$ \[\begin{aligned} f_{ i , j } + f_{ i + 1 , j + 1 } & \leq f_{ i , j + 1 } + f_{ i + 1 , j } \\ \end{aligned}\]

$$

定理

记\(p_{ i , j }\)为\(f_{ i , j }\)的最优决策,若\(f\)满足四边形不等式,那么对于\(\forall i < j ， 有 p_{ i , j - 1 } \leq p_{ i , j } \leq p_{ i + 1 , j } \\\).

证明:

记\(p = p_{ i , j }\),\(\forall k , i < k \leq p\),因为\(f\)满足四边形不等式,所以有:

\[ \begin{aligned} f_{ i , k } + f_{ i + 1 , p } & \leq f_{ i , p } + f_{ i + 1 , k } \\ f_{ i + 1 , p } - f_{ i + 1 , j } & \leq f_{ i , p } - f_{ i , k } \end{aligned} \]

根据\(p\)定义,有:

\[ \begin{aligned} f_{ i , p } + f_{ p + 1 , j } & \leq f_{ i , k } + f_{ k + 1 , j } \\ f_{ i , p } - f_{ i , k } & \leq f_{ k + 1 , j } - f_{ p + 1 , j } \end{aligned} \]

由上两式移项联立,得到:

$$ \[\begin{aligned} f_{ i + 1 , p } - f_{ i + 1 , k } & \leq f_{ k + 1 , j } - f_{ p + 1 , j } \\ f_{ i + 1 , p } + f_{ p + 1 , j } & \leq f_{ i + 1 , k } + f_{ k + 1 , j } \\ f_{ i + 1 , p } + f_{ p + 1 , j } + w_{ i + 1 , j } & \leq f_{ i + 1 , k } + f_{ k + 1 , j } + w_{ i + 1 , j } \\ \end{aligned}\]

$$

因此对于\(f_{ i + 1 , j }\),\(p\)比任意的\(k < p\)更优,因此\(p_{ i + 1 , j } \geq p_{ i , j }\),另一方向同理.

四边形不等式判断凸性

判断一个函数的凸性只需判断\(f ( k ) + f ( k + 2 ) \geq 2 f ( k + 1 )\),而这只需证明\(k\)的时候的答案和\(k + 2\)时的答案可以调整出两个\(k + 1\)的答案(不一定是最小答案)并且这两个\(k + 1\)的答案的和小于等于\(k\)时和\(k + 2\)时的答案之和即可.

Example1(CF1661F)

首先考虑四个点\(( a , b , c , d )\),注意到其一定满足四边形不等式,也就是\(w_{ ac } + w_{ bd } \geq w_{ ad } + w_{ bc }\).

我们现在想证明,设\(f_k\)为新增\(k\)个传送机后的减少的答案,我们考虑证明\(f_k + f_{ k + 2 } \geq 2 f_{ k + 1 }\).

我们画出\(f_k\)时选的点和\(f_{ k + 2 }\)时选的点,注意到我们可以用这两次调整出两个\(k + 1\)的答案,并且这两个答案的和小于等于\(f_k + f_{ k + 2 }\),于是证明了最小的\(f_{ k + 1 }\)是更小的.

于是我们可以使用二分,每次二分一个最小增加量\(w\),然后对于每一段二分出在这一段中再增加一个传送机的增加量小于等于\(w\)的最大的传送机数量,然后就可以做了.

常用激活函数

Sigmoid函数

\(f ( x ) = \frac{ 1 }{ 1 + e^{ - x } } : ( - \infty , + \infty ) \to ( 0 , 1 )\).

\(f ' ( x ) = f ( x ) ( 1 - f ( x ) )\).

tanh函数

\(f ( x ) = \frac{ e^x - e^{ - x } }{ e^x + e^{ - x } } : ( - \infty , + \infty ) \to ( - 1 , 1 )\).

\(f ' ( x ) = 1 - f^2 ( x )\).

ReLU函数

\(f ( x ) = \max ( 0 , x ) : ( - \infty , + \infty ) \to ( 0 , + \infty )\).

Leaky ReLU函数

\(f ( x ) = \max ( \alpha x , x ) , 0 < \alpha < 1 : ( - \infty , + \infty ) \to ( - \infty , + \infty )\).

Softmax函数

\(f ( x_i ) = \frac{ e^{ x_i } }{ \sum_j e^{ x_j } }\).

损失函数

Least Square

即\(\arg \min \sum_{ i = 1 }^n ( f ( x_i ) - y_i )^2 = \arg \min ( A \beta - Y \mid A \beta - Y )\).用最小二乘法取\(\hat \beta = ( A^T A )^{ - 1 } A^T Y\).

Cross Entropy

用错误的分布\(q\)来表示真实分布\(p\)的样本,则平均编码长度应该是:

\[ H ( p , q ) = \sum_i p ( i ) \log ( \frac{ 1 }{ q ( i ) } ) = - \sum_i p ( i ) \log{ q ( i ) } \]

此为交叉熵.

特别地,当最终样本只有两个的时候,例如Logistical Regression问题,可以写成:

\[ \begin{aligned} H & = - ( y \log a + ( 1 - y ) \log ( 1 - a ) ) \\ \frac{ \partial H }{ \partial a } & = - ( \frac{ y }{ a } - \frac{ 1 - y }{ 1 - a } ) \end{aligned} \]

那如果有多个呢?考虑直接对归一化条件作偏导,先有:

\[ \begin{aligned} H ( p , q ) & = - \sum_i p_i ( \log{ q_i } - \log ( \sum_j q_j ) ) \\ \frac{ \partial H ( p , q ) }{ \partial q_k } & = - \frac{ p_k }{ q_k } + \frac{ \sum p_k }{ \sum_j q_j } \\ & = - \frac{ p_k }{ q_k } + 1 \end{aligned} \]

再乘以softmax那里的\(q_k\),得到\(- p_k + q_k = - y_k + f ( x_k )\).

神经网络实现

通过若干隐藏层,假设最后的输出层为第\(L\)层,则:

1. 对于第\(l\)层,取\(\vec{ z }_l = ( W_l )^t \vec{ a }_{ l - 1 } + \vec{ b }_l\).这里对\(W_l\)作转置的目的是写代码的时候需要用行向量.

2. 对于第\(l\)层,取\(\vec{ a }_l = f ( \vec{ z }_l )\),这里意味着将每一个分量对\(f\)操作.

3. 对于最终答案,取误差\(\mathcal{ L } = \frac{ 1 }{ m } ( \vec{ y } - \vec{ a }_L \mid \vec{ y } - \vec{ a }_L )\).

梯度下降法

换言之就是让\(w : = w - \alpha \frac{ \partial \mathcal{ L } }{ \partial w }\),其中\(\alpha\)是一个选定的小常数,也可以采用类似模拟退火的方式动态决定.事实上可以把各个位置分开,写作\(w_j : = w_j - \alpha \frac{ \partial \mathcal{ L } }{ \partial w_j }\).

另外,虽然是这么写,应当见到去掉下标\(k\)的记号仍然合理,无非是逐分量做此操作,因此下面如无特殊说明,运算均采用逐分量运算.例如可以定义\(\vec{ a } \circ \vec{ b }\)为两个向量逐分量相乘后得到的新向量,为表区分用\(\times\)表示正常的矩阵乘法.甚至采取\(( \vec{ a } - \vec{ y } )^2\)表示其自点积.坦白而言,笔者对此符号相当无奈,可也想不出什么更好的写法了.但总之这种写法总是强于部分参考资料上所将下标放上面的写作\(a^L\)的做法.笔者所能维持的精神数院人的唯一做法也只能是在下面加上向量符号,藉此泄愤.

顺便一提,应当见到\(\times\)和\(\circ\)这两种运算比较随意,用线性映射来理解,你这个\(W \times\)任意作用在一个向量上就行.

误差反向传播

既然要用梯度下降法,就应该把每一层的偏导都求出来.然而\(\mathcal{ L }\)是最后一层的结果,因此应该用链式法则一路求出前面的偏导.

更具体地,不妨设误差函数选的是\(( \vec{ a } - \vec{ y } )^2\),激活函数选的是cross entropy有:

1. \(\frac{ \partial{ \mathcal{ L } } }{ \partial \vec{ a }_{ L } } = ( \vec{ a }_{ L } - \vec{ y } )\).(如若选择不同的误差函数,这里作适当变化)

2. \(\frac{ \partial \vec{ a }_{ l } }{ \partial \vec{ z }_{ l } } = f ' ( \vec{ z }_{ l } ) = \vec{ a }_{ l } \circ ( 1 - \vec{ a }_{ l } )\).(如若选取不同的激活函数,这里作适当变化)

3. \(\frac{ \partial \vec{ z }_{ l + 1 } }{ \partial \vec{ z }_{ l } } = \frac{ \partial \vec{ z }_{ l + 1 } }{ \partial \vec{ a }_{ l } } \frac{ \partial \vec{ a }_{ l } }{ \partial \vec{ z }_{ l } } = ( W_{ l + 1 } )^t \times ( \vec{ a }_l \circ ( 1 - \vec{ a }_l ) )\).

4. \(\frac{ \partial \vec{ z }_{ l } }{ \partial W_{ l } } = ( \vec{ a }_{ l - 1 } )\).结果理应是一个矩阵,其实就是这个列向量不断复制若干遍,或者写成\(( \vec{ a }_{ l - 1 } )^t M ( 1 )\),其中\(M ( 1 )\)是全\(1\)矩阵.

5. \(\frac{ \partial \vec{ z }_{ l } }{ \partial \vec{ b }_{ l } } = 1\).

我们应当见到:

不妨设\(\delta_l = \frac{ \partial{ \mathcal{ L } } }{ \partial \vec{ z }_l }\).见到:

1. \(\delta_L = \frac{ \partial \mathcal{ L } }{ \partial \vec{ z }_L } = \frac{ \partial \mathcal{ L } }{ \partial \vec{ a }_L } \frac{ \partial \vec{ a }_L }{ \partial \vec{ z }_L } = ( \vec{ a }_{ L } - \vec{ y } ) \circ \vec{ a }_{ L } \circ ( 1 - \vec{ a }_{ L } )\).前者会因为误差函数的选取而改变,后者会因为激活函数的选取而改变.

2. \(\delta_l = \frac{ \partial{ \mathcal{ L } } }{ \partial \vec{ z }_l } = \delta_{ l + 1 } \frac{ \partial \vec{ z }_{ l + 1 } }{ \partial \vec{ z }_l } = \delta_{ l + 1 } \circ ( W_{ l + 1 } )^t \times ( \vec{ a }_{ l } \circ ( 1 - \vec{ a }_{ l } ) )\).

3. \(\frac{ \partial \mathcal{ L } }{ \partial W_{ l } } = \frac{ \partial \mathcal{ L } }{ \partial \vec{ z }_{ l } } \frac{ \partial \vec{ z }_l }{ \partial W_{ l } } = \delta_l \times a_{ l - 1 }^t\).

4. \(\frac{ \partial \mathcal{ L } }{ \partial \vec{ b }_l } = \delta_l\).

如此以上更新即可.

卷积神经网络(CNN)

神经网络受矩阵乘法的限制,导致对于真实的尺寸巨大的图像难以快速识别,因此产生了卷积神经网络的概念,大概有以下特征:

1. 空间上权值共享:不同位置使用同一个卷积核(滤波器)

2. 稀疏链接:每一层只链接前一层的感受野.

3. 等变表示:卷积神经网络有某种平移不变性.

对于2D卷积,其公式如下:

\[ S_{ r , c } = ( X * W )_{ r , c } = \sum_i \sum_j X_{ r + i , c + j } \times w_{ i , j } \]

其中\(W\)是卷积核,\(X\)是输入图像,\(S\)是输出的结果.如果一个图像有多个通道(比如色彩层之类的),每个通道上都需要应用一个卷积核.

下面引入一些名词:

1. input size:输入图像的尺寸.

2. padding:填充的像素数.

3. filter size:卷积核的尺寸.有时也写作两个变量:filter height和filter width.3D卷积还会有一个filter depth的变量.

4. stride:步长.

5. output size:卷积后输出的尺寸.有时也写作feature size.

6. input channels:输入图像的通道数.

7. n filters:卷积核的数量.

8. dilation rate:膨胀率,用于空洞卷积.膨胀率为\(d\)的时候,卷积核中间会插入\(d - 1\)个\(0\)间隔.

感受野计算

先看output size的计算,容易见到,其各个维度方面计算是独立的.只要对于单个维度算出卷积核在上面移动的次数,最后将不同维度相乘即可.

对于单个维度,这个维度的移动次数应该是:

$$ \[\begin{aligned} \text{ output \_ size } & = \lceil \frac{ \text{ input \_ size } + 2 \times \text{ padding } - \text{ filter \_ size } + 1 }{ \text{ stride } } \rceil \\ & = \lfloor \frac{ \text{ input \_ size } + 2 \times \text{ padding } - \text{ filter \_ size } }{ \text{ stride } } \rfloor + 1 \\ \end{aligned}\]

$$

这个公式相当容易理解,原因是\(\text{ stride } = 1\)的时候,上面恰好是移动的次数,而\(\text{ stride }\)变化的时候,当然要拿到一个上取整.

至于所谓的空洞卷积,只需在上面的基础上改\(\text{ filter \_ size }\)就好.

至于乘法操作,每得到一个\(\text{ output }\)当然都会需要\(\text{ filter \_ size }\)次乘法操作.

再看感受野的计算,不妨设\(S_i\)为前\(i\)次卷积的\(\text{ stride }\)的乘积,设\(k_{ i + 1 }\)表示第\(i + 1\)层的\(\text{ kernel \_ size }\),则:

\[ RF_{ i + 1 } = RF_i + ( k_{ i + 1 } - 1 ) \times S_i \]

这个公式的含义大概是每次先看对应了多大的原数据上的范围,再把原本的边界\(RF_i\)给补上.

池化(Pooling)

池化操作它没有一个可学习的参数,只是对输入数据进行固定的操作.简单来说就是降低输入的规模,以实现更好的鲁棒性以及提高效率.

常见的池化操作包括:

1. MaxPooling:取区域内的最大值.

2. MeanPooling:取区域内的平均值.

3. PyramidPooling:多次进行尺度不同的池化.

常见卷积架构

AlexNet

首次引入ReLU激活函数,Dropout 技术,以及数据增强,提高了模型的训练效率和泛化能力.

采用了\(8\)层深的网络结构,证明了深度网络的潜力.

VGG

开始堆叠小尺寸的卷积核,获得与大卷积核相似的感受野的同时可以增加网络深度.

ResNet

引入残差的概念,直接将输入数据累加(跳跃连接)到最后的输出中,这样网络学习的实际上是输入和输出之间的残差,从而提高了网络学习能力.

SqueezeNet

SqueezeNet的基本构建单元是Fire模块.Fire模块由一个squeeze层和一个expand层组成.squeeze层使用\(1 \times 1\)卷积核减少通道数,而expand层则使用\(1 \times 1\)和\(3 \times 3\)卷积核增加通道数.这种设计有效地减少了参数数量和计算量.

MobileNet

1. 深度卷积:在这个操作中,每个输入通道独立地进行卷积,这意味着在进行卷积时,不同通道之间没有交互.这样可以减少计算量和参数数量.

2. 逐点卷积:逐点卷积使用\(1 \times 1\)的卷积核,它作用在深度卷积的输出上,将不同通道的信息整合在一起.逐点卷积可以减少参数数量,同时保持较高的性能.

ShuffleNet

1. 组卷积(Group Convolution):将通道分成几个组,并使用不同的卷积神经网络层执行标准卷积.

2. 打乱层(Shuffle layer):通过对通道进行洗牌,将不同组的信息合并.

反卷积

也就是将较小的数据特征图扩大到较大的尺寸.有的时候也把这个操作说成上采样.

1. 插值步骤(Interpolation Step):首先,在输入特征图的元素之间插入零,增加特征图的尺寸.

2. 卷积步骤(Convolution Step):接下来,对扩大后的特征图应用一个标准的卷积操作.此步骤相当于在扩大的特征图上滑动卷积核,计算卷积输出.

• OI中的线性代数
  • 线性基
    • Example1
    • Example2([CF1100F]Ivan and Burgers)
    • Example3(luoguP8337 [Ynoi2004] rsxc)
    • Example4([uoj703]赵云八卦阵)
  • 杂题
    • Example1([CF1270I]Xor on Figures)
    • Example2([Petrozavodsk Winter-2014. Moscow SU Tapir Contest(openstrain contest 1435) F]Passing Finals)
  • 逆矩阵求解线性方程组
    • Example1(codeforces CF1266H Red-Blue Graph)

本质相同

Example1

对于所有满足以下条件的长度为\(n\)的序列\(\{ a \}\),我们称它是好的:

\[ \begin{aligned} a_1 & = 1 \\ \forall 2 & \leq i \leq n , a_i \leq \max \{ a_1 , \cdots , a_{ i - 1 } \} + 1 \end{aligned} \]

对于每一个数\(1 \leq x \leq n\),求它在每个好的序列中出现的次数的平方和.其中\(1 \leq n \leq 3000\),任意模数.

首先注意到可以枚举每个数\(x\)出现的次数,这样就转化为对满足某些位置是\(x\)的好的序列计数.

对于一个没有限制的好的序列,设\(f_{ i , j }\)表示\([ 1 , i ]\)中填了\([ 1 , j ]\)(其中\(j\)必填)的方案数,不难发现这就是第二类斯特林数.

这样,对于一个\(x\),我们可以枚举它第一次出现的位置以及出现的次数,以及它第一次出现的位置后面的大于等于它的数的数量,合并即可.复杂度\(O ( n^4 )\).

再思考一下,似乎我们不用枚举它出现的次数,而是可以直接用\(g_{ i , j , 0 / 1 / 2 }\)表示在\([ 1 , i ]\)中填\([ 1 , j ]\),\(1\)出现次数的平方和.同样枚举后面有多少大于等于它的位置,然后就可以把这些位置抽出来作为一个子序列,这个子序列就可以认为\(x\)就是\(1\).复杂度\(O ( n^3 )\).

如果写出上面的式子的话,会发现最难处理的是一个形如\(x^k\)的项,表示\(x\)第一次出现的位置后面仍然选比它小的数字的位置的方案数.这个怎么办呢?自然的想法是想在dp中顺便把它算了.

再进一步想,我们之所以合并麻烦,是因为取了两段上升区间.如果我们能求出一个上升区间和一个下降区间,在交点处合并呢?

但是这样怎么统计平方和呢?我们发现如果在\([ 1 , k ]\)中选了\([ 1 , i ]\),那么\([ 1 , i ]\)在\([ k + 1 , n ]\)中是本质完全相同的,因此还是可以用上面的dp求.

排列转环

Example1(P8416)

这题牛逼.

首先考虑一维的情况,一维情况下最劣应该是\(2 , 3 , . . . , n , 1\)这样的.

为啥捏?因为注意到操作数\(= n -\)排列环数,这样的排列环数为\(1\),显然是最小的.加上列也差不多,所以\(k_0 = 2 n ( n - 1 ) = 2 n^2 - 2 n\).

而我们显然可以通过两次操作把一个位置归位,最后剩一行再随便做做,这样的答案就是\(2 n^2 - n + 1\),如果我们想赢,那就需要在上面的\(n - 1\)行每行省出一步操作.

这咋做呢?类似上面的做法,也考虑找环然后省一步,对于一行,我们找到所有应该放在这里的值以及它们所在的列,把它们应该在的列和实际在的列连边,一定能找到至少一个环(自环也算),删环就可以省一步操作.

Example2

给序列\(a\)和排列\(b\),有若干次操作:

1. 修改操作:给定\(x , y\),将\(a_x\)改为\(y\).

2. 查询操作:给定\(l , r , x\),查区间\([ l , r ]\)内最长的子区间\([ l ' , r ' ]\),使得对\(\forall l ' \leq i < r '\),有\(a_{ i + 1 } = b_{ a_i }\),且存在\(l ' \leq i \leq r '\)使得\(a_i = x\).需要输出满足条件的子区间的长度最大值.

一步一步来,首先处理出所有的极长的满足条件的段,不难发现修改一个点只会断掉一个段或者连接两个段,影响是\(O ( 1 )\)的.

难点在于,我们如何处理要求其中存在一个\(x\)这种东西.

注意到\(b\)是排列,上置换,不难发现\(b\)其实就是一个置换,也就是说每一个极长的段一定是一个置换环内部的元素,我们可以快速定位到\(x\)所在的置换环.但这样还是不能做.

考虑由于是单点查询\(x\),我们可以直接将数组也做置换,这样一个置换环就在一个区间内部,意味着一个极长的段一定是一个区间或者两个区间(原区间的一段前缀和一段后缀).

现在对于区间查询,我们考虑特殊处理和端点相交的段,这个是平凡的.这样我们只需要处理出完全被区间包含的那些段该怎么做.把右端点缩一缩,就等价于左端点完全被区间包含的那些点.也就是以\(a\)为横坐标,\(l\)为纵坐标,这样这些就相当于对一条横线取\(\max\),然后查询一段竖着的线段的最大值.注意到一行不可能有两个横线,因此可以线段树分治+线段树维护,复杂度\(O ( n \log^2 n )\).

规定转移顺序

Example1

给定一张\(n\)个点的图,每个点有一个\([ 1 , k ]\)的颜色,求这张图有多少个子图是一棵树并且在这棵树中每种颜色恰好出现了一次.

首先无根树转有根树计数,设\(dp_{ i , S }\)表示以\(i\)为根,已经选了\(S\)集合中的颜色的方案数.转移的时候枚举出边(注意可能会算重,只要是会算重的都考虑钦定某种颜色在其中一个块里),复杂度\(O ( m 3^k )\).

冷静一下,想到斯坦纳树,于是再设一个\(g_{ x , S }\)表示以\(x\)为根且\(x\)只有一个儿子,\(S\)的定义类似的方案数.这样我们就可以用斯坦纳树的换根技巧计数.很厉害.

这个故事告诉我们:对于图论计数问题(尤其是和树有关),\(m\)大概率可以转化为\(n\),但是需要一些小技巧(例如斯坦纳树)

Example2(P7142)

类似宝藏那个题,我们考虑设\(f_{ d , S_1 , S_2 }\)表示\(S_1\)中的点到\(1\)的距离\(< d\),\(S_2\)中的点到\(1\)的距离\(= d\).然后枚举到\(1\)的距离\(= d + 1\)的点集,这一部分复杂度是\(O ( n 3^n )\),预处理一下不同情况的答案即可.

复杂度均摊

大概是如果多组询问那复杂度是错误的,但是如果我全局求,那我\(\sum\)起来的总复杂度大概是对的.经典问题是树上背包.

Example1

给定一颗二叉树,求对于每一个\(x\),满足\(x , y , z\)互不相同的三元组\(( x , y , z )\)的价值(定义为两两距离之和对\(L\)取膜)的最大值是多少.\(n \leq 3000\).

乍一看,二叉树,想到换根后做dsu on tree+set.但是\(O ( n^2 \log^2 n )\)实在是跑不过去.冷静一下,除去三点共线的情况,考虑三个点在二叉树上的两两LCA一定只有两个点,枚举其中深度较浅的那个点并枚举其子树中的两个点和子树外的一个点.假设其子树内有\(x\)个点对,子树外有\(y\)个点,注意到\(\sum x = n^2 \land \sum y \leq n^2\),于是总复杂度\(O ( n^2 \log n )\).

字典序相关

题目中询问满足条件的字典序第\(k\)小之类的问题,通常采用转化为计数问题.

Example1([2022noip十连测day8]8ady)

首先,我们肯定想如果知道\(a\),我们怎么求出\(b\).

首先不难发现,我们可以这么还原:先开一个堆,然后先将前\(m - 1\)个位置扔进堆里,从第\(m\)个位置开始,假设现在到了第\(i\)个位置\(( m \leq i \leq n )\),每次将\(a_i\)扔进堆里,并从堆中取最小元素扔到\(i - m + 1\)位置,最后把堆清空到剩下的位置即可.

大量实验证明:这种反向构造思路,你用个堆通常是做不动的.

我们考虑有没有别的做法.

一个一个数地考虑,\(b_1\)在\(a\)中的位置应该在哪?显然是应该在\([ 1 , m ]\)中,而且根据上面的堆的做法,显然它应该是\([ 1 , m ]\)中最小的数字,换句话说,我们需要满足:\([ 1 , m ]\)中除它以外的数字都比它大.

我们继续考虑\(b_2\),显然它在\(a\)中应该在\([ 1 , m + 1 ]\)中,并且需要满足\([ 1 , m + 1 ]\)中的所有数字除了\(b_1\),都比它大.

以此类推.不难注意到对于一个数\(b_i\),其中\(1 \leq i \leq n - m + 1\),它能填回的原序列的位置一定最大最大是\([ 1 , m + i - 1 ]\),并且如果它能填到区间\([ l , r ]\)中,这个区间中除去在它之前填进来的数字以外,均比它大.

但是,这显然是个上界.这个区间能不能缩小一下呢?

对于一个\(i\),我们找到最大的\(j\)满足\(1 \leq j < i\)并且\(b_j > b_i\)(有可能找不到).

冷静一下,显然,\(b_i\)不能填到\([ 1 , j + m - 1 ]\).(因为如果它扔在这里,那它就:在\(j\)出堆前入堆,在\(j\)出堆后出堆,显然不合法)

也就是说,我们将每个数能填的区间缩小为了\([ j + m , i + m - 1 ]\).

那是不是说每个数只要填在这个区间中,就一定合法呢?

我们考虑一个数\(i\)以及所有比它小且在它后面的数字\(j\),当\(j = i + 1\)时,显然\(j\)只有一种选择,直接填上;当\(j = i + 2\)时,若\(i + 1\)已经选择好了,那\(j\)显然也只有一种选择,填上.这样,对于所有\(i\),如果它前面有一个大于它的数字,那它一定只有一个位置可以填.

这样我们就可以简化为:给定\(b\)数组单调递增的问题.不难发现该条件下\(i\)可以选择的区间是\([ 1 , i + m - 1 ]\),且满足条件一定有解.

冷静一下,这个时候假设新序列长度为\(len\),那显然一共有\(m^{ len }\)个满足条件的\(a\)序列.注意到这个级别是指数级别.

所以前面一定是按顺序填,直到后面才会打乱顺序.而后面的长度大概也就是个\(\log_m k\),枚举枚举就行.

前缀和与差分

Example1(loj3266)

把点都扔到坐标系上,显然到一个点曼哈顿距离相等的数一定在一个正方形(对角线平行于坐标轴)上.

我们考虑如果已知两个点,怎么找第三个点的坐标,显然是两个正方形的边界的交点,那也就是说,曼哈顿距离下,一个等边三角形必定有两个点所在直线与坐标轴成\(45 \degree\)角,那这两个点必然和另一个点组成了一个等腰直角三角形(欧几里得意义下),我们枚举等腰直角三角形的直角顶点和直角边长就可以确认这两个点的坐标,而另一个点一定在一条与坐标轴成\(45 \degree\)的斜线上,可以使用前缀和做.

注意到有的点对可能会被算两遍,要特判.

Example2

小孔在玩卡牌游戏.众所周知,在卡牌游戏里,过牌是很关键的,所以目前小孔的牌库中,只可能有数字牌\(0 , 1 , 2 , 3 , 4\).

数字牌\(x\)的含义是当你打出它的时候,会从牌库的顶端抽\(x\)张牌到自己手里,若牌库中不足\(x\)张牌,则将牌库抽空为止.打出的数字牌\(x\)会放入弃牌堆中.在题目中你可以认为这张牌不会再被用到了.

目前,牌库里有\(n\)张牌,从牌堆顶到牌堆底数第\(i\)张牌为数字牌\(a_i\).在开始回合时,发牌员会进行一次切牌,切牌的结果是从牌堆顶到牌堆底的牌的顺序变为了\(a_s , a_{ s + 1 } , . . . , a_n , a_1 , . . . , a_{ s − 1 }\).

接着,小孔会抽\(k\)张牌堆顶的牌到自己手上.每次小孔可以打出一张牌,但这一回合中小孔至多打出\(p\)张牌.小孔可以在任意时刻结束回合.

请问,这一回合中若小孔使用最优策略,那么牌库里最少还剩多少牌.进一步地,有\(q\)次这样的询问,每次询问给定三个整数\(s , k , p\),你需要输出牌库里最少还剩多少牌.\(( n , q \leq 3 \times 10^5 )\).

每次询问是独立的,也就是说每次询问并不会以任何方式影响到之后的询问.

首先我们想一下我们需要知道什么:我们需要知道其在这一回合中打出的各种牌的数量是多少.而只要知道这一点,我们自然得到了答案是多少.注意到每次一定优先打出手头上最大的牌.

我们设\(sum_{ t , i }\)表示从开始到抽完第\(i\)张牌之前,在只用大于\(t\)的牌的前提下,还能往下抽多少张牌.显然\(sum_{ t , 0 } = 0\)并且\(sum_{ t , i } = sum_{ t , i - 1 } + a_{ i - 1 } [ a_{ i - 1 } > t ] - 1\).注意到\(sum_{ t , i } = 0\)就抽不了第\(i\)张牌了.不考虑还能抽负数张牌的情况,注意到\(sum\)数组具有可差分性!

那我们一开始抽了\(k\)张牌,也就是令\(sum_{ s + 1 } \leftarrow sum_{ s + 1 } + k\),那第一个不能继续抽牌的地方显然也就是第一个满足\(sum_{ i } - sum_{ s } \leq 0\)的地方,用原本的\(sum\)数组表示也就是\(sum_{ i } + k \leq sum_{ s }\).那第二个地方呢?由于后面的\(sum\)都加上\(k\)了,第二个地方也就是满足\(sum_j \leq sum_{ i } - t\)的地方(不过注意到后面要倍增,所以直接写\(sum_j < sum_i\)也可以,这样方便用单调栈维护这个东西).以此类推,注意到这个东西和询问无关,可以使用倍增预处理,处理的过程中判断一下还有没有大小为\(t\)的牌以及用牌总数是否小于等于\(p\)即可.都是可以用前缀和之类的东西预处理的.最后从小的牌开始选,选完之后的牌就可以当成\(0\)牌了.另外要注意:我们要保证目前一定有大小为\(t\)的牌选,所以需要在做之前判断一下最后一次选择大小为\(t\)的牌的位置是在哪里.

等一下,注意到我们好像没啥办法判断还有没有大小为\(t\)的牌.有一个方法是:我们直接令所有\(\leq t - 1\)的牌变成\(t\),并处理出不用\(\leq t - 1\)的牌能跑到的最右点,然后取个\(\min\).

想出\(sum\)数组并发现可差分性后,这个题突然就变可做了.问题来了:咋想到的\(sum\)数组,又是怎么发现的可差分性?

首先,由于切牌这个环节会变化起点.所以有两种可能:要么是像倍增那样起点不定,要么是像差分一样其它起点的答案可以由原本的起点答案得到.那想到差分后呢?又注意到一定会先选较大的牌,所以大概率可以分层考虑:这样就先把问题转化为只有\(0 / 1\)或者是只有\(0 / 1 / 2\)的情况再继续考虑.由于要多组询问,所以答案一定是可以通过某种方式迅速算出来的,考虑到只要得到每种牌选的次数就可以快速算答案.又有一定是比它大的牌都选完了才选它,于是考虑第一次选不了其它牌只能选它的地方.注意到这个地方可以使用前缀和在变换起点的情况下求.于是由前缀和判断差分性质.

二分答案

Example1([2022qbxt国庆Day6]kth)

考虑\(f\)的取值不会很多,我们可以枚举\(f\)的取值,并把相同取值的归类.也就是,对于\(f = i\)的类别里也就是后\(i\)位为\(0\),第\(i\)位为\(1\)的那些数.

注意到每个类别内部是很有序的,也就是说我们可以采取类似初赛归并排序的方法二分,找到前\(k\)大的和.

调了一年,这个故事告诉我们,如果一个东西暴力调整能过/复杂度均摊,就不要写一些很丑的很难写的即使更快的东西去做.

Example2

给你一棵\(n\)个点的树,每条边是一个字符(字符集是小写字母),一个点的所有相邻边边权不同.

有\(m\)次操作:每次询问给出点\(x\)和字符串\(S\),\(S\)中不包含相同字符,\(| S | = 26\),每次修改会修改一条边边权.

从\(x\)点开始,每次对与\(x\)点相邻的边,对这些边找出其边权在\(S\)中出现的位置,找出边权出现位置最靠前的边,然后走过去.

每次询问走过的边直接从树上删除,一条边正反方向算同一条边,也就是说没法\(x \rightarrow y \rightarrow x\).

这个过程会停机,你需要输出在哪个点停下来,询问之间独立.

这题最重要的思想在于:我们首先需要将这个问题改成一个判定性问题:判定性问题显然弱于找到答案.

怎么判定呢?对于一条路径,如果我们要沿着它走,那么我们就可以确定每个点的最小边(或者次小边),这等价于给出若干个边之间的大小关系,可以使用bitset维护一下,最后判定即可.我们发现判定数组是可以合并的,于是这玩意可以扔到线段树上维护.

会了判定这题就做完了,做树链剖分,然后开始从下往上跳重链,能跳到顶端就跳,不然二分跳到哪里,下去是同理的,只不过下去的二分需要多个\(\log n\).

整体二分

通常解决在二分的情况下,单次check的复杂度比较高的问题.思想是把所有询问共同的check一起做.

整体二分的具体复杂度往往需要现场分析.

最常用的整体二分的写法是分治.但是有的问题(例如不能撤销)可能不太好写分治.

还有一种方式是,我们把所有询问一字排开,然后求出每个询问当前二分的\(mid\),然后顺序处理或者别的什么处理方式做这些\(mid\).

Example1([AGC002D]Stamp Rally)

直接整体二分,注意需要做可撤销并查集之类的东西.

分治

Example1(平面最近点对)

按照\(x\)轴排序,递归做两边的子问题,假设两边问题的最小值为\(d\),对着\(d\)做中间的问题.

Example2([CF1764G3] Doremy’s Perfect DS Class (Hard Version))

有一个\([ 1 , n ]\)的排列\(p\),每次可以询问\(l , r , k\),交互库会返回\(\lfloor \frac{ p_l }{ k } \rfloor , \lfloor \frac{ p_{ l + 1 } }{ k } \rfloor , \cdots , \lfloor \frac{ p_r }{ k } \rfloor\)中不同数字的个数,你需要在\(20\)次询问内找到\(p\)中\(1\)的位置.

第一反应就是令\(k = 2\),然后如果\(n\)是奇数,不难发现此时只有\(1\)自己一个人一组.一个自然的想法是,我们可以对于每个位置\(i\),查询\([ 1 , i - 1 ]\)和\([ 1 , i ]\)的答案,如果答案一样,那这个位置肯定不是\(1\).如果不一样,我们再查一下\([ i , n ]\)和\([ i + 1 , n ]\).由于\(1\)不会和左右任意一个人配对,不难发现如果这两种情况都不一样,那这里一定是\(1\),这样我们就做到了\(2 n - 2\)次查询.

那么如何优化呢?我们冷静一下,如果我们查询一个区间\([ l , r ]\),那么得到的答案自然是\(len -\)配对数字都在区间内的对数,因此我们自然也能得到这个区间的未配对数.这个时候发现,对于位置\(i\),如果我们查询\([ 1 , i ]\)和\([ i + 1 , n ]\),由于这两个区间内没配对的数字要么是\(1\),要么会和另一个区间中的数字配对,因此这两个区间中,未配对数多的那个一定包含\(1\).这样就可以通过\(k\)不断向下二分,最后只需要\(20\)步操作就可以解决\(n\)是奇数的情况.

那么\(n\)是偶数怎么办呢?这个时候\(1\)和\(n\)都没人配对.我们需要找到\(n\)并将它杀掉.注意到\(k\)可以取别的数,我们如果只是让\(k = 2\)未免有些弱,而且看上去也区分不了\(1\)和\(n\),而不难发现,令\(k = n\)就可以找到\(n\)在哪里,于是可以先找\(n\)再找\(1\),需要\(40\)步.

那怎么继续优化呢?我们还是令\(k = 2\),查询\([ 1 , i ]\)和\([ i + 1 , n ]\),我们发现此时会有两种情况:

1. 左右两边未配对数量相差\(2\),这个时候\(1\)和\(n\)一定都在较大的那边,直接递归.

2. 左右两边未配对数量相等,这个时候一定\(1\)在一边,\(n\)在另一边,我们可以通过一次查询\(k = n\)判断哪边是\(n\).

于是只需要\(21\)次.

但是还是不够,我们从哪里抠出那一次呢?发现最后处理区间\([ i , i + 1 ]\)还需要两步操作,我们看看能不能省掉一步.

1. \(1\)和\(n\)都在\([ i , i + 1 ]\)中,我们显然只需要查询一步就可以知道哪边是\(n\).

2. 只有\(1\)在\([ i , i + 1 ]\)中,我们考虑利用一下前面的信息.注意到我们一定已经知道\([ 1 , i - 1 ] , [ i , n ] , [ 1 , i + 1 ] , [ i + 2 , n ]\)的答案(如果区间为空或者区间为\([ 1 , n ]\)显然我们也知道答案),假设这个区间中的两个数是\(1\)和\(x\),\(x \in ( 1 , n )\),那么\(x\)一定有一个和它配对的数字,我们考虑通过\([ 1 , i - 1 ]\)和\([ 1 , i + 1 ]\)就可以知道和\(x\)配对的数字在\([ 1 , i - 1 ]\)还是在\([ i + 2 , n ]\).接下来只需要一步判断就可以找到\(1\)了.

Example3(XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan(opentraisn contest 1489)D Nice Set of Points)

给定一个点集\(S = \{ ( x , y ) \}\),\(( x_1 , y_1 )\)和\(( x_2 , y_2 )\)可达当且仅当\(x_1 = x_2 \lor y_1 = y_2\).称一个点集是好的当且仅当这个点集中任意两个点的最短距离是它们的曼哈顿距离.给出一个点集,大小为\(N\),\(1 \leq N \leq 1000\),加入不多于\(10000 - N\)个点使得这个点集变成好的.

找一条分界线\(x = d\),我们将这条线左右两边的点全都作出在这条线上的投影点,将这些投影点全都加入,不难发现左右两边之间的路径就合法了,继续递归就行.

Example4([CF1442D]Sum)

一个自然的想法是由于越靠后的可能越优秀,所以应该是要不断往后挖的.具体地,我们发现只可能有一个数组被选了一部分,剩下的数组要么不选,要么全选.

为什么呢?假设有两个数组各选了一部分,不妨假设它们最后选的数分别是\(a\)和\(b\),下一个未选的数分别是\(c\)和\(d\),有\(c \geq a , d \geq b\),假设\(a \geq b\),那么自然有\(c \geq b\),于是我们把\(b\)删掉换成\(c\)一定更优秀.

有了这个性质后,我们可以枚举是哪个数组只选了一部分,然后求出剩下部分的背包,背包部分可以求前缀和后缀最后合并起来,我们的复杂度就是\(O ( nk^2 )\).

但这个复杂度还是不太够,如何优化呢?

注意到这里的背包是支持撤销操作的,我们考虑一个分治做法:每次做到\([ l , r ]\)的时候,假设此时\([ 1 , l - 1 ]\)和\([ r + 1 , n ]\)都加入答案了,我们把\([ mid + 1 , r ]\)也加入背包,然后递归求解\([ l , mid ]\),然后再撤销,同样的方法求解右边的答案.复杂度\(O ( nk \log n )\).

Example5(AGC044D)

这题在于分治后归并,考虑我们是可以快速判断一个串是否是原串的子序列的,就是判断它们的编辑距离是否恰好等于长度之差.而我们也可以快速判断每个字母在原串中出现了多少次,只需要询问\(L\)个这个字母然后看编辑距离就是替换的次数.这样我们考虑对字母分治,\([ l , r ]\)表示只用到\([ l , r ]\)中的字母,得到的极长的原串的子序列是什么.边界情况\([ l , l ]\)是好处理的,对于\([ l , r ]\),我们考虑归并,合并\([ l , mid ]\)和\([ mid + 1 , r ]\)的时候不断判断当前串是否是子序列就行.

倍增

顺便一提,倍增比二分方便的一点在于:倍增能迅速确定答案的规模,这在复杂度与答案规模有关的时候至关重要.

Example1([SCOI2015]国旗计划)

先破环成链,然后设\(f_{ i , j }\)表示从\(i\)这个人,途径\(2^j\)个人后能到达的最远的人是谁,然后就可以直接通过倍增处理.

Example2([PKUSC2018]星际穿越)

Example3(CF1523H Hopping Around the Array)

类似国旗计划,只不过需要用背包合并一维.

不过吧,这题有个问题在于最后的询问,我们要每次判断当前越界的点的代价是否小于等于dp数组的代价,如果小就回撤dp数组(因为无论如何都必不可能在这里选择).

Example4(loj3665)

思考一下发现,走相同的步数能到的点一定是一段区间,于是考虑使用倍增算法,设\(f_{ x , i }\)表示从\(x\)走\(2^i\)步能到的区间,转移是简单的RMQ问题.

但是初值怎么求呢?先考虑右端点怎么求.对于每个路线\(j\),它会把\([ A_j , A_j + k - 1 ]\)能到达的右端点与\(B_j\)取\(\max\),由于查询在修改之后,所以这个东西很好做.

Example5(CF1707E)

引理1:如果\([ l , r ] \subseteq [ L , R ]\),则\(f ( ( l , r ) ) \subseteq f ( ( L , R ) )\).

引理2:如果\([ L , R ] = [ l_1 , r_1 ] \cup [ l_2 , r_2 ]\),则\(f ( ( L , R ) ) = f ( ( l_1 , r_1 ) ) \cup f ( ( l_2 , r_2 ) )\).

引理1显然,引理2是因为\([ L , R ]\)中的最大值和最小值一定都被后面的两个部分取到.

于是,考虑\([ l , r ] = \cup_{ i = l }^{ r - 1 } [ i , i + 1 ]\),就可以倍增了.

考虑求出每个单点的倍增数组,那么总区间的倍增数组也就是这些数组的最小值和最大值.

大概做一下.

Example6([22zr提高组十连测day6]百分号)

首先看上去多组询问给定起点终点看上去就很像倍增.

一个很自然的设计是\(L_{ x , i }\)表示从\(x\)这个点跳\(2^i\)所能到达的最左端的点,\(R_{ x , i }\)同理.但是能跳到最远的点不一定能跳到一个较近的点,那咋办呢?

冷静一下,注意到我们好像还没有用到括号序列的性质:两个跳跃要么包含要么不交,不可能出现第三种情况.

所以,如果目前能跳到的最远的点为\(l , r\),那么再跳一步能到达的最远的点一定是从\(l\)或\(r\)跳过去的.考虑反证这个结论,设能从\(( l , r )\)中的一个点\(k\)跳到更远的点,那么由于之前没跳到过\(k\)就跳到\(l\)了,所以一定存在一个\(i > k\),\(i \rightarrow l\),而如果存在\(j < l\),\(k \rightarrow j\),显然不满足性质.

同理,我们最后处理询问答案的时候,考虑从\(x\)和\(y\)都跳.先从\(x\)跳到再跳一步就会跳过\(y\)的位置,然后把\(y\)跳到再跳一步就会跳过\(x\)的位置,那么现在的\(x\)和\(y\)一定相邻,不然分别跳一步就会出现包含的情况,于是一定是最优解.

对称/建立双射

Example1(CF1627F)

冷静一下考虑,分界线一定是一个中心对称图形,分成的两部分一定中心对称.那这条分界线一定过中心点.

我们考虑这么一点:如果所有点对都在矩阵一边,我们就可以直接求中心点到矩阵一边的最短路然后对称一下就好了.

而矩阵上遍布点对怎么办呢?我们在和每个点对对称的位置把这个点对复制一遍,然后从中心点找到一条到边界的最短路,把它对称一下即可.

Example2([AH2017/HNOI2017]抛硬币)

设\(A\)的正面朝上为\(S_A\),\(B\)的为\(S_B\).设\(p_1 = \sum [ S_A > S_B ] , p_2 = \sum [ S_A = S_B ] , p_3 = \sum [ S_A < S_B ]\).

当\(a = b\),翻转所有硬币,自然有\(p_1 = p_3\),又设\(P = p_1 + p_2 + p_3 = 2^{ a + b }\),于是求得\(p_2\)即可得到答案.而\(p_2 = \sum_{ i = 0 }^a \binom{ a }{ i } \binom{ b }{ i }\),用范德蒙德卷积的变式,有\(p_2 = \binom{ a + b }{ a }\).

同样,当\(a > b\)时.我们设\(p_4 = \sum [ a - S_A > b - S_B ] , p_5 = \sum [ a - S_A = b - S_B ] , p_6 = \sum [ a - S_A < b - S_B ]\).同样是翻转硬币的套路,自然有\(p_4 = p_1 , p_5 = p_2 , p_6 = p_3\).注意到:\(S_A \leq S_B \Rightarrow a - S_A > b - S_B\),但逆命题不成立.不妨设\(p_7 = \sum [ S_A > S_B \land a - S_A > b - S_B ]\).自然有:

\[ p_1 = p_4 = p_7 + p_2 + p_3 = p_7 + P - p_1 \]

于是只要求出\(p_7\)就可以求得\(p_1\).

考虑\(p_7\)如何求,注意到\([ S_A > S_B \land a - S_A > b - S_B ] = [ 0 < S_A - S_B < a - b ]\),我们可以枚举\(S_A - S_B\),然后继续用范德蒙德卷积的变式.

Example3([2022qbxt国庆Day4]C)

直接考虑对于每一对位置\(( i , j ) , i < j\),计算它们可能产生的逆序对贡献.注意到每一对对答案的贡献会大概接近\(0 . 5\),我们考虑构造一个双射,判断双射左右是否都会贡献.

设\(d_i\)为\(i\)个数的错排数量,根据错排公式有\(d_n = ( n - 1 ) ( d_{ n - 1 } + d_{ n - 2 } )\).接下来讨论一下这两个位置的取值:

1. 如果\(a_i = j , a_j = i\),那么一定贡献了逆序对,这里总共贡献为\(d_{ n - 2 } \cfrac{ n ( n - 1 ) }{ 2 }\),一半的贡献也就是\(\cfrac{ d_{ n - 2 } n ( n - 1 ) }{ 4 }\).

2. 如果\(a_i = j , a_j = k , k \ne i \lor a_i = k , a_j = i , k \ne j\),考虑前后两者形成双射.如果\(k\)在\(i\)和\(j\)之间,那么无论前者还是后者,都一定贡献逆序对;不然,则两种情况一定只有一种会贡献逆序对.前者多出的贡献应该是\(\cfrac{ n ( n - 1 ) ( n - 2 ) }{ 6 } ( d_{ n - 2 } + d_{ n - 3 } )\),也就是先选出\(i < k < j\),如果\(a_k = i\),那么剩余的可能性就是\(d_{ n - 3 }\);不然,也就是说\(a_k \ne i\),类似于错排公式,剩余的可能性为\(d_{ n - 2 }\).另外,由于\(d_{ n - 2 } + d_{ n - 3 } = \cfrac{ d_{ n - 1 } }{ n - 2 }\),所以上面的贡献也就是\(\cfrac{ n ( n - 1 ) }{ 6 } d_{ n - 1 }\).

3. 如果\(i , j , a_i , a_j\)互不相同,那我们交换\(a_i\)和\(a_j\)一定可以构造出另一组答案,并且这两组答案中一定只有一组贡献了逆序对,于是二者形成双射.

除去上面的部分的贡献是\(\cfrac{ d_n n ( n - 1 ) }{ 4 }\).于是总贡献为:\(n ( n - 1 ) ( \cfrac{ d_{ n - 1 } }{ 6 } + \cfrac{ d_n + d_{ n - 2 } }{ 4 } )\).

Example4(ARC115D)

第一反应感觉完全不可做.

思考一下,如果我们随便选边肯定完蛋了:我们又不知道选出了几个奇度点,这不完蛋了?

先考虑要求全是偶度点怎么办?

由于点只有奇度点和偶度点两种,如果我能先随便选个边集,再把它删到全是偶度点好像就赢了.但是一方面我咋删啊,一方面这样删有可能删出重复的.又注意到删一条边就一定可以让两个点的奇偶性改变.

我们考虑求出原图的一棵生成树,然后剩下的边随便选.之后从生成树深度较大的点开始考虑:如果这个点是奇度点,我们就把它的父边删掉.容易发现这样是双射.而如果有奇度点的话可以先组合数选出来然后同样做上面的操作,容易发现是一样的.

不同的连通块可以分别做最后卷起来.

Example5(Hihocoder1230)

这题最重要的一点在于观察到一组\(a\)如果有解,那么一定是唯一解.为啥呢?我们考虑如何构造一个解:从小位到高位枚举,如果当前位所有数异或起来是\(1\),那么\(x\)这一位也必然是\(1\),然后加上后进位.这是由于序列长度是奇数.然后就每次对于\(a \in [ x , m + x ]\)计数,做FWT就行.

Example6(23省选10连测 day5B)

首先我们要知道,一轮冒泡排序的过程等价于:从前往后考虑每一个点,如果它前面存在一个比它大的点,就将它和前面的点交换.

于是我们考虑令\(b_i = \sum_{ j = 1 }^{ i - 1 } [ a_j > a_i ]\).也就是每次冒泡排序,这个\(b_i\)都会变成\(\max \{ b_i - 1 , 0 \}\).显然\(b_i\)需要满足的条件是\(b_i \in [ 0 , n - i ]\),接下来我们证明:只要满足这个条件,\(b\)和\(a\)就是双射关系.根据\(a\)还原\(b\)是简单的,那么如何根据\(b\)还原\(a\)呢?我们只需要从大向小考虑元素,就可以判断元素插入哪里.

有了这个条件后,我们不妨设原序列是\(a '\),其对应\(b '\),那么显然\(b_i = \max \{ 0 , b_i ' - m \} \leq \max \{ 0 , n - i - m \}\).也就是说,如果\(b_i = 0\),那么\(b_i ' \in [ 0 , m ]\),反之\(b_i ' = b_i + m\).但问题在于:我们如何保证\(b_i ' \in [ 0 , n - i ]\)呢?不难发现,冒泡排序每次会把前面最大的数扔到后面,也就是说整个序列最后的\(m\)个数一定有序,那我们分开考虑:对于最后的\(m\)个数,它一开始在序列中的相对顺序是无所谓的:无论如何都会扔到最后.而对于其它的数,如果\(b_i = 0\),\(b_i ' \in [ 0 , m ]\),由于最后都已经凑出\(m\)个数了,从大向小将数字插入,一定可以使这一部分满足条件.而如果\(b_i > 0\),由于有判定条件\(b_i \leq \max \{ 0 , n - i - m \}\),显然满足.于是我们设一共有\(k\)个\(b_i = 0\)的位置(也就是前缀最大值位置),于是自然有\(f ( a , m ) = ( m + 1 )^k m !\).注意这个式子的前提在于判定每个\(b_i \leq \max \{ 0 , n - i - m \}\)以及\(a\)的最后\(m\)个位置是\(n - m + 1 , \cdots , n - 1 , n\).到这里不难发现只要满足后者前者必定满足.现在只需要统计前缀最大值的个数就可以解决这个问题了.这个设计个\(dp_{ i , j }\)表示前\(i\)个数的最大值是\(j\)就行.

拆多项式

通常适用于数据范围中有一项的范围不大的情况,然后拆成多项式后可以带入另一项较大的值.

Example1([22zr提高组十连测day5]可)

首先考虑数位dp,每次枚举当前的\(k\)个数中还有\(x\)个数被limit,这次又有\(y\)个数不用被limit,再枚举一下当前各位之和,然后可以写一个转移,复杂度\(O ( k^4 \lg x )\)

然后想了好久发现这个东西好像优化不动了.

冷静一下,注意到问题在于枚举,我们不妨把枚举换成容斥试试.设\(g ( x )\)为\(\sum a\)为\(x\)的方案数,那么可以通过容斥得知:

\[ g ( n ) = \sum_{ i = 0 }^k ( - 1 )^i \binom{ k }{ i } \binom{ n - i ( x + 1 ) + k - 1 }{ k - 1 } \]

我们最后要求的答案也就是\(\sum f ( n ) g ( n )\),继续推式子:

\[ ans = \sum_{ n = 0 }^{ kx } f ( n ) g ( n ) = \sum_{ n = 0 }^{ kx } f ( n ) \sum_{ i = 0 }^k ( - 1 )^i \binom{ k }{ i } \binom{ n - i ( x + 1 ) + k - 1 }{ k - 1 } \]

\[ = \sum_{ i = 0 }^k ( - 1 )^i \binom{ k }{ i } \sum_{ n = 0 }^{ kx } f ( n ) \binom{ n - i ( x + 1 ) + k - 1 }{ k - 1 } \]

看上去好像推不动了.

冷静一下,会发现\(n\)的取值远远大于\(i , k\)的取值.于是我们选择把组合数拆成一个\(k - 1\)次多项式,这样只需要处理出这个多项式的每一项的系数,然后就可以预处理后面的东西.

拆二项式系数的时候要注意特判上指标小于下指标的情况.

\[ ans = \sum_{ i = 0 }^k ( - 1 )^i \binom{ k }{ i } \sum_{ j = 0 }^{ k - 1 } c_{ i , j } \sum_{ n = i ( x + 1 ) }^{ kx } f ( n ) n^j \]

其中\(c_{ i , j } = [ n^j ] \binom{ n - i ( x + 1 ) + k - 1 }{ k - 1 }\).

这样我们就成功地分离出了一项\(\sum_{ n = i ( x + 1 ) }^{ kx } f ( n ) n^j\),接下来考虑怎么处理这一项.

考虑枚举\(i\),然后设\(dp_{ j , limit } = \sum_{ n = 0 }^{ limit } f ( n ) n^j\),考虑拿数位dp做这个东西,枚举当前位置\(cnt\)的取值\(w\),根据二项式定理,\(dp_{ a + b , limit } \leftarrow \binom{ a + b }{ b } dp_{ b , limit } f ( w ) ( w 10^{ cnt } )^a\),那么\(\sum_{ n = i ( x + 1 ) }^{ kx } f ( n ) n^j = dp_{ j , kx } - dp_{ j , i ( x + 1 ) - 1 }\).

这样我们需要枚举\(i , a , b , cnt\)得到一组答案,然后还需要把这些答案合并起来,复杂度\(O ( k^3 \lg x )\).

抽屉原理

Example1([UNR #6]小火车)

首先考虑证明一定有解:

注意到我们可以先选择出两个不完全相同的集合,如果这两个集合的和相等,那么我们把只在第一个集合的\(b\)设为\(- 1\),只在第二个集合的\(b\)设为\(1\),都在或都不在的设为\(0\),那么这显然就是一组解.

而由于\(p < 2^n\),根据抽屉原理,显然存在这么两个集合.

考虑对于一个权值区间\([ l , r ]\),如果有超过\(r - l + 1\)个集合的和在这个区间内,那一定有两个集合可以组成一个解.

假设现在已知权值区间\([ l , r ]\)一定有解,我们判断\([ l , mid ]\)中是否有超过\(mid - l + 1\)个集合,使用折半搜索再合并可以快速求出权值和为某个定值的集合有多少个.然后可以使用双指针判断,继续递归下去判断即可.复杂度\(O ( 2^{ \frac{ n }{ 2 } } n )\).

Example2([NOI2021]量子通信)

考虑\(k \leq 15\),所以如果我们把两个零一串每\(16\)个分一块,那么两个零一串相差少于\(k\)处,则一定有一块完全相等.由于数据随机,这个概率为\(\cfrac{ 1 }{ 2^{ 16 } }\).

考虑把在一块中是某个数的零一串全都集合到一起,然后暴力判断,复杂度约为\(O ( \cfrac{ n^2 q }{ 2^{ 16 } w } )\).

拆贡献

Example1([2022qbxt国庆Day7]fenwick)

注意到要变换多次,考虑每个值的贡献.

一个点要往后更新,不难通过平行求和法则一个值\(v\)对它向后跳\(w\)步的贡献为\(\binom{ w + k }{ w }\).但是有修改很难办,怎么办?注意到如果我们暴力跳,查询的时候复杂度是\(O ( 1 )\)的,我们没必要让它这么低.我们把所有值对\(p\)这个点的更新存到一个数组里,显然只有\(\log n\)种步数.最后每次查询的时候用组合数一起更新即可.

Example2([QOJ5097] 小 P 爱学习)

这个题的厉害之处在于完全将贡献拆开.

我们不妨设最后将所有的数分成了\(k\)组,那么显然我们只要算出两个东西就可以得到此时的答案的和:

1. \(\sum_{ x_{ 1 , . . . , k } } \prod_{ i = 1 }^k a_{ x_i } \\\).

2. \(\sum_{ 1 \leq x_1 , . . . , x_k \leq n , \sum x = n } \frac{ ( nm - k ) ! }{ \prod_{ i = 1 }^k ( x_i m - 1 ) ! } \\\).

第一个显然就是个背包,问题在于第二个的分子部分,我们用生成函数,设\(F = \sum_{ i = 1 }^{ n } \frac{ 1 }{ ( im - 1 ) ! } x^i\),我们要求的就是\([ x^n ] F^k , \forall 1 \leq k \leq n\).

这个东西可以做BSGS,也就是光速幂.这样就可以用\(O ( n^2 \sqrt{ n } )\)预处理,用\(O ( n )\)查询单个\(k\).

Example3(Luogu4211 [LNOI2014]LCA)

将\(dep\)拆成到根节点的路径上的点的数量,差分一下\([ l , r ]\),这样就只需要求\(z\)和一个前缀点的LCA的\(dep\).将这个操作离线下来,我们对于每一个点把它到根节点的路径上的点全部\(+ 1\),查询每个点到根节点上的权值和就行.

CF757G是一样的,只不过好像需要卡卡空间?

二进制拆位

Example1(Luogu5354 [Ynoi2017]由乃的OJ)

对每一位分开处理,对于线段树上每个区间,设\(f_{ 0 }\)表示一开始\(v\)的这一位是\(0\),最后的答案是\(1\)还是\(0\),显然可以合并,拿bitset优化一下.

bitset优化暴力

Example1([2022qbxt国庆Day4]D)

先想一个很明显的优化:我们记录一下每个字符出现的位置,当我们判断当前字符串是否出现过的时候,我们直接从这个字符串开头的字符存在的位置进行判断.

如果我们记录下每个字符在母串中的某个位置是否存在,我们就可以基本脱离母串进行判断.注意到只需要用bitset优化这个过程就可以做到\(O ( \sum tlen + \cfrac{ nq }{ w } )\).

Example2([NOI2020] 制作菜品)

这题首先要根据数据范围,注意到\(m \geq n - 1\)的时候存在贪心解法.

具体怎么做呢?我们将原料按照质量排序,每次选最小的那个,不够的话就选最大的那个的一部分,重新排序后递归处理.

为啥这个是对的呢?根据鸽笼原理,最大的那个的质量一定大于等于\(\frac{ mk }{ n }\),而最小的那个数和最大的那个数之和一定大于等于\(0 + \frac{ mk }{ n - 1 } \geq k\),因此一定有解.

接下来我们就只需要做\(m = n - 2\)的情况.

那么这个怎么做呢?我们发现每道菜和两个原材料有关,于是不妨抽象成图论模型:将这两个原材料所代表的点用一条边连起来:我们发现有\(n - 2\)条边和\(n\)个点,这个图必不联通.也就是说如果有解,必然可以分成两个集合,这两个集合互不相关.如果我们分成了两个集合,一个集合有\(a\)个原材料,另一个集合有\(n - a\)个原材料,我们就可以第一个集合做\(a - 1\)道菜,第二个集合做\(n - a - 1\)道菜,自然解决了问题.

接下来的问题在于01背包,用bitset优化一下.

简化能更新答案的集合

简单来说就是当你注意到一个答案只有可能由某些地方贡献,我们就只判断这些地方的贡献.有的时候不仅需要减小集合,还需要使这个集合尽可能好维护,这个时候可能会向集合里放一些不合法但不可能更新答案的选项.

Example1(CF1149D Abandoning Roads)

首先一个把只有\(a\)边的连通块缩起来,那\(1\)到\(i\)的最短路显然是通过几个\(b\)连接若干个连通块来到\(i\).

由于防止用\(b\)边链接连通块的时候连出环,我们需要用一个\(dp_{ S , x }\)表示从\(1\)经过\(S\)集合的连通块到\(x\)的最短路.

但是集合数量可能很多,怎么办?

注意到,如果这个集合只有一个点,那显然不可能重复经过;如果这个集合只有两个点,那重复经过意味着想用一条长度为\(2 b\)的边代替一条长度为\(a\)的边,显然也不优秀;同理集合只有三个点也不优秀.

于是只有点数\(\geq 4\)的集合是有用的,复杂度\(O ( 2^{ \frac{ n }{ 4 } } m \log n )\).

Example2

给定\(n\)个正整数,要求将\(n\)个正整数分到\(k\)个集合中,每个集合恰好\(\cfrac{ n }{ k }\)个数(保证\(k | n\))且每个集合中不能有相同的数.设一个方案的代价是每个集合的极差之和,求最小代价,\(n \leq 70\).

首先\(O ( 3^n )\)很好设计不说了.

注意到这题看上去就不太能多项式复杂度,我们考虑简化一下状态数.考虑做\(O ( 3^n )\)的时候,我们是将\(\cfrac{ n }{ k }\)个数打包成一个集合再塞进去,这样看上去就不太优秀,我们考虑能不能一个数一个数塞进去.

我们现在有\(k\)个集合,要塞进去一个数到一个集合中.注意到最后的代价实际上和很多数是没啥关系的.考虑先把数字从小到大排序,然后挨个插入集合.如果插入一个数之前,这个集合是空的,那这个数对答案有负的贡献;如果插入一个数之后,这个集合是满的,那这个数对答案有正的贡献;反之无贡献.

于是我们可以枚举目前集合填成啥样了,这样状态数变成了\(( \cfrac{ n }{ k } + 1 )^k\).

这样还是过不去,我们再冷静一下,显然我们只关心每个集合填了多少个数而不关心具体是哪个集合,于是我们把每个集合的大小排序后再压成状态,这样状态数就是\(\sum_{ i = 0 }^{ k }{ \binom{ i + \frac{ n }{ k } }{ \frac{ n }{ k } } } \\\),根据目前填到第几个数分一分类就会发现这部分上限是\(O ( n \binom{ 2 \sqrt{ n } }{ \sqrt{ n } } )\).

不过我们还需要保证一个集合里不能有相同的元素.这里我们考虑将相同的元素一起放并规定放的顺序.因为放进去的集合在放这种元素前是有大小顺序的,我们每次放进最大的集合中.换句话说,我们设\(f_{ i , j , S }\)表示目前放到\(i\),状态是\(S\),并且\(a_i\)放进去的那个集合目前大小是\(j + 1\)(放前是\(j\)).

算一下复杂度是\(O ( n^2 \binom{ 2 \sqrt{ n } }{ \sqrt{ n } } )\)的,实际上远远跑不满,甚至写了个map来做双射也跑过去了.

Example3

给定一张有向图,多组询问,每次询问三个数\(p , x , y\),求是否能从\(p\)出发只经过\([ x , y ]\)中的边且经过的边的编号单调递减到达\(1\)号节点.

冷静一下,先加边,注意到如果加\(u \rightarrow v\)这条边的时候,不存在一条从\(v\)到\(1\)的路径,那这条边显然没有用.

做完这一步后,我们注意到可以在加边的过程中对于每个\(u\)维护从\(u\)到\(1\)的所有合法路径经过的最小编号的边的最大值\(maxn_u\),这样就可以对于每个点维护若干个二元组\(( l , r )\),只要对于\(p\),存在一个二元组\([ l , r ] \in [ x , y ]\)就合法.

Example4([Petrozavodsk Winter-2014. Moscow SU Tapir Contest(openstrain contest 1435) C]Combinations Strike Back)

给定一个大小为\(n\)的可重集,多次询问,每次询问查询插入一个数\(x\)后,这个集合大小为\(k\)的可重子集共有多少个,每次询问互相独立.\(n , q \leq 1 . 2 \times 10^5\),答案对\(1051721729 = 1003 \times 2^{ 20 } + 1\)取膜.

自然的想法是上生成函数.

假设数字\(i\)在原集合中共有\(b_i\)个,那么原集合大小为\(k\)的可重子集数量显然为\([ z^k ] \prod_{ i = 1 }^n \frac{ z^{ b_i + 1 } - 1 }{ z - 1 }\).

插入一个数字\(x\),自然就是乘上一个\(\frac{ z^{ b_x + 2 } - 1 }{ z^{ b_x + 1 } - 1 }\).但如果每次都乘的话复杂度显然不行.怎么办?

注意到答案与插入的数字本身无关,只和这个数字在原集合中出现了多少次有关.而原集合最多有\(\sqrt{ n }\)(自然根号)个出现次数不同的数字,预处理一下就行.

Example5([CF1621G]Weighted Increasing Subsequences)

一个自然的想法是拆出每个点\(x\)的贡献,再枚举终点\(y\),这样问题就转化为了以\(y\)结尾并且包含\(x\)的LIS计数,这样做到\(O ( n^2 )\)的复杂度.

那么怎么继续优化呢?我们还是想拆出每个点的贡献,但是如何不枚举终点\(y\)呢?我们考虑枚举一下和它做贡献的点\(z\)满足\(a_z > a_x\)并且终点\(y\)满足\(y < z\),但是这样的\(z\)有很多个,不难发现取最后一个就行.如果我们对整个序列取后缀\(\max\),就可以得到所有可能被当作\(z\)的点,而且更强的性质是,只要这些点不在LIS中,LIS的终点\(y\)必然有\(y < z\),这是显然的.做一下补集转化,就变成了计数包含\(x\)和\(z\)的LIS数量.

注意到\(z\)的数量不多,且所有数字按照权值排序后被这些\(z\)分成了若干个区间.所以颠倒值域和下标重新做LIS就行.

Example6(CF919F A Game With Numbers)

最小表示法表示每个人的手牌.

不过要注意有可能成环.我们考虑用刷表法更新,最后刷不出来的点就是和.

Example7([IOI2014]holiday)

首先发现走的一定是一个区间,然后发现这个区间\([ l , r ]\)的\(l\)随\(r\)的增大具有决策单调性,然后做完了,上主席树就行.

Example8(CF1446D2)

我们假设目前得到的答案区间是\([ l , r ]\),也就是说\([ l , r ]\)无论如何不可能扩展成更大的区间了.那这需要满足什么条件呢?注意到全局众数一定是答案,如果它不是答案,我们就可以往两边拓展,直到满足区间众数是答案且区间合法.显然可以实现.然后做根号分治.

这个是怎么想到的呢?我们考虑一个区间如何拓展成更大的区间:如果每个数出现次数不降,显然是一个更大的区间.这同样是在说:如果我们能找到一段区间,使得加上这段区间后,原本不是区间众数的数成为了区间众数,并且区间仍然合法,那就一定更为优秀.再注意到如果一个数在全局出现次数多于区间众数,这一定可以实现,进而推出全局众数的结论.

你以为结束了?没有,我们下面给出一个\(O ( n \log n )\)的做法:

首先,我们假设全局众数是\(x\),枚举和它一起成为区间众数的数字\(y\),剩下的数先不管,那么区间大概长这个样:xyxyyxyxxxxxx.

我们发现这一段x一定是没有意义的:xyxyyxyxx[xxxx].

我们对于每一个\(y\)出现的位置,找到其左右两边离他最近的没有被标记的\(x\)标记一下,没有被标记的\(x\)一定没有意义.这样对于一组解\(( x , y )\),合法的端点数量只有\(O ( y 出 现 的 次 数 )\)次.每次判断每个端点是否可以做右端点,拿\(set\)维护一下后缀和就可以实现\(O ( n \log n )\).

当然,这里得到的区间不一定是合法的(有可能\(x , y\)出现的次数都不是最多的,但没关系,这种一定不优秀).

【luoguP4062 [Code+#1]Yazid 的新生舞会】也是这个标记的思路,标记的话用一下链表之类的大概能做.

支配对问题

lxl起的名字.

这里的思路其实大概就是:我们将一些很废物的二元组杀了,然后将剩下的二元组进行贡献答案.我们称这种一个二元组严格强于另一个二元组的限制称作支配关系.

第一类支配对

虽然总数很多,但是本质不同的很少.

Example1(luoguP7880 [Ynoi2006] rldcot)

我们这么考虑:如果现在有三个点\(a , b , c , a < b < c\),它们两两LCA都是\(d\),那么显然\(( a , c )\)这一对是没有用的,有用的是\(( a , b )\)和\(( b , c )\).进一步你发现这等价于什么呢:我们从下往上合并子树,每次做启发式合并,假设当前要把子树\(A\)合并到子树\(B\)上,考虑所有的点对\(( a , b ) , a \in A , b \in B\)的贡献,显然,能贡献到\(a\)的\(b\)只有\(a\)的前驱和后继,这样我们就只找到了\(O ( n \log n )\)个点对,它们等价于\(O ( n \log n )\)个矩形,最后把\(dep\)相等的合并一下,随便做做.

Example2(luoguP8528 [Ynoi2003] 铃原露露)

和Example1基本差不多.

第二类支配对

虽然总数很多,但是有用的很少.

Example1(CF765F)

典.

Example2(CodeChef MINXORSEG)

这个题比较厉害,仍然考虑\(a < b < c\),我们看如果\(a \oplus c > \max \{ a \oplus b , b \oplus c \}\)的充要条件是什么.

简单分类讨论一下,不难发现这意味着\(LCP ( a , c ) > LCP ( a , b )\).于是有用的贡献对只有\(O ( n \log v )\)个.

Example3(Luogu9058 [Ynoi2004] rpmtdq)

这题更为逆天.

首先,这题有两个维度:树和序列,我们要先处理掉其中一维.lxl:树这一维度更加困难,因此我们应该是选择困难的那一维分治掉.

考虑边分治,然后就只需要处理两棵子树间的贡献.但是对于一棵子树内的点,我们要找到在另一棵子树中有可能和它产生贡献的点对,这个咋做呢?

牛逼的一步来了,我们考虑对于每个点,算出它到分治中心的距离\(r\),然后找另一棵子树中到分治中心距离\(\leq r\)的点\(x\)与它贡献,但是这还是有很多点,其实只需要找这些点中的\(x\)的前驱后继就可以了.因为如果\(x < b < c\),\(b\)和\(c\)在同一边,那么\(( b , c )\)一定比\(( a , c )\)更加优秀.

Example4(CF1635F Closest Pair)

首先,由于匹配无序,我们考虑对于一对数\(( i , j )\),只在\(w\)较大的那个位置来更新答案.

不妨假设较大的为\(i\),我们考虑\(i\)有可能和谁来更新答案.

如果现在有两个数\(k < j , w_k \leq w_i \land w_j \leq w_i\),如果\(w_k \geq w_j\),那肯定选\(( j , i )\)更优秀;不然,如果选\(( k , i )\)比选\(( j , i )\)更优秀,那么我们会发现\(( k , j )\)比\(( k , i )\)更要优秀,因此答案一定会由\(( k , j )\)更新而不是由\(( k , i )\)更新.通过这里的分析我们发现,每个数只有可能和它左右两边的第一个\(w\)小于等于它的数更新.

于是我们可以找到\(O ( n )\)个可能更新答案的点对,设点对为\(( x , y )\),我们每次查找一个区间\([ l , r ]\),即要找到所有在\([ l , r ]\)内的点对并将它们的答案取min.

这一步可以将\(( x , y )\)当作二维平面的点,查询当作一个左下角为\(( l , l )\),右上角为\(( r , r )\)的矩阵,就是一个经典的矩阵取min的操作.

Example5([ICPC2017 WF]Money for nothing)

注意到抽象问题后等价于有若干个A点\(( x_1 , y_1 )\)和若干个B点\(( x_2 , y_2 )\),我们想要找到一个A点和一个B点使得\(( x_1 - x_2 ) ( y_1 - y_2 )\)最大.也就是它们作为右上和左下顶点的矩形面积最大.

怎么做这个问题呢?首先我们必须要发现的一点是:对于A点来说,如果有两个点\(( a_1 , b_1 )\)和\(( a_2 , b_2 )\)满足\(a_1 \leq a_2\),\(b_1 \leq b_2\),那么前者一定更优秀.把那些废点删掉后,就会得到一个横坐标递增,纵坐标递减的点的序列.对于B点是同理的.

这个序列看上去就很亲切了,接下来简单证明一下是满足决策单调性的就可以判断答案了.

奇偶染色

Example1

一个\(9 \times 9\)的网格,一开始上面有\(65\)个蚂蚁,每个蚂蚁每分钟会四联通移动一格,每个蚂蚁每三分钟所在的格子不能在一条直线上,求证:一定会有一个时间,两只蚂蚁在同一个格子里.

sol1:

注意到如果条件不成立,则一定存在若干条路径,蚂蚁在路径上转圈,也就是找到长度和尽可能大的路径不交地覆盖矩阵,注意到一定是使用\(2 \times 2\)的矩阵路径,于是最多有\(64\)只蚂蚁.(感性理解)

sol2:

考虑对奇偶染色,设\(( i , j ) = \begin{cases}white & 2 \nmid ( i + j ) \\ blue & 2 \mid i \land 2 \mid j \\ yellow & \text{ otherwise }\end{cases}\).

我们把黄格子和蓝格子称为彩格子,注意到如果一开始一只蚂蚁在白格子,一分钟后必定在彩格子.一开始一只蚂蚁在蓝格子,两分钟后必定在黄格子.

因为最多有\(16\)个蓝格子,所以一开始黄格子和蓝格子上分别最多有\(16\)只蚂蚁,从而白格子上最多有\(32\)只蚂蚁,总共最多\(64\)只,得证.

Example2(CF1521E)

首先考虑我们显然可以一行空一行放,也就是说如果最大的\(a_i > n \times \lceil \frac{ n }{ 2 } \rceil\)的话显然不可以,如果能放的位置少于\(\sum a\)显然也不可以.

类似lyz那个题,我们考虑删去行列编号均为偶数的点,这样就满足了一个子矩阵不能全放的限制.

然后呢?我们考虑将所有能放的位置排序.先把所有的位置分成三类:\(( \mathrm{ even } , \mathrm{ odd } ) , ( \mathrm{ odd } , \mathrm{ odd } ) , ( \mathrm{ odd } , \mathrm{ even } )\),不同类位置按照这个顺序排,不然按照相对位置排.然后直接从头开始放.如果不合法,一定是同种颜色放到了\(( \mathrm{ even } , \mathrm{ odd } )\)和\(( \mathrm{ odd } , \mathrm{ even } )\),并且相同类别是按照相对位置排序的,于是一定不满足最大的\(a_i \leq n \times \lceil \frac{ n }{ 2 } \rceil\)的限制条件.所以这么做一定是对的.

好!冷静一下,咋想到的啊.

首先这种题肯定要找到一些看上去就很显然的边界,当你发现找不到的时候,大概率就一定有解了(大概率).

然后呢?注意到不合法一定是同种颜色放到了\(( \mathrm{ even } , \mathrm{ odd } )\)和\(( \mathrm{ odd } , \mathrm{ even } )\),又观察到每种位置的数量和一个边界限制条件很像,于是就可以构造出来了.

所以大概是说,这种构造题要先想判断边界的条件,然后对着做.

Example3(CF1615F)

太牛逼了这个题.

首先,找边界条件:啥时候\(s\)不能变成\(t\)呢?一个自然的想法是数\(1\)的个数的奇偶性,但这样显然不对(\(01\)和\(10\)不能互相转移),我们需要一个更强的条件.

然后:注意到每次操作是相邻的两个数,于是我们有:奇数位置的和-偶数位置的和是定值.但是:注意到这个操作是有限制的!它只能对相邻相同的位置做.

然后我也不知道咋想到的,可能是因为找到限制条件后只要不改变限制条件就可以随便转化?反正我们先把偶数位置全部取反,这样操作就变成了交换相邻数字(如果相邻数字不相同,取反后相同,交换无用).

就可以dp了.

Example4(CF1517G)

按照横纵坐标的奇偶性,分四种情况染色.注意到四边形接下来的路径一定会形如\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\),建立分层图跑最小割.

捆绑更新答案

Example1([2022qbxt国庆Day6]binary)

首先因为有\(- 1\),我们先考虑一个朴素的暴力,从\(L\)到\(R\)枚举现在被匹配的数\(i\),我们假设之前匹配到\(p - 1\),那我们接下来一定是要找到一个最小的\(x \geq p\)能把\(i\)给匹配掉,仔细思考这个过程,由于是二进制考虑最高位,不难发现我们只需要找到\(( p \land i ) \oplus i\)的最高位\(1\),然后把\(p\)的这一位改成\(1\),然后后面的位置全部设成\(0\),如果\(i \subseteq p\)那么就不用改.

冷静一下,二进制大概率是没啥通项公式的,还是要一点一点做.但是我们枚举每一个数实在是太慢了,我们考虑一个地方:\(i \subseteq p\)就不用改,下一步\(i + = 1 , p + = 1\),如果没有发生进位还是不用改,这个过程看上去就很可以优化.

所以我们考虑:当遇到\(i \subseteq p\)的时候,我们就捆绑更新.如果不满足就暴力更新.重复这个过程,每次不断暴力更新\(\rightarrow\)捆绑更新\(\rightarrow\)暴力更新\(\rightarrow . . .\).每次捆绑更新至少会更新一个\(lowbit\),而暴力更新的情况下,每次\(p\)至少会多包含一位\(i\).就算后面进位把这一位消掉了,由于这里进位了,那下一步一定可以直接包含掉,于是复杂度也是\(\log n\)的,反复做一下就做完了,这里能分析复杂度\(O ( T \log^2 R )\).我们冷静一下,发现二者复杂度算重了,捆绑更新会帮助暴力更新多匹配\(1\),于是复杂度\(O ( T \log R )\).但是肯定跑不满,考场甚至写了个上界\(O ( T \log^2 R )\)的仍然跑的飞快.

Example2

给定一棵树和一个值域为\(n\)序列\(a\),每次询问给出\(l , r , x\).

设\(f ( x , y )\)为点\(x\)朝着\(y\)的方向走一步后得到的点,求\(x\)在经过\(a [ l \cdots r ]\)操作后得到的答案.

这么考虑:这题看上去就需要把任何一个数字\(x\),通过若干个点变成了一个\(f ( x )\),我们要做的就是把\(f ( x )\)求出来,这玩意很难求,考虑分块,单点用长剖做\(O ( 1 )\)求\(k\)级祖先,然后对于每个整块预处理出它的\(f\)就可以了.

接下来的问题在于如何快速处理一个块的答案,考虑把所有的\(x\)扔到树上,然后一起维护它们的\(f ( x )\).这玩意看上去好像有点不太能做.

牛逼的一步来了:考虑对于每个块内的\(\sqrt{ n }\)个点,建立这些点的虚树,对于不在虚树上的点,它们一定会往虚树的方向跑(其实也就是向上跑),然后处理出时间扫描线转化成在虚树上的点的问题.对于在虚树上的点,考虑虚树一共有\(O ( \sqrt{ n } )\)条边(也就是原树上的路径),我们用一个双端队列维护每条边上的点,显然每次每条边只会有\(O ( 1 )\)的入队和出队,这样就实现了\(O ( n )\)的预处理单个块.

单独更新答案

Example1

一个数轴上有\(n\)个小球,第\(i\)个小球在\(x_i\)坐标处.数轴上还有\(m\)个洞.第\(i\)个洞在\(y_i\)坐标处.你每秒可以以相同矢量速度移动所有小球.当一个小球和一个洞重合时,小球就会进洞.求一共可能出现多少种最终情况.(我们认为,两种”最终情况”不同,当且仅当存在一个球在两种情况中进入了不同的魔法洞中)

考场的想法:按照洞分类,把被同样两个洞夹起来的球一起处理,显然会有一段区间往左走一段区间往右走,按照这种区间的长度排序,然后硬dp,复杂度\(O ( n^3 )\).

实际的做法:我们抛弃区间,单独考虑每个球.对于每个球而言,有用的信息只有它到左端点的距离和它到右端点的距离.我们把这两个距离缩为\(( x_i , y_i )\).接下来我们要给每个点\(0 / 1\)染色,如果是\(0\)代表它要到左边的洞里,如果是\(1\)代表要到右边的洞里.那什么染色条件是无解的呢?

如果存在两个点\(a\)和\(b\),\(col_a = 0\),\(col_b = 1\),那显然当\(x_a \geq x_b \land y_a \leq y_b\)时无解.换句话说,如果\(col_b = 1 \land x_a \geq x_b \land y_a \leq y_b\),那么\(col_a = 1\).我们不妨按照\(x\)降序排序,\(x\)相同的按照\(y\)升序排列.那就会先决定\(b\)再决定\(a\).注意到:如果\(a\)能确定\(c\)的状态,那\(b\)一定也能确定\(c\)的状态.因此我们采取这个策略:如果\(x_a \geq x_b \land y_a \leq y_b \land col_b = 1\),那我们直接不管\(a\);反之,则考虑一下\(a\)的两种取值即可.具体一点,我们设\(f_{ i , 0 / 1 }\)表示以\(i\)结尾,\(col_i = 0 / 1\)的方案数,然后顺着做就好.注意到:我们其实不关心\(col_x\)具体是啥,我们只关心最后的方案数.所以其实可以直接删去第二维.

zhq对这题的理解:

这可以等价成求一个上升子序列.上升子序列说的是如果\(x_i < x_j , y_i > y_j\),\(i\)“选了”,\(j\)就必须”不选”.但是钦定必须选和必须不选,这两个限制是一样的.就是说,\(j\)没有选择的权力了.

这个说法很有意思,但是要注意:类似说法成立当且仅当我们认为\(j\)选了和认为\(j\)没选对后面不会产生影响.

Example2([Petrozavodsk Summer-2015. Moscow IPT Contest(openstrain contest 1464) J]Two Airlines)

这是一道交互题.给定一张\(n\)个点的完全图,每两个点之间是红色的边或是蓝色的边.可以询问\(2 n\)次某两个点之间的边的颜色,求一条哈密顿回路使得这条路上的颜色段最多有两个.

考虑将点逐个加入.假设现在的哈密顿回路的两种颜色分别是\(r_s \rightarrow r_t\)和\(b_s \rightarrow b_t\),当前要加入\(x\),我们每次询问\(x\)和\(r_t\)和\(b_t\)之间的颜色,如果可以加入链就加入.如果不能加入,必然意味着\(x\)和\(r_t\)之间是蓝边,和\(b_t\)之间是红边,我们查一下\(r_t\)和\(b_t\)之间是什么边,然后将其中一个点与\(x\)一起扔到对面就行.

不过这样用了\(3 n\)次询问,考虑先询问\(r_t\)和\(b_t\)之间的颜色,这样就能省掉一种.

寻找不变量

Example1([NOIP2021] 方差)

首先我们注意到:设\(b_i = a_i - a_{ i - 1 }\)这个操作相当于交换\(b_{ i - 1 }\)和\(b_i\).

接下来推一下式子:

\[ \begin{aligned} n^2 S^2 & = n \sum_{ i = 1 }^n a_i^2 - ( \sum_{ i = 1 }^n a_i )^2 \\ & = n \sum_{ i = 1 }^n ( \sum_{ j = 1 }^i b_j )^2 - ( \sum_{ i = 1 }^n ( n - i + 1 ) b_i )^2 \\ & = n \sum_{ i = 1 }^n \sum_{ j = 1 }^i b_j \sum_{ k = 1 }^i b_k - \sum_{ j = 1 }^n ( n - j + 1 ) b_j \sum_{ k = 1 }^n ( n - k + 1 ) b_k \\ & = n \sum_{ j = 1 }^n b_j \sum_{ k = 1 }^n b_k \times ( n - \max \{ j , k \} + 1 ) - \sum_{ j = 1 }^n ( n - j + 1 ) b_j \sum_{ k = 1 }^n ( n - k + 1 ) b_k \\ & = n \sum_{ j = 1 }^n b_{ n - j + 1 } \sum_{ k = 1 }^n b_{ n - k + 1 } \times \min \{ j , k \} - \sum_{ j = 1 }^n jb_{ n - j + 1 } \sum_{ k = 1 }^n kb_{ n - k + 1 } \end{aligned} \]

令\(c\)为\(b\)的倒置数组,则原式

\[ \begin{aligned} & = n \sum_{ j = 1 }^n c_{ j } \sum_{ k = 1 }^n c_{ k } \times \min \{ j , k \} - \sum_{ j = 1 }^n jc_{ j } \sum_{ k = 1 }^n kc_{ k } \\ & = 2 \sum_{ j = 1 }^n nc_j \sum_{ k = 1 }^j c_k k - 2 \sum_{ j = 1 }^n jc_{ j } \sum_{ k = 1 }^j kc_{ k } + \sum_{ i = 1 }^n c_i^2 i ( i - 1 ) \\ & = 2 \sum_{ j = 1 }^n ( n - j ) c_j \sum_{ k = 1 }^j c_k k + \sum_{ i = 1 }^n c_i^2 i ( i - 1 ) \\ & = \sum_{ j = 1 }^n ( n - j ) c_j \sum_{ k = 1 }^n c_k k + \sum_{ i = 1 }^n ( n - 1 ) ic_i^2 \end{aligned} \]

推到这一步发现好像没啥用但是推了好久懒得删了

冷静一下,由于一开始的数列是单调递增的,所以改变后的数列一定也是单调递增的(差分数组均\(\geq 0\)).感性上理解,我们肯定是想让尽可能多的数接近绝对值,于是让重新排列后的差分数组呈现单最小值的峰看上去就很优秀.

这样我们设计\(dp_{ i , S }\)表示现在填到第\(i\)小的\(b\),\(\sum a = S\)的情况下最小的\(\sum a^2\),复杂度\(O ( n^2 a )\).

注意到\(a\)很小的时候大部分\(b\)都是\(0\),于是可以优化为\(O ( na^2 )\).

Example2([AGC030E] Less than 3)

注意到:当我们把一个位置取反的时候,这个位置相邻的左右两个位置一定有一个\(0\)和一个\(1\),所以我们的操作等价于移动\(0\)和\(1\)的分界线.

然后枚举一下从边界多产生了多少个分界线就行.

组合意义

Example1(ARC110D)

注意到这相当于先把一个长度等于\(m\)的序列划分成\(n + 1\)段,再从第\(i\)段选出\(a_i\),其中\(a_{ n + 1 } = 0\).

于是自然是\(\binom{ n + m }{ \sum a + n }\).

Example2(ABC231G)

乍一看,感觉完全不可做.因为一开始给定\(a\)了,感觉上好像也不太能组合意义.

如果没有\(a_i\)怎么做?我们设\(f_n\)表示将\(k\)个小球分到\(n\)个盒子后的答案.那乘法相当于:分完后,在每个盒子中取出一个小球的方案数.于是\(f_n = \binom{ k }{ n } n ! n^{ k - n }\).

那给定\(a\)咋做呢?我们注意到上面的式子好像可以对于任意\(n\)快速求.于是将原式子拆为:\(\prod ( a_i + b_i )\),那答案就是选出\(n - x\)个\(a\)和选出\(x\)个\(b\)的答案.前者可以背包,后者也就是\(f_x = \binom{ k }{ x } x ! n^{ k - x }\).

Example3(AGC060D)

不妨设\(C_p = \{ i | p_i > p_{ i + 1 } , 1 \leq i < n \}\).

用一下组合意义,注意到答案等于:

\[ \sum_{ S } ( \sum_{ p } [ S = C_p ] )^2 \]

中间那个地方看上去是经典的计数容斥,我们对着它做容斥:

\[ \sum_{ S } ( \sum_{ p } [ S = C_p ] )^2 = \sum_{ S } ( \sum_{ S \subseteq T } \sum_{ p } ( - 1 )^{ | T | - | S | } [ T \subseteq C_p ] )^2 \]

这个咋做呢?我们考虑用组合意义展开:

\[ \begin{aligned} & \sum_{ S } ( \sum_{ S \subseteq T } \sum_{ p } ( - 1 )^{ | T | - | S | } [ T \subseteq C_p ] )^2 \\ = & \sum_{ S } \sum_{ S \subseteq T_1 , T_2 } ( - 1 )^{ | T_1 | + | T_2 | } ( \sum_{ p } [ T_1 \subseteq C_p ] ) ( \sum_p [ T_2 \subseteq C_p ] ) \end{aligned} \]

注意到\(S\)屁用没有,直接交换枚举顺序.

\[ \begin{aligned} & \sum_{ S } \sum_{ S \subseteq T_1 , T_2 } ( - 1 )^{ | T_1 | + | T_2 | } ( \sum_{ p } [ T_1 \subseteq C_p ] ) ( \sum_p [ T_2 \subseteq C_p ] ) \\ = & \sum_{ T_1 , T_2 } 2^{ | T_1 \cap T_2 | } ( - 1 )^{ | T_1 | + | T_2 | } ( \sum_{ p } [ T_1 \subseteq C_p ] ) ( \sum_p [ T_2 \subseteq C_p ] ) \end{aligned} \]

考虑\(( \sum_{ p } [ T_1 \subseteq C_p ] )\)怎么求,注意到这等价于所有\(T_1\)中的位置全都被钦定为\(>\),而其他位置任意,如果我们设所有以大于号连接的部分的长度为\(l_1 , l_2 , . . . , l_k\),那么这里的答案就是\(n ! \prod_{ i = 1 }^k \frac{ 1 }{ l_i ! }\).

但我们很快发现了难点:\(2^{ | T_1 \cap T_2 | }\)这个东西是难求的,怎么办呢?

我们考虑一下这个东西的意义:其实也就是在\(T_1\)和\(T_2\)中都是\(>\)的位置,这个好像不太好求,因为\(>\)是很平常的,但如果取补集就不一样了,取补集后意味着都是任意的位置的数量,而我们上面已经发现了:如果有一个位置对前后两个数字的约束是独立的,那我们可以把前后两个位置拆开.于是我们有:

\[ \begin{aligned} & \sum_{ T_1 , T_2 } 2^{ | T_1 \cap T_2 | } ( - 1 )^{ | T_1 | + | T_2 | } ( \sum_{ p } [ T_1 \subseteq C_p ] ) ( \sum_p [ T_2 \subseteq C_p ] ) \\ = & \sum_{ T_1 , T_2 } 2^{ ( ( n - 1 ) - | T_1 \cup T_2 | ) - ( n - 1 ) } ( - 2 )^{ | T_1 | + | T_2 | } ( \sum_{ p } [ T_1 \subseteq C_p ] ) ( \sum_p [ T_2 \subseteq C_p ] ) \\ = & 2^{ 1 - n } ( n ! )^2 \sum_{ T_1 } ( ( - 2 )^{ | T_1 | } \frac{ 1 }{ \prod l_{ 1 , i } ! } ) \sum_{ T_2 } ( ( - 2 )^{ | T_2 | } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) 2^{ n - 1 - | T_1 \cup T_2 | } \end{aligned} \]

其中\(n - 1 - | T_1 \cup T_2 |\)意味着均不在\(T_1\)和\(T_2\)中的位置的数量.为了给每一段连续的\(>\)都分配权值,我们进行一个细小的修改:

\[ 2^{ - 1 - n } ( n ! )^2 \sum_{ T_1 } ( ( - 2 )^{ | T_1 | + 1 } \frac{ 1 }{ \prod l_{ 1 , i } ! } ) \sum_{ T_2 } ( ( - 2 )^{ | T_2 | + 1 } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) 2^{ n - 1 - | T_1 \cup T_2 | } \]

写到这里应该就能发现,接下来必然要对\(n - 1 - | T_1 \cup T_2 |\)做整体操作.那我们再这么搞可能就很难受,我们采取这样的方式:对\(T_1\)和\(T_2\)求补集,这样它们的含义就变成了除了集合中的元素,剩下的全部被钦定为了\(>\),我们自然有:

$$ \[\begin{gathered} 2^{ 1 + n } ( n ! )^2 \sum_{ T_1 } ( \frac{ 1 }{ ( - 2 )^{ | T_1 | + 1 } } \frac{ 1 }{ \prod l_{ 1 , i } ! } ) \sum_{ T_2 } ( \frac{ 1 }{ ( - 2 )^{ | T_2 | + 1 } } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) 2^{ | T_1 \cap T_2 | } \\ \end{gathered}\]

$$

这里已经很显然了,我们大概要做一个不断加段的做法,那此时\(| T_1 \cap T_2 |\)这个限制就显得尤其强,如果只是\(S \subseteq T_1 , T_2\)就会好做很多:我们可以钦定\(S\)作为分界线,然后把两边的东西卷起来.因此我们暴力拆开后面的式子:

$$ \[\begin{aligned} & 2^{ 1 + n } ( n ! )^2 \sum_{ T_1 } ( \frac{ 1 }{ ( - 2 )^{ | T_1 | + 1 } } \frac{ 1 }{ \prod l_{ 1 , i } ! } ) \sum_{ T_2 } ( \frac{ 1 }{ ( - 2 )^{ | T_2 | + 1 } } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) 2^{ | T_1 \cap T_2 | } \\ = & 2^{ 1 + n } ( n ! )^2 \sum_{ S } \sum_{ S \subseteq T_1 } ( \frac{ 1 }{ ( - 2 )^{ | T_1 | + 1 } } \frac{ 1 }{ \prod l_{ 1 , i } ! } ) \sum_{ S \subseteq T_2 } ( \frac{ 1 }{ ( - 2 )^{ | T_2 | + 1 } } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) \\ \end{aligned}\]

$$

令\(f ( T ) = \sum_{ S \subseteq T } ( \frac{ 1 }{ ( - 2 )^{ | T | + 1 } } \frac{ 1 }{ \prod l_{ 2 , i } ! } ) \\\),则原式即:

\[ 2^{ 1 + n } ( n ! )^2 \sum_{ S } ( \sum_{ S \subseteq T } f ( T ) )^2 \]

考虑下面这个东西怎么求:

\[ \sum_{ S } ( \sum_{ S \subseteq T } f ( T ) )^2 \]

注意到,如果我们把每一段(\([ T_i , T_{ i + 1 } )\))的贡献求和,那么\(f ( T )\)相当于这些和乘起来,那么\(( \sum_{ S \subseteq T } f ( T ) )^2\)就是这些和的平方乘起来.换句话说,我们自然有\(ans_n = \sum_{ m } ans_{ n - m } g^2_{ m }\),其中\(g_m\)表示长度为\(m\)的一段的贡献之和.而\(g_{ n } = \sum_m g_{ n - m } \frac{ 1 }{ - 2 m ! }\).二者都可以使用分治FFT或多项式求逆解决.更进一步地,\(h_i = \frac{ 1 }{ - 2 i ! } , G = \frac{ 1 }{ 1 - H } , F = \frac{ 1 }{ 1 - G }\).

这题还有一个做法:tyy的变魔术做法.

还是容斥,考虑将\(( > , > )\)容斥掉,这样我们有若干种对:\(2 ( < , < ) , 1 ( e , e ) , - ( e , < ) , - ( < , e )\),然后我们发现两个序列联系得太紧了,我们考虑分配系数:\(< \rightarrow \sqrt{ 2 }\),\(e \rightarrow - \frac{ 1 }{ \sqrt{ 2 } }\),但是这样发现\(( e , e )\)算错了,你把剩下的补上就行.你会发现这个式子和上面我们推的是等价的,但是变魔术.

复杂度抵消

Example1(CF1439B)

首先注意到度数小于\(k - 1\)的点一定没用,于是可以不断删点.删点后的图度数全部\(\geq k - 1\).

首先如果剩下的点度数全都\(\geq k\)那就直接找到答案,不然,我们看一下度数为\(k - 1\)的点:它要么在团里,要么没用.不妨直接暴力判断是否在团里,复杂度\(O ( k^2 )\).

欸等一下,这总复杂度\(O ( mk^2 )\)了啊,这咋办?

首先,删完点后的度数全都\(\geq k - 1\),注意到此时的点数是\(O ( \frac{ m }{ k } )\)的.所以复杂度\(O ( mk )\).

好像还是过不去,这咋办?

冷静一下,如果\(k \geq \sqrt{ m }\),显然不可能存在团.于是复杂度\(O ( m \sqrt{ m } )\).

寻找关系式

Example1

一张有向图,边有两种颜色,从\(s\)开始随机游走,维护一个权值.经过第一种颜色的边,权值\(+ 1\).经过第二种颜色的边,权值归\(0\).保证\(t\)没有出边,所有点均能到\(t\).询问到\(t\)时权值的期望和方差.\(n \leq 100\).

(注意方差为平方的期望减去期望的平方.)

注意到难点在于权值归\(0\).所以一个点到\(t\)的期望权值一定和到达它时的权值有关系.

然后就来到了降维打击的时间:我们可以使用数学归纳法证明,如果到一个点\(u\)的权值是\(x\),那它到达\(t\)的权值一定形如\(a_u x + b_u\).

如果要严谨一点的话,我们发现第一种颜色的边会影响常数项,第二种颜色的边会影响一次项,因此最后的答案一定是一次函数.

最后可以使用高斯消元直接求出每个点权值的\(a_u\)和\(b_u\),就可以求出期望.

至于方差是同理的,你注意到平方的期望一定是一个二次函数.

特判边界

Example1(2022ICPC杭州E)

第一反应肯定是一点一点调整成\(\{ 1 , 2 , . . . , n \}\)的形式,写个暴力验证一下发现当\(n \geq 4\)的时候的确都可以调整成功.

假设目前形如:\([ 1 , k ] , A , k + 1 , B\).我们考虑如何调整:

1. \(| B | \ne 0\).

我们有:

\[ \{ [ 1 , k ] , A , k + 1 , B \} \rightarrow \{ B , A , k + 1 , [ 1 , k ] \} \rightarrow \{ [ 1 , k + 1 ] , B , A \} \]

2. \(| B | = 0 , | A | = 0\).

直接合并就行.

3. \(| B | = 0 , | A | \geq 2\).

假设\(A = A_1 A_2\),我们有:

\[ \{ [ 1 , k ] , A_1 , A_2 , k + 1 \} \rightarrow \{ A_2 , k + 1 , A_1 , [ 1 , k ] \} \rightarrow \{ [ 1 , k + 1 ] , A_1 , A_2 \} \]

4. \(| B | = 0 , | A | = 1\).

此时一定有\(k \geq 2\),发现有点难构造,但是我们猜测是可以构造出来的.不难证明这个问题等价于将\(\{ 1 , 2 , 4 , 3 \}\)调整为\(\{ 1 , 2 , 3 , 4 \}\),写个暴力跑一下就行.

摩尔投票

Example1([CF643G]Choosing Ads)

将摩尔投票扩展一下.我们现在想求其中出现次数大于等于\(\lfloor \frac{ n }{ p } \rfloor\)的数字,令\(k = \lfloor \frac{ 100 }{ p } \rfloor\),我们考虑每次取出\(k + 1\)个两两不同的数字并且全部杀掉,那么做完这一步操作后,该满足条件的仍然满足条件(讨论一下),于是拿线段树维护当前的五个数的出现数量,每次对着杀就行.

寻找周期性

Example1([CF1463F]Max Correct Set)

自然的想法是\(O ( n 2^{ \max ( x , y ) } )\)作dp.

接下来比较牛逼的是,注意到如果\(S_1\)满足条件,令\(m = x + y\)那么\(S_1 \cup ( S_1 + m )\)也满足条件.

我们考虑\(S_1\)中满足条件意味着什么,意味着\(\forall a , b \in S_1 , a < b\),\(b - a \ne x \land b - a \ne y\),这意味着\(m + b - a \ne x \land m + b - a \ne y\),这同样意味着\(m + a - b = x + y + a - b \ne x + y - x \land m + a - b \ne x + y - y\).

因此,只要我们找到了一个长度为\(m\)的可行解,我们一定可以将其不断扩展到全部集合.

进一步地,我们一定能证明:原集合中的最优解是以一个长度为\(m\)的可行解作为周期的.

这个是为啥呢?我们设\(n = km + c\),那么我们直接求出一个长度为\(m\)的解,满足前\(c\)位对答案的贡献的权值是\(k + 1\),后\(m - c\)位贡献的权值为\(k\),然后直接求答案.注意到如果最大答案另有其人,我们一定可以拿其中的某一段不断循环得到更大的答案,这就不符合我们的假设了.

补集转化

Example1

给定一个\(n\)个点\(m\)条边的无向图,求给每一条边定向使得\(1\)和\(2\)能到达同一个点(可以是\(1\)或\(2\))的方案数.\(n \leq 15 , m \leq \frac{ n ( n - 1 ) }{ 2 }\).

考虑正难则反,算不存在的概率(事实上也确实很好理解,因为存在性问题通常都要取补集),这时候我们发现:此时\(1\)能到达一个集合\(S\),\(2\)能到达一个集合\(T\),\(S\)和\(T\)无交,并且两个集合之间不可能存在边,因此我们只需要算\(f ( S )\)表示\(1\)能到达\(S\)中的点的方案数即可,\(2\)同理.

那么这个怎么算呢?我们仍然考虑正难则反,如果\(1\)不能到达\(S\)中的所有点,那么\(1\)一定只能到达\(S\)中的一部分点,枚举这一部分,假设是\(T\),就可以用\(f ( T )\)算\(f ( S )\)的答案.

二进制分组

Example1(loj3273)

先考虑没有插入怎么做,注意到所有的线会扫出一个空白区域:这个空白区域由一条折线围成,而所有的点都在折线外或在折线上,更进一步地,在折线外的点没有动,就是初始位置.

这启发我们分开维护,每次扫线的时候更新折线,把该扔进来的扔进来,由于折线上的点\(( x , y )\),随着\(x\)的增大\(y\)不增,因此是简单维护的,用一下平衡树就行.

问题在于如何维护插入点.我们使用二进制分组,将所有点分为大小为\(0 , 1 , 2 , 4 , \cdots , 2^k\)大小的组,当然有些组可能没被分出来.然后如果有两个大小都是\(2^k\)的组,我们暴力合并二者,得到一个还没被折线扫过的新的大小为\(2^{ k + 1 }\)的组.

Example2(Luogu7447 [Ynoi2007] rgxsxrs)

一眼看上去和CF702F很像,但是区间操作感觉很艰难,怎么做呢?

我们对值域分块:分成\([ 0 , 1 ) , [ 1 , 2 ) , [ 2 , 4 ) , [ 4 , 8 ) , \cdots\),这样只会分成\(\log V\)段,每段内部维护平衡树来处理下标.那么对于一个\(x\),它会把后面的段全部打上一个\(tag\),有些位置要掉落到下面的段上,这个维护每个段的最小值就可以处理(最多只会掉落\(\log n\)段),问题是和\(x\)在同一块内的没有办法打tag,但这一部分一定会掉落到下面的段,一块处理.

好,下面开始思想总结:

首先,我们发现这个区间和值域都很难处理,但是感觉值域更加重要,应该是对值域做均摊(也就是类似CF702F的打tag操作和暴力修改操作分开),于是考虑到对值域分块然后内部平衡树,然后发现可以做了吧.不太清楚,也有可能只是值域分块的套路.

Luogu9069是同款思路,判一下负数.

Example3(CF1515I Phoenix and Diamonds)

俗称带修T-shirt.

做法大概是这样的:我们考虑对于每次给出的\(c\),不妨假设它在\([ 2^k , 2^{ k + 1 } )\)这个块上,那么如果它减去了任何一个还在这个块里的数字,那就一定会掉落到下一个块中.这样就又有均摊了.

但是我们不一定能减去一个还在这个块里的数字,我们怎么做呢?

我们考虑最后的操作一定是减去若干个小于这个块的,最后有可能再减去一个这个块的,然后\(c\)就掉到了下一个块,考虑先按照价值排序,然后维护\(f_i\)表示排名在\(i\)前面且代价在更小的块中的代价和,我们要找到最靠左的小于\(c - 2^k\)的\(f\),这个可以做线段树二分维护.

[IOI2021]地牢游戏 类似,但是因为是在图上做,所以把二分要改成倍增.

The Bright Morning Star(A Sequel to A Streetcar Named Desire)

MATRON: This is her room. [She knocks on the door.] Miss DuBois,

here is someone who wants to visit you.

MITCH [overwrought]: Thank you. Has anyone visited her before? And

has she recovered?

MATRON: No, no. Although she has recovered a lot, sometimes she’ll

crouch over and tremble in corners as if someone will hurt her, and

she’ll try to hit anyone who wants to touch her when she’s insane.

[*She pushes the door open and lets Mitch in. The room where Blanche

lives now is a pure white space without windows, and a naked bulb

brightens the whole room as if it were daylight. There is a collapsible

bed in the corner of the room and a Bible on the table. Blanche sits on

a chair in a blue dress and stares at Mitch, which makes Mitch feel a

little guilty. Then the Matron goes out and leaves Mitch in the room.*]

MITCH [keeping his head lower, staring at his hands]: Hello, Miss

… DuBois.

BLANCHE [happily]: Hello, Mitch. I’m glad that you could visit me.

You know, I haven’t spoken to anybody for a long time. I … I didn’t

mean that the Doctor and the Matron treated me badly, and I also didn’t

mean that you are just a … talkative partner in my heart. [*Her voice

dies out nervously.*] You know that, you know that … did you bring

some whiskey or lemon coke for me?

MITCH: No, the Matron said that you can’t have any liquor.

BLANCHE: That’s a pity. Did you bring some unwashed grapes for me?

MITCH: What?

BLANCHE [smiled]: That’s just a joke.

MITCH [relieved]: It’s a relief to see you more delighted and

energetic now. [There is a pause.] The room is so … white, like a

… marble palace.

BLANCHE [delightedly]: Yes. Yes, I know that you mean to say “Ivory

tower”. The room is neat and … it is better than Elysian Fields,

right? I feel like a new human being with the white walls, the light,

and the Bible here. And Shep Huntleigh called me a few seconds ago. Soon

I’ll leave here and go to the real palace, being old and full of days.

The Lord will bless the latter end of mine more than my beginning.

[*The music of the polka rises, faint in the distance. She gets

crazy] No, no, I don’t want to hear it again! [Mitch gets

shocked.*] I’m sorry for that. I … I don’t know why sometimes I

behave like … like … Oh, how is your mother?

MITCH [sadly]: She has passed on.

BLANCHE: I’m sorry to hear that. [There is a pause.] Oh, don’t let

silence ruin our meeting. We haven’t met for …

MITCH: Seven months.

BLANCHE: Yes, seven months … It’s difficult for me to count the days

because there’s no calendar, nor sun … How about Stella’s baby? When I

feel lonely at night, I will miss the lovely baby. I haven’t seen him

… or her? Oh, it is not important, you know, Stella is my precious

little sister, and her baby is my precious little nephew … although

the baby’s father is … Stanley.

MITCH [avoiding Blanche’s eyes]: That’s why I came here, Blanche, I

have known the brutal thing that Stanley had done. I feel angry and …

sorry for it. I want to confess my behavior to you and … beseech your

forgiveness. [His voice dies out.]

BLANCHE: What thing? I must forget something. Pardon me, let me remember

for a moment … [*She starts shaking all over and panting for

breath.] No, no, no! [She screams*] That’s enough.

MITCH [bravely]: You know, Blanche. I … I’m sorry for what Stanley

… and I have done.

BLANCHE: I forgive you! You are the man that is without sin.

MITCH [shocked]: No, no, I’m not …

BLANCHE [raising her voice]: You are the one! It is you who lighten

my life … although just for a while. But that is not your fault. I

don’t deserve the light for my sinful self. It must be God’s punishment

…

MITCH [restlessly]: No, Blanche, you are …

BLANCHE: A courtesan, I’ve known it.

MITCH [embarrassedly]: No, Blanche, I didn’t mean that.

BLANCHE [with a bitter smile]: So why do you come here? To remind me

of the past which I try to forget, to sneer at my fate that I have been

trapped in this prison, or just because you want to have a sweet rest

without guilt?

MITCH [embarrassedly]: No, no, Blanche, I come here with kindness. I

know the memory of Stanley is so harsh for you and I … I have no

hostility to mention it. And … and, you see, the room is not so bad as

a prison. It is safe. No one will hurt you here.

BLANCHE [coldly]: And no one will love me here.

[They keep silent for a while.]

MITCH [nervously]: Maybe we can turn the light off. The room is too

bright.

BLANCHE [with a bitter smile]: Don’t touch the button. From the

first day I came here, the merciful Doctor and the Matron kept the bulb

on because they thought I’d be cured when there was no night. It works!

Now I love the light, it makes the room like a … white coffin. Yes, a

white coffin made of white woods.

MITCH: Don’t talk about death. You said you were afraid of it.

BLANCHE [faintly]: That was the past. In the past, I always wanted

to get away from death. Before I met you, I escaped to desire; after I

met you, I was lost in hope. In the past, I clutched at anything that

would tell me that I’m alive, and when there was no solid thing in

reality, I tried to clutch at myself … although I’m not solid enough.

The seven months I have spent here helped me understand death. Maybe

death isn’t just about crying and darkness but salvation and light. I

thought I dreamt about Jesus a few days ago and he said, “Today shalt

thou be with me in paradise.” I wanted to ask him what paradise is like

but … I could speak no word, and then I woke up ... But, but I could

imagine it! You see, the room is … is as stainless as heaven. You see

I’m more delighted and energetic here! It is doubtless that I’ll keep

delighted and energetic in heaven after I pass on … if I can go to

heaven by entering in at the strait gate … Do you think I can?

MITCH: Yes, of course.

BLANCHE [laughed]: God love you for a liar! But let me tell you the

truth: I’ve chosen a wide way that leadeth to destruction … it’s real

… but why I talk about the truth …

MITCH: I’m serious. I have made up my mind to come here … and I want

to take you away.

BLANCHE: I am not clean enough.

MITCH: Everyone is not clean enough. Everyone has … a sinful past. The

world is broken, Blanche …

BLANCHE: No, Mitch. I'm too delicate and painful, but you … are

realistic and natural. How can we live together … just because we long

for a partner? Sick people have such deep, sincere attachments. But the

truth is that I’m sick and you’re not. How can you forbear me when I’m

on the edge of lunacy and want magic?

MITCH: If we … get married, I swear that you won’t be on the edge of

lunacy.

BLANCHE [sobbing]: I will. I’m too vulnerable and the world is …

always too harsh. [There is a pause.] It’s getting late. Maybe the

bright morning star has risen.

MITCH: But …

BLANCHE [cutting him off, keeping sobbing]: Will you attend my

funeral in the future? I have no idea when it will be held. But I know

it will come soon.

MITCH: Don’t say that.

BLANCHE: It’s a pity I can’t attend my own funeral. But I could imagine

it. It will be quiet and stainless, with pretty flowers … right?

MITCH [hesitantly]: Yes.

BLANCHE: Will I be buried at sea at noon in the summer?

MITCH [sobbing]: Yes.

BLANCHE: I wonder if you will cry for me that day. But don’t … don’t

answer me. Let it be a mystery, a fantastic mystery, just like the end

of a fairy tale. I had read so many fairy tales when I was young and I

always imagined that I’m a princess living in a palace, in a magic

palace, waiting for my prince and then having a happy ending. Everyone

believes that the protagonists of stories will have a happy ending, and

I’ll also believe it. Do you know the French story La Porte étroite?

MITCH: You know, I read few books.

BLANCHE: It’s my mother’s favorite novel. Do you believe that at the end

of the story, the hero and the heroine get married and have a happy

ending?

MITCH [sobbing]: I believe it.

BLANCHE [smiled palely]: Why are you so sad? Oh, don’t cry. Tears

are so precious that you should save them for more precious people.

[*Mitch covers his face with his hands. Blanche wants to wipe away his

tears at first, but then she hesitates and turns back.*]

BLANCHE: God shall wipe away all tears from our eyes, for the former

things are passed away.

MITCH [raising his head with eyes full of tears, hesitantly]: Do you

… do you still remember the inscription?

BLANCHE: What inscription? I have forgotten about it.

MITCH: Alright … alright, I’ll go. Good night, Miss DuBois.

BLANCHE: I shall say “Good night” till it be morrow.

[MITCH leaves.]

BLANCHE: And if God choose, I shall but love thee better after death.

[The lights fade away.]

END

SUMMARY

At the end of A Streetcar Named Desire, Blanche says she has forgotten

something. In this sequel, Mitch visits the asylum where Blanche is

living to express his wish to take Blanche away. Blanche refuses him

despite her love for Mitch. While living in the asylum, Blanche has

understood more about death and love. She knows she is not clean enough

and wants to go to heaven and love Mitch after death.

Or is this sequel just Blanche’s another dream before death? In the

Bible, there is no night nor sun in heaven, just like the room.

THEME

It’s an attempt to explain Blanche’s change after Stanley’s rape. Before

that, she was afraid of death and tried to avoid harsh light. But after

that, she claimed that she’d be buried at noon. I tend to link it to her

chase for a fancy world like heaven.