出题人：hx073269（ABCD）、四糸智乃（EFG）

这次和HX大佬合场非常愉快，大家都玩的比较开（毒）心（瘤）。期待下一次合作。

A-科学家的模型

考点：思维

显然有多种解法，出题人的做法如下：

设置一个变量ans，初值为0。接着遍历矩阵，如果当前位置的字符为‘1’，则统计这个位置上下左右有多少个字符为‘1’。如果有3个‘1’，则ans++。

最后判断ans的值，如果ans为0表示图片中的数字为0；如果ans为1表示图片中的数字为9；如果ans为2表示图片中的数字为8。

时间复杂度： ${O(1)}$ 。

B-音乐家的曲调

考点：尺取法

我们设定：如果区间内每种小写字母的出现个数不超过m，则这个区间为合法区间，否则为非法区间。那么若[l,r]为非法区间，则[l,r+1],[l,r+2],...,[l,n]均为非法区间，同样的[l-1,r],[l-2,r],...,[1,r]也均为非法区间。因此其区间端点具有单调性，可以使用尺取法。

那么我们从左到右使用一次尺取法，对每个r求出最长的合法区间[l,r]，令pre[r]=max(pre[r-1],r-l+1)，即保存前缀最大值，pre[i]表示[1,i]能选出的最长的合法区间长度。

接着从右往左再使用一次尺取法，对每个l求出最长的合法区间[l,r]，令suf[l]=max(suf[l+1],r-l+1)，即保存后缀最大值，suf[i]表示[i,n]能选出的最长的合法区间长度。

得到这两个数组后，令答案为ans，初值设为0。最后再来一次尺取法，令ans=max(ans,r-l+1+pre[l-1]+suf[r+1])。最后ans即为所求。

除此之外，本题还有DP方法也可以通过。

时间复杂度： ${O(n)}$ 。

C-哲学家的沉思

考点：单调栈+倍增

比较套路的一题。使用单调栈预处理出每个元素右边第一个比它大的元素的下标，再使用倍增预处理出st表，对每个询问利用st表跳跃计算答案即可。

时间复杂度： $O((n+q)\cdot log_2n)$ 。

D-数学家的迷题

考点：线段树+bitset

我们用一个数字串表示每个数含有素数的情况，若其含有第i小的素数，则数字串的第i位为1，否则为0。例如对于数字12，其含有2(第1小的素数)和3(第2小的素数)两个素数，所以它的数字串表示为11000...。显然可以通过分解质因数，求出每个数字的数字串。

那么对于二类型的询问，就是将[l,r]区间数字代表的数字串全部或起来，然后输出数字串上1的个数。我们可以利用线段树来维护区间或值，而较长的01数字串的或操作以及计算1的个数等操作，则可以利用bitset实现。

时间复杂度： ${O((n+m)\cdot (log_2n*num_1/64+num_2))}$ ，其中 ${num_1}$ 代表 ${10^5}$ 以内素数的个数，而 ${num_2}$ 代表 $10^{\frac{5}{2}}$ 以内素数的个数。

E-F-音游家的谱面(Easy version and Hard version)

考点：动态规划+动态规划的优化+单调栈/队列+前后缀max+回溯法

本题是一本动态规划优化套路的“教科书”，不擅长做dp优化的同学可以学习一下。

题意：

两只手一只初始在最左侧，一只初始在最右侧，两只手每个时间单位都可以选择移动到相邻的位置或者不动。求双手手按照顺序到达m个固定位置的最短时间，并且依次输出到达每个目标点的时间。（只要求到达最终节点的时间最小，前面的时间只要合法即可，不做其他要求）

思路：

首先能够想到的，最无脑最暴力的DP是这样。假设只要一只手能动，那么至多N*M个回合就能够走完所有的目标位置。
所以就开一个三维数组dp[N][N][N*M]，其中dp[i][j][k]表示左手在i，右手在j，当前的时刻为k时完成了多少个目标，k所表示的状态也同时作为整个动态规划的阶段，最后扫一遍找dp[i][j][k]==m中最小的k即可。
此时的时空复杂度均为 $O(N^3M)$ 。

至于方案的输出，可以通过记录动态规划转移的前驱状态的方式进行回溯。

具体来讲的话就是通过维护一个pre数组，像链表一样每次跳到转移到该状态的上一状态即可。
接下来开始进行优化。

优化一：（Easy Version）

先从动态规划的阶段开始考虑，对于本题，选用时间作为动态规划的阶段，一个个时间单位得递推过去是最直观最显然的，但是这样不够优。
这里不是说选时间作为阶段不好，而是说这样“阶段划得太细”了没有必要这么细致的精确到每个时间单位。实际上由于目标位置也要按照时间递增的顺序去处理，所以直接用这个状态做动态规划的阶段就好了。
所以此时开一个三位数组dp[N][N][M],其中dp[i][j][k]表示左手在i，右手在j，已经完成了k个目标位置花费的最小时间，k所表示的状态也同时作为整个动态规划的阶段。
此时的时空复杂度均为 $O(N^2M)$ （已经足以通过Easy 版本）
欸？这里有没有认真看的同学提出疑问？
如果认真看到这里，理应对这个时间复杂度抱有疑问。
一般来讲，动态规划的时间复杂度=阶段数*状态数*决策数。

从dp数组上来看，阶段数*状态数已经是 $N^2M$ 了，决策转移还需要一个 ${N}$ ，那时间复杂度不应该是 $O(N^3M)$ 么？
这个问题其实你打表看一看就会发现好多INF（无效状态）。
然后你继续观察一下就会发现，对于dp[i][j][k]的合法状态，等式i==pos[k]或者j==pos[k]必有一成立。

这个动机就是接下来做下一步优化的“重要条件”。

优化二：

想一下为什么会出现这个奇妙的现象：i==pos[k]或者j==pos[k]必有一成立。
虽然看上去貌似很神奇，但是这不是废话么，你要用手去摁音符，那音符出现的时候手肯定得过去吧。所以这个时候就可以想到能优化成dp[i/j][k][0/1]，后面的01状态表示到底是i==pos[k]还是j==pos[k]。

然后你再想一下，左手右手不都是爷的手？分那么细干嘛？干脆01状态也不要了。

变成dp[N][M]，其中dp[i][k]表示其中一只手在i，另一只手在pos[k]，摁到第k个音符所用的最小时间。

此时时间复杂度为 $O(N^2M)$ ，空间复杂度为 ${O(NM)}$ 。

优化三：

到这里其实就基本没有什么性质可以利用了，还差一手数据结构没有用，然后这个状态转移是一个朴素的区间赋值取min，单点查询，用线段树维护即可。
此时时间复杂度为 ${O(NMlogN)}$ ，空间复杂度为 ${O(NM)}$ 。

优化四：(Hard Version)

这个优化的方向其实写出优化三这个代码之后就会有感觉。

for(int i=1;i<=m;++i)
{
    scanf("%d",&pos[i]);
    ST.buildt(1,1,n);
    for(int j=1;j<=n;++j)
    {
        if(dp[i-1][j]!=INF)
        {
            p1=pos[i-1],p2=j;
            ///p1 ->
            timeLimit=abs(pos[i]-p1);
            L=max(p2-timeLimit,1);
            R=min(p2+timeLimit,n);
            ST.change(1,L,R,make_pair(dp[i-1][j]+timeLimit,j));
            ///p2 ->
            timeLimit=abs(pos[i]-p2);
            L=max(p1-timeLimit,1);
            R=min(p1+timeLimit,n);
            ST.change(1,L,R,make_pair(dp[i-1][j]+timeLimit,j));
        }
    }
    for(int j=1;j<=n;++j)
    {
        pair<int,int>resdata=ST.get(1,j);
        dp[i][j]=resdata.first;
        pre[i][j]=resdata.second;
    }
}

这里给出优化三，也就是将题目写到线段树优化转移的代码。（完整代码见帖子最下方std）

p1表示用来摁音符的手，p2表示自由移动的手。

这两种转移在做优化的时候，它们的优化思路是不一样的，（这也是本题的难点之一）。

先看p1部分，当摁音符的手去摁下个音符时，则有 ${timeLimit=abs(pos[i]-pos[i-1])=C}$ ，是一个常数。

问题转化成定划窗区间极大值问题，用单调队列维护。

所以用下面这段代码替换///p1 -> 的部分，即可做到该种转移的线性。

///p1 ->
int pin=1;
head=1;
tail=0;
for(int j=1;j<=n;++j)
{
    while(pin<=n&&L[pin]<=j)
    {
        while(tail-head+1 > 0 && que[tail].first >= dp[i-1][pin] + abs(pos[i]-pos[i-1]) )tail--;
        que[++tail]=make_pair(dp[i-1][pin] + abs(pos[i]-pos[i-1]),pin);
        ++pin;
    }

    while(tail-head+1 > 0 && R[que[head].second]<j)++head;
    if(tail-head+1 > 0)
    {
        if(dp[i][j]>que[head].first)
        {
            dp[i][j]=que[head].first;
            pre[i][j]=que[head].second;
        }
    }
}

再看p2部分，当自由手去摁下一个音符时，则有 ${timeLimit=abs(pos[i]-j)=0,1,2,3...}$ ，而 ${L=max(pos[i-1]-timeLimit,1),R=min(pos[i-1]+timeLimit,n)}$

这不巧了，所有覆盖的区间长度随着 ${timeLimit}$ 单调递增，分情况套路之后可以认为是随着 ${j}$ 单调的。

那更简单了，它自己就单调，我连单调栈都省了，直接进行一个前后缀 ${max}$ 操作就解决了。

所以用下面这段代码替换///p2 -> 的部分，即可做到该种转移的线性。

///p2 ->
for(int j=1;j<=n;++j)
{
    timeLimit=abs(pos[i]-j);
    l=max(pos[i-1]-timeLimit,1);
    r=min(pos[i-1]+timeLimit,n);
    mind[l]=min(mind[l],make_pair(dp[i-1][j]+timeLimit,j));
    mind[r]=min(mind[r],make_pair(dp[i-1][j]+timeLimit,j));
}
for(int j=1;j<=pos[i-1];++j)
{
    mind[j]=min(mind[j],mind[j-1]);
}
for(int j=n;j>=pos[i-1];--j)
{
    mind[j]=min(mind[j],mind[j+1]);
}
for(int j=1;j<=n;++j)
{
    if(dp[i][j]>mind[j].first)
    {
        dp[i][j]=mind[j].first;
        pre[i][j]=mind[j].second;
    }
}

最终优化后，时空复杂度均为 ${O(NM)}$ 。

所以这个题综合性满强的，如果不会做的话我非常推荐你补一下。

小结(dp优化套路题对策)

首先要对题目有感觉，毛估估能写出什么样的dp，不要求一步到位，只要复杂度不是多项式界别的暴力，能大概做个dp就行。（这个需要大量刷题获得）

接下来按照顺序从这几个角度考虑

1、首先一定要先检查dp的阶段选的合不合适，因为一个dp阶段定了，大方向就定了，从某些角度入手可能就是不太好优化。
2、对于动态规划中使用的状态做优化，要特别关注状态之间是否有恒等关系，或者特定情况下是某个定值。例如dp[i][j][k],存在恒等关系i+j=k。有些可能是隐含的，比如本题这种dp[i=pos[k]][j][k]或dp[i][j=pos[k]][k]必有一成立，就可以优化成dp[i/j][k][2]。
3、看决策是否具有单调性，这里主要是针对一些不等式/单调队列、栈/斜率优化。
4、从数据结构层考虑，动态规划是不是统计类问题，是不是带有连续区间的增、删、改、查，是不是需要引入线段树等数据结构，bool类型的dp是不是需要引入bitset等。
5、从代码实现层考虑，是选用for循环还是记忆化搜索，需不需要bfs队列辅助转移。这里的意思是说如果你dp设计的不是很好，或者dp数组天然的有大量的非法/无效状态的时候，用搜索的方式可以快速过滤无效状态。例如可以证明，dp数组的空间复杂度和算法运行的时间复杂度不对等。（这种以状压dp居多，很多二进制状压dp都充斥着大量的非法/无效状态，借助搜索会比朴素的二进制枚举更快）
6、从非动态规划的角度考虑，指搜索减枝或者贪心。例如你选用记忆化搜索作为dp的实现方式，那它在是一个DP的同时也是一个dfs，在搜索到一些具有特殊性质的状态可以快速得出答案的时候就不用继续再展开了。

G-水果家的背包

考点：生成函数+可逆背包+背包泛化物品+多项式化简+多项式卷积+树上差分/前缀和

首先你要具备一定的背包和生成函数基础。

首先先科普一下关于01背包计数及其逆背包的相关知识。

01背包计数问题及其逆背包生成函数

若要去掉某个物品的影响，就需要构造一个背包使得该背包的生成函数 $g(x)=\frac{1}{f(x)}=\frac{1}{1+x^{w}}$ ，则f(x)*g(x)=1，也就是可以消除01背包产生的影响。

体积为w，贡献（系数）为负的完全背包，其生成函数为 $g(x)=1-x^{w}+x^{2w}-x^{3w}+...\pm x^{\infty } =\frac{1-(-x^{w})^{\infty }}{1-(-x^{w})}$

由于生成函数中多项式x的幂代表背包的体积，所以我们并不关心 $(-x^{w})^{\infty }$ 这一项到底代表什么，因为背包的体积是有限的，无限的项并不能影响有限。所以该项并不对答案提供任何贡献。

所以 $\frac{1-(-x^{w})^{\infty }}{1-(-x^{w})}\Leftrightarrow \frac{1}{1+x^{w}}$ 在该问题中等价。

所以f(x)*g(x)=1，则表示正贡献01背包与负贡献完全背包互为逆运算。

正贡献01背包数组与负贡献完全背包数组的卷积为空背包数组（dp[0]=1,dp[i]=0,i>0），则空背包数组为单位元，正贡献01背包数组和负贡献完全背包数组互为逆元。

然后还要科普一下多重背包计数问题以及其逆背包的相关知识。

多重背包计数问题以及其逆背包生成函数

多重背包的生成函数为：假设某物品的体积为w，并且这种物品有N个，则生成函数 $F(x)=1+x^{w}+x^{2w}+x^{3w}+...+x^{Nw}=\frac{1-x^{(N+1)w}}{1-x^{w}}$ ，不妨拆分成两部分，即 $f(x)=1-x^{(N+1)w}$ ， $g(x)=\frac{1}{1-x^{w}}$ 。则F(x)=f(x)*g(x)。也就是说该多重背包的效果和f(x)与g(x)所表示的背包叠加的效果相同。

$f(x)=1-x^{(N+1)w}$ 为负贡献（系数）01背包的效果，相当于放入一个负贡献体积为(N-1)*w的物品。

$g(x)=\frac{1}{1-x^{w}}$ 为正贡献（系数）完全背包的效果，相当于放入无穷多个正贡献，体积为w的物品。

所以先往背包里面放一个负贡献体积为(N-1)*w的物品，再放无穷多个正贡献，体积为w的物品，就可以达到放入N个体积为w的物品这个效果啦。

多重背包的逆元也就是找到生成函数为 $G(x)=\frac{1}{F(x)}=\frac{1-x^{w}}{1-x^{(N+1)w}}$ 的背包，这个其实就是刚才多重背包的倒数，所以方法相同，拆解为f(x)*g(x)两部分，相当于两个背包效果的叠加。于是令 $u(x)=1-x^{w}$ ， $v(x)=\frac{1}{1-x^{(N+1)w}}\; \;$ ，G(x)=u(x)*v(x)。说明该逆背包和u(x)与v(x)所表示的背包叠加效果相同。

$u(x)=1-x^{w}$ 为负贡献（系数）01背包的效果，相当于放入一个负贡献体积为w的物品。

$v(x)=\frac{1}{1-x^{(N+1)w}}$ 为正贡献（系数）完全背包的效果，相当于放入无穷多个正贡献，体积为(N-1)*w的物品。

F(x)*G(x)=1，说明F(x)与G(x)所代表的背包互为逆操作，放入的物品也互为逆物品，两者的卷积为空背包(dp[i]=[i==0])。

嘛...其实就是...emmm各种意义上面的反一反就行了。

然后还需要科普一下分组背包泛化物品的生成函数相关知识。

分组背包泛化物品计数问题以及其逆背包生成函数

分组背包的生成函数为： $f(x)=1+x^{w_{1}}+x^{w_{2}}+x^{w_{3}}+x^{w_{4}}+...+x^{w_{m}}$

但是也可以将分组背包中每组都可以泛化成一个物品，比如一个有m个互斥物品的组，体积分别为w1,w2,w3...wm

把这整个组当成一个整体，视为一个物品，就可以转化为泛化物品的01背包问题。

本题中可令 $\Delta =x^{w_{1}}+x^{w_{2}}$ , $\Delta$ 表示该组泛化成的物品。然后01背包的生成函数为 $f(x)=1+\Delta$ ，需要找到生成函数为 $g(x)=\frac{1}{1+\Delta }$ 的背包。

将泛化物品做负贡献的完全背包的生成函数为： $g(x)=1-\Delta +\Delta ^{2} -\Delta ^{3} +...+\Delta ^{\infty }=\frac{1-(-\Delta)^{\infty }}{1+\Delta }$ ，然后因为 $\Delta =x^{w_{1}}+x^{w_{2}}$ ，是一个不含常数项的多项式，生成函数中幂代表体积，所以 $(-\Delta)^{\infty }$ 不提供贡献 $\frac{1-(-\Delta)^{\infty }}{1+\Delta }\Leftrightarrow \frac{1}{1+\Delta }$

所以f(x)*g(x)=1,之前的所有结论在泛化物品下也是成立的，不过需要注意的是，如果多重背包中放的是泛化物品， $\Delta ^{k}$ 表示一个多项式的k次幂，所以最后在计算答案的时候要展开还原成x的多项式。

然后就是本题，分组背包套多重背包计数问题。

分组背包套多重背包计数问题以及其逆背包生成函数

本题中每个互斥的组的生成函数为：

$F(x)=1+x^{w_{1}}+x^{2w_{1}}+x^{3w_{1}}+x^{4w_{1}}+...+x^{N_{1}w_{1}}+x^{w_{2}}+x^{2w_{2}}+x^{3w_{2}}+x^{4w_{2}}+...+x^{N_{2}w_{2}}$

$=(1+x^{w_{1}}+x^{2w_{1}}+x^{3w_{1}}+x^{4w_{1}}+...+x^{N_{1}w_{1}})+(1+x^{w_{2}}+x^{2w_{2}}+x^{3w_{2}}+x^{4w_{2}}+...+x^{N_{2}w_{2}})-1$

$=\frac{1-x^{N_{1}w_{1}+w_{1}}}{1-x^{w_{1}}}+\frac{1-x^{N_{2}w_{2}+w_{2}}}{1-x^{w_{2}}}-1$

$=\frac{1-x^{w_{2}}-x^{N_{1}w_{1}+w_{1}}+x^{N_{1}w_{1}+w_{1}+w_{2}}+1-x^{w_{1}}-x^{N_{2}w_{2}+w_{2}}+x^{N_{2}w_{2}+w_{1}+w_{2}}-(1-x^{w_{1}}-x^{w_{2}}+x^{w_{1}+w_{2}})}{1-x^{w_{1}}-x^{w_{2}}+x^{w_{1}+w_{2}}}$

$=\frac{1-x^{N_{1}w_{1}+w_{1}}-x^{N_{2}w_{2}+w_{2}}+x^{N_{1}w_{1}+w_{1}+w_{2}}+x^{N_{2}w_{2}+w_{1}+w_{2}}-x^{w_{1}+w_{2}}}{1-x^{w_{1}}-x^{w_{2}}+x^{w_{1}+w_{2}}}$

即 $F(x)=\frac{1-x^{N_{1}w_{1}+w_{1}}-x^{N_{2}w_{2}+w_{2}}+x^{N_{1}w_{1}+w_{1}+w_{2}}+x^{N_{2}w_{2}+w_{1}+w_{2}}-x^{w_{1}+w_{2}}}{1-x^{w_{1}}-x^{w_{2}}+x^{w_{1}+w_{2}}}$
不妨设 $\Delta _{1}=x^{N_{1}w_{1}+w_{1}}+x^{N_{2}w_{2}+w_{2}}-x^{N_{1}w_{1}+w_{1}+w_{2}}-x^{N_{2}w_{2}+w_{1}+w_{2}}+x^{w_{1}+w_{2}}$
再设 $\Delta _{2}=x^{w_{1}}+x^{w_{2}}-x^{w_{1}+w_{2}}$
$\Delta _{1}$ 和 $\Delta _{2}$ 为分组背包泛化物品。

$\Delta _{1}$ 有5个分量，分别为：
1、体积为 $N_{1}w_{1}+w_{1}$ 的正贡献物品。
2、体积为 $N_{2}w_{2}+w_{2}$ 的正贡献物品。
3、体积为 $N_{1}w_{1}+w_{1}+w_{2}$ 的负贡献物品。
4、体积为 $N_{2}w_{2}+w_{1}+w_{2}$ 的负贡献物品。
5、体积为 $w_{1}+w_{2}$ 的正贡献物品。

这五个分量是等价的，在状态转移时属于同阶段同状态的不同决策，所以需要同时转移。
$\Delta _{2}$ 有3个分量，分别为：

1、体积为 $w_{1}$ 的正贡献物品。
2、体积为 $w_{2}$ 的正贡献物品。

3、体积为 $w_{1}+w_{2}$ 的负贡献物品。

这三个分量是等价的，在状态转移时属于同阶段同状态的不同决策，所以需要同时转移。

然后我们用 $\Delta _{1}$ 和 $\Delta _{2}$ 替换掉F(x)中的多项式，得到 $F(x)=\frac{1-\Delta _{1}}{1-\Delta _{2}}$ 。
接下来像之前做多重背包一样进行拆解，令 $f(x)=1-\Delta _{1}$ ， $g(x)=\frac{1}{1-\Delta _{2}}$ ，则F(x)=f(x)*g(x)。说明F(x)所代表的背包是f(x)和g(x)代表的背包效果叠加。
f(x)表示负贡献01背包（物品为泛化物品 $\Delta _{1}$ ），g(x)表示正贡献完全背包（物品为泛化物品 $\Delta _{2}$ ）。
转移的时候注意负贡献物品在做负贡献背包的时候贡献为正（负负得正）。
下面说说这个分组多重背包的逆背包。

需要找到生成函数为 $G(x)=\frac{1}{F(x)}=\frac{1-\Delta _{2}}{1-\Delta _{1}}$ 的背包。将G(x)拆解为两个函数，令 $u(x)=1-\Delta _{2}$ ， $v(x)=\frac{1}{1-\Delta _{1}}$ ，则G(x)=u(x)*v(x)说明G(x)所代表的背包是u(x)和v(x)两个生成函数代表的背包效果叠加。

u(x)表示负贡献01背包（物品为泛化物品 $\Delta _{2}$ ），v(x)表示正贡献完全背包（物品为泛化物品 $\Delta _{1}$ ）。

然后这个题只要再维护一下树上前缀和/差分，利用LCA合并卷积就做完了，并不是非常困难（确信）。