集训营笔记

本帖汇总了作者参加的集训营中精讲精练的几道题目的解法。

---

动态规划篇

例题1

原题：$\tt AtCoder\_Beginner\_Contest\,\,282\,\,G$ Similar Permutation
洛谷传送门
$\tt AtCoder$传送门

题意：对于两个排列 $A$ 和 $B$，定义二者的相似度为比大小结果相同的相邻位置对数量，求所有相似度为 $k$ 的排列数量，关于大质数 $P$ 取模（$n\leq100$）

思路：对于排列而言，基本按照下标或值考虑。

基本想法是：设 $dp[i][j][k][l]$ 表示考虑前 $i$ 个数，$A$ 序列中第 $i$ 位为 $j$，$B$ 序列中第 $i$ 位为 $k$，整体相似度为 $l$

但是显然这样是不够的，因为排列需要保证每个数都出现恰好 $1$ 次，还需要维护第 $i$ 个数出现过几次，会导致时间和空间都爆掉。

因而，考虑转换 $dp[i][j][k][l]$ 的含义，令其表示 已有的 $A$ 序列中第 $i$ 位排名为 $j$，已有的 $B$ 序列中第 $i$ 位排名为 $k$，整体相似度为 $l$

注意：这里的排名是 相对的，不是绝对的，因而初始化的时候只能够是 $dp[1][1][1][0]=1$，因为只有一个数的时候排名肯定是第一

接下来考虑转移。

第一种情况：如果当前位置对会产生贡献：

1.1. 如果都小于当前位：

$\displaystyle dp[i][j][k][l]=\sum_{a=1}^{j-1}\sum_{b=1}^{k-1}dp[i-1][a][b][l-1]$

1.2. 如果都大于当前位：

$\displaystyle dp[i][j][k][l]=\sum_{a=j}^{n}\sum_{b=k}^{n}dp[i-1][a][b][l-1]$

第二种情况：如果当前位置对不产生贡献：

2.1. 如果 $A$ 小 $B$ 大：

$\displaystyle dp[i][j][k][l]=\sum_{a=1}^{j-1}\sum_{b=k}^{n}dp[i-1][a][b][l]$

2.2. 如果 $A$ 大 $B$ 小：

$\displaystyle dp[i][j][k][l]=\sum_{a=j}^{n}\sum_{b=1}^{k-1}dp[i-1][a][b][l]$

由于是相对排名，因而下标应当从 $n$ 开始枚举，就像超过第二名你就是第二名，原本第二名变成第三名了一样。

朴素の代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
int n,k,MOD;
int dp[N][N][N][N];
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>MOD;
    dp[1][1][1][0]=1;
    for(int i=2;i<=n;i++){
        for(int l=0;l<n;l++){
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    //贡献<<
                    if(l){
                        for(int a=1;a<j;a++){
                            for(int b=1;b<k;b++){
                                dp[i][j][k][l]+=dp[i-1][a][b][l-1];
                                dp[i][j][k][l]%=MOD;
                            }
                        }
                    }
                    //贡献>>
                    if(l){
                        for(int a=j;a<=i;a++){
                            for(int b=k;b<=i;b++){
                                dp[i][j][k][l]+=dp[i-1][a][b][l-1];
                                dp[i][j][k][l]%=MOD;
                            }
                        }
                    }
                    //不贡献<>
                    for(int a=1;a<j;a++){
                        for(int b=k;b<=i;b++){
                            dp[i][j][k][l]+=dp[i-1][a][b][l];
                            dp[i][j][k][l]%=MOD;
                        }
                    }
                    //不贡献><
                    for(int a=j;a<=i;a++){
                        for(int b=1;b<k;b++){
                            dp[i][j][k][l]+=dp[i-1][a][b][l];
                            dp[i][j][k][l]%=MOD;
                        }
                    }
                }
            }
        }
    }
    for(int a=1;a<=n;a++){
        for(int b=1;b<=n;b++){
            ans+=dp[n][a][b][k];
            ans%=MOD;
        }
    }
    cout<<ans;
    return 0;
}

时间复杂度：$O(n^6)$，空间复杂度：$O(n^4)$

因而需要优化时间，由于这里一直是对于一段进行求和，可以使用二维前缀和优化 $\tt{DP}$ ，降低时间复杂度，可过

注意：这里由于需要不同维度的 $l$，因而如果你前缀和只开二维需要两次初始化，浪费一定时间，如果开三维或者四维则可以避免这个问题，但会浪费空间。实测两种方式都可以过

优化后の代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
int n,k,MOD;
int dp[N][N][N][N],sum[N][N];
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>MOD;
    dp[1][1][1][0]=1;
    for(int i=2;i<=n;i++){
        for(int l=0;l<n;l++){
            //二维前缀和维护贡献的情况
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    sum[j][k]=sum[j-1][k]+sum[j][k-1]-sum[j-1][k-1]+dp[i-1][j][k][l-1]+MOD;
                    sum[j][k]%=MOD;
                }
            }
            //转移贡献的情况
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    //贡献<<
                    if(l){
                        dp[i][j][k][l]+=(sum[j-1][k-1]-sum[j-1][0]-sum[0][k-1]+sum[0][0])%MOD+MOD,
                        dp[i][j][k][l]%=MOD;
                    }
                    //贡献>>
                    if(l){
                        dp[i][j][k][l]+=(sum[i][i]-sum[i][k-1]-sum[j-1][i]+sum[j-1][k-1])%MOD+MOD,
                        dp[i][j][k][l]%=MOD;
                    }
                }
            }
            //二维前缀和维护不贡献的情况
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    sum[j][k]=sum[j-1][k]+sum[j][k-1]-sum[j-1][k-1]+dp[i-1][j][k][l]+MOD;
                    sum[j][k]%=MOD;
                }
            }
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    //不贡献<>
                    dp[i][j][k][l]+=(sum[j-1][i]-sum[j-1][k-1]-sum[0][i]+sum[0][k-1])%MOD+MOD,
                    dp[i][j][k][l]%=MOD;
                    //不贡献><
                    dp[i][j][k][l]+=(sum[i][k-1]-sum[j-1][k-1]-sum[i][0]+sum[j-1][0])%MOD+MOD,
                    dp[i][j][k][l]%=MOD;
                }
            }
        }
    }
    for(int a=1;a<=n;a++)for(int b=1;b<=n;b++){
        ans+=dp[n][a][b][k];
        ans%=MOD;
    }
    cout<<ans;
    return 0;
}

时间复杂度：$O(n^4)$，空间复杂度：$O(n^4)$

---

例题2

原题：$\tt JOISC\,\,2014$ たのしい家庭菜園
洛谷传送门
$\tt AtCoder$传送门

题意：有一个长度为 $n$ 的序列 $\{a_n\}$，只能进行邻项交换操作，让序列变为单峰序列，求最小交换次数（$n\leq3\times10^5$）

思路：如果是要变成排序后的序列，即单调递增序列的话，那么会很方便

由于一次交换相当于去掉一组逆序对，因此，如果需要让序列变得有序，那么最小交换次数就是逆序对数量。

现在需要变成单峰序列，即 $\exist i,s.t.(\forall j<i,a_j\leq a_{j+1})\land(\forall j>i,a_j\leq a_{j-1})$，

相当于，对于 $1\leq j\leq i$ 的 $a_j$ 构成的序列从前往后看单调递增，且 $i\leq k\leq n$ 的 $a_k$ 构成的序列从后往前看单调递增，

问题转化为，你把任意的 $a_i$ 放在前面交换的次数少，还是放在后面交换的次数少

即统计前后逆序对的数量那个更少，

利用树状数组统计逆序对，将所有结果累加即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int n,a[N],c1[N],c2[N],lsh[N];
int ans;
int lowbit(int n){ //lowbit函数
    return n&-n;
}
void add(int x,int id,int(&c)[N]){ //添加-树状数组
    for(;id<=n;id+=lowbit(id))c[id]+=x;
}
int get(int id,int(&c)[N]){ //获取-树状数组
    int res=0;
    for(;id;id-=lowbit(id))res+=c[id];
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lsh[i]=a[i];
    }
    //离散化
    sort(lsh+1,lsh+n+1);
    int len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
        add(1,a[i],c2); //全部加入倒序的树状数组
    }
    for(int i=1;i<=n;i++){
        add(1,a[i],c1); //加入正序的树状数组
        ans+=min(get(n,c1)-get(a[i],c1),get(n,c2)-get(a[i],c2)); //统计逆序对
        add(-1,a[i],c2); //从倒序的树状数组中删去
    }
    cout<<ans;
    return 0;
}

上面之所以用 $a[i]$ 作为get函数的参数，是因为去重的关系

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

---

例题3

原题：$\tt P4766\,\,[CERC2014]$ Outer space invaders
洛谷传送门

题意：有 $n$ 个外星人，第 $i$ 个外星人出现时间段为 $a[i]\sim b[i]$，距离为 $d[i]$，清除距离 $\leq R$ 的所有外星人费用为 $R$，求将所有外星人都清除的最小费用

思路：朴素区间 $\tt{DP}$

先将时间序列 $\{a_i\}$ 和 $\{b_i\}$ 进行离散化，然后设 $dp[L][R]$ 表示干掉时间 $a[i]$ 和 $b[i]$ 都在区间 $[L,R]$ 内所有敌人所需要花费的最少能量

初始化就是时间 $[i,i]$ 内每个时间点都是花费 $0$

考虑转移：枚举断点 $k$，假设所有在时间区间 $[L,k-1]$ 和 $[k+1,R]$ 内的敌人都已经被清除，只需要再清除 $\forall i,s.t.L\leq a[i]\leq k\leq b[i]\leq R$，然后加上其中某个敌人的 $d_i$，即 $\displaystyle dp[L][R]=\min_{k=L+1}^{R-1}dp[L][k-1]+dp[k+1][R]+d[x]$

那么，具体是哪一个敌人的 $d_i$？应当清除最大的 $d_i$，因为如果清除的不是最大的 $d_i$，你还需要花一定的费用来清除它，会造成前面的费用浪费。因而，只需要找到 $d_i$ 最大的敌人，保证其满足 $L\leq a[i]\leq k\leq b[i]\leq R$，从而进一步优化 $k$ 的范围到 $[a[i],b[i]]$

最终的答案就是清除所有的敌人。设 $m$ 为离散化之后所有的时间节点个数，故需要清除所有 $a[i]$ 和 $b[i]$ 在 $[1,m]$ 内的敌人，因此答案为 $dp[1][m]$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=303;
int n;
int a[N],b[N],d[N];
int dp[N<<1][N<<1];
void solve(){
    vector<int>alls;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>d[i];
        alls.push_back(a[i]);
        alls.push_back(b[i]);
    }
    //离散化
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(alls.begin(),alls.end(),a[i])-alls.begin()+1;
        b[i]=lower_bound(alls.begin(),alls.end(),b[i])-alls.begin()+1;
    }
    //区间dp
    memset(dp,0x3f,sizeof(dp));
    int m=alls.size();
    for(int i=1;i<=m;i++)dp[i][i]=0;
    for(int len=2;len<=m;len++){
        for(int L=1,R=len;R<=m;L++,R++){
            int x=0;
            for(int i=1;i<=n;i++)if(a[i]>=L&&b[i]<=R&&(!x||d[i]>d[x]))x=i;
            if(!x){
                dp[L][R]=0;
                continue;
            }
            for(int k=a[x];k<=b[x];k++){
                dp[L][R]=min(dp[L][R],dp[L][k-1]+dp[k+1][R]+d[x]);
            }
        }
    }
    cout<<dp[1][m]<<"\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int _;
    cin>>_;
    while(_--)solve();
	return 0;
}

时间复杂度：$O(n^3)$

---

最优化篇

例题1

原题：$\tt CodeForces\,\,632\,\,C$ The Smallest String Concatenation
洛谷传送门
$\tt CodeForces$传送门

题意：$n$ 个字符串，拼接使得最终字符串字典序最小

思路：假设一个最优解是 $s_1s_2\cdots s_n$，考虑微调，使得新的解比原来的解更大，不优

使用类似于排序算法的操作，交换相邻位置，或者把元素直接拉到开头或结尾

此处考虑交换相邻两个串的位置。

例如，交换 $s_1$ 和 $s_2$，要求 $s_1s_2<s_2s_1$，那么推广到全局，只需要重载 $\leq$ 符号即可，记作 $s_1\preceq s_2$

定义 $s_1\preceq s_2$，那么可知其传递性：若 $s_1\preceq s_2,s_2\preceq s_3$，则 $s_1\preceq s_3$

也可从其定义知其反对称性：$s_1\preceq s_2$，则 $s_2\preceq s_1$ 不成立

因而总字典序最小的是按照 $\preceq$ 的方式排序，然后拼接

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;
int n;
string s[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1, s+n+1, [](const string&a,const string&b){
        return a+b<b+a;
    });
    for(int i=1;i<=n;i++)cout<<s[i];
	return 0;
}

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

---

例题2

原题：$\tt AtCoder\_Beginner\_Contest\,\,225\,\,F$ String Cards
洛谷传送门
$\tt AtCoder$传送门

题意：$n$ 张卡片，第 $i$ 张字符串 $s_i$，恰选出 $K$ 张，任意顺序连接，使得最终字典序最小（$n,K\leq50$，$s_i$ 仅由小写字母构成）

思路：动态规划即可

一、状态表示：设 $dp[i][j]$ 表示前 $i$ 张选出 $j$ 个的方案数，

二、转移方程：

如果选：$dp[i][j]=\min(dp[i][j],dp[i-1][j-1]+s[i])$

如果不选：$dp[i][j]=\min(dp[i][j],dp[i-1][j])$

三、初始化：初始化为极大值（例：char(127)）

四、答案：$dp[n][K]$

为了能够保证 $\tt{DP}$ 的最优化，需要将 $s_i$ 提前按照 $s_1\preceq s_2$ 的方式排序

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
int n,k;
string s[N];
string dp[N][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s****+n+1,[](const string&a,const string&b){
        return a+b<b+a;
    }); //排序
    for(int i=0;i<=n;i++)for(int j=1;j<=k;j++)dp[i][j]+=char(127); //初始化为极大值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+s[i]); //选
            dp[i][j]=min(dp[i][j],dp[i-1][j]); //不选
        }
    }
    cout<<dp[n][k]; //答案
	return 0;
}

时间复杂度：$O(n\cdot k\cdot|s|)$

但是这种做法有问题：若 $s_1\preceq s_2$，它是从前往后比较，即对于前缀相同有效，对于后缀相同不一定有效，即不一定有 $s_1+s_3<s_2+s_3$，但是一定有 $s_3+s_1<s_3+s_2$

因而需要 从后往前 $\tt{DP}$

一、状态表示：设 $dp[i][j]$ 表示 后 $i$ 张选出 $j$ 个的方案数，

二、转移方程：

如果选：$dp[i][j]=\min(dp[i][j],s[-i]+dp[i-1][j-1])$

如果不选：$dp[i][j]=\min(dp[i][j],dp[i-1][j])$

三、初始化：初始化为极大值（例：char(127)）

四、答案：$dp[n][K]$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
int n,k;
string s[N];
string dp[N][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s****+n+1,[](const string&a,const string&b){
        return a+b<b+a;
    }); //排序
    for(int i=0;i<=n;i++)for(int j=1;j<=k;j++)dp[i][j]+=char(127); //初始化为极大值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=min(dp[i][j],s[n-i+1]+dp[i-1][j-1]); //选【从后往前，加在前面】
            dp[i][j]=min(dp[i][j],dp[i-1][j]); //不选
        }
    }
    cout<<dp[n][k]; //答案
	return 0;
}

时间复杂度：$O(n\cdot k\cdot|s|)$

---

例题3

原题：$\tt P11628\,\,[WC2025]$ 猫粮
洛谷传送门

题意：给 $n$ 只猫分配猫粮，优质猫粮所有没吃饱的猫都会来抢，普通猫粮则不会，需要让所有猫都达到饱腹值 $m$，问能否得到这样的分配方案

思路：显然最坏的情况是每只猫都抢到一袋优质猫粮，因而希望能够让普通猫粮和优质猫粮一对一匹配成 $m$，这是最好的。

当然，也有一种特殊情况，让一只猫全吃普通猫粮吃饱，其他猫能抢到优质猫粮那就给它们配一袋普通猫粮吃饱。然后，最后一只猫吃剩下的两袋优质猫粮吃饱。这也是一种合法方案。

我在做这道题的时候还想到一种特殊情况：一只猫吃一袋优质猫粮和两袋普通猫粮吃饱，另一只猫则吃一袋优质猫粮，这样能否可行？当然，如果有任何一只猫吃了不止两袋猫粮，那么必然有至少一只猫只吃一袋猫粮，这袋猫粮的饱腹值一定是 $m$，但是因为 $1\leq a_i,b_i<m$，与题设矛盾，所以无需考虑这种情况。

自信满满地把这个代码写完之后一看，得了 $65$ 分，后来明白了如果剩下一堆饱腹值相等的优质猫粮也是可以的，那么这个时候谁抢到哪一袋优质猫粮就无所谓了，且这个时候剩下的优质猫粮必然是 $\cfrac{m}{2}$。

因而，基本思路就是，用普通猫粮匹配优质猫粮。如果匹配不到，那就普通猫粮匹配普通猫粮。再匹配不到就无解。

对于优质猫粮而言，要么最终剩余的饱腹值只能有一种，要么最终剩下的袋数恰好是两袋，否则也无解。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=40010,M=1e5+10;
int n,m,a[N],b[N];
int buca[M],bucb[M]; //用桶来存储猫粮的种类
bool solve(){
    memset(buca,0,sizeof(buca));
    memset(bucb,0,sizeof(bucb));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        buca[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        bucb[b[i]]++;
    }
    for(int i=1;i<=n;i++){ //先匹配普通猫粮
        if(!bucb[b[i]])continue; //已经被匹配掉了
        if(buca[m-b[i]])buca[m-b[i]]--,bucb[b[i]]--; //匹配优质猫粮
        else if(bucb[m-b[i]]&&b[i]!=m-b[i])bucb[b[i]]--,bucb[m-b[i]]--; //匹配普通猫粮
        else if(b[i]==m-b[i]&&bucb[b[i]]>1)bucb[b[i]]-=2; //匹配到自身的值
        else return 0; //无法匹配
    }
    int uniq=0,cnt=0; //统计为被匹配的优质猫粮种类数和袋数
    for(int i=1;i<=m;i++)if(buca[a[i]])uniq++,cnt+=buca[a[i]]; //统计
    if(uniq>1&&cnt>2)return 0;
    return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int _;
    cin>>_;
    while(_--)cout<<(solve()?"Yes\n":"No\n");
	return 0;
}

时间复杂度：$O(n+m)$，多组数据忽略不计

这道题如果没哟那个猫粮的限制的话会更难，因而有了限制之后刚到绿题水准，或许还不到，CSP-S或NOIP签到题的感觉，就是比较考验细节

---

例题4

原题：$\tt AtCoder\_Beginner\_Contest\,\,018\,\,C$ Coins
洛谷传送门
$\tt AtCoder$传送门

题意：给定 $x+y+z$ 个三元组 $(a_i,b_i,c_i)$，选择 $x$ 个 $a_i$，$y$ 个 $b_i$，$z$ 个 $c_i$，使得选择的数的和最大

思路：本题的弱化版本是二元组 $(a_i,b_i)$，假设全部选择 $a_i$，然后考虑选择 $b_i$ 带来的额外贡献，按照差值排序。

现在是三元组，也可以这样做，假设全部选择 $a_i$，那么问题转化成在此条件下选择 $y$ 个 $b_i$ 和 $z$ 个 $c_i$ 能带来的最大的额外贡献。

一道标准的二位偏序贪心题。选择 $b_i$ 的额外贡献是 $db_i=b_i-a_i$，选择 $c_i$ 的额外贡献是 $dc_i=c_i-a_i$，因而每个三元组可以简化为 $(db_i,dc_i)$ 形式的二元组进行描述

采用邻项交换法，假设对于 $(db_1,dc_1)$ 和 $(db_2,dc_2)$ 二者而言，选择 $db_1$ 和 $dc_2$ 会更优，即 $db_1+dc_2>db_2+dc_1$

移项，得 $db_1-dc_1>db_2-dc_2$

因而，按照 $db_i-dc_i$ 进行降序排序，前面一部分选择 $db_i$ 的贡献，后面一部分选择 $dc_i$ 的贡献，最后求出贡献的最大值即可。

考虑用堆维护前缀 $db_i$ 的贡献前 $y$ 大，以及后缀 $dc_i$ 的贡献前 $z$ 大，进行预处理，然后从前往后枚举分界线扫一遍，把前半段和后半段的贡献加起来求最大值即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long //不开long long见祖宗
const int N=1e5+10;
struct node{
    int a,b,c;
    int id;
    int db,dc;
    int d;
}a[N];
int x,y,z,sum,n;
int pre[N],suf[N];
priority_queue<int,vector<int>,greater<int>>p,s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y>>z;
    n=x+y+z;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b>>a[i].c;
        sum+=a[i].a; //假设全选a
        a[i].db=a[i].b-a[i].a; //选b的额外贡献
        a[i].dc=a[i].c-a[i].a; //选c的额外贡献
        a[i].d=a[i].db-a[i].dc; //额外贡献之差
    }
    sort(a+1,a+n+1,[](const node&a,const node&b){ //排序
        return a.d>b.d;
    });
    for(int i=1;i<=n;i++){ //预处理前缀
        pre[i]=pre[i-1]+a[i].db;
        p.push(a[i].db);
        if(p.size()>y){
            pre[i]-=p.top();
            p.pop();
        }
    }
    for(int i=n;i;i--){ //预处理后缀
        suf[i]=suf[i+1]+a[i].dc;
        s.push(a[i].dc);
        if(s.size()>z){
            suf[i]-=s.top();
            s.pop();
        }
    }
    int ans=-9223372036854775807; //赋为极小值，因为额外贡献有可能为负
    for(int i=y;i<=n-z;i++)ans=max(ans,pre[i]+suf[i+1]);
    //注意这边错位相加，否则i位置的贡献可能会重复
    ans+=sum;
    cout<<ans;
    return 0;
}

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

这道题应该是很久以前的一道好题了，可以用来练习二位偏序上的最优调整策略，洛谷上评价是紫题，但放在现在肯定不到这个难度。

它唯一的难点在于细节。我就在细节上犯了两个错误，一个是不开 long long 见了祖宗，另一个是 ans 没有赋极小值，因而吃了两发罚时。

不过我一开始把题目看错为“可以从每个人那里拿最多两种硬币”，因而卡了好久，实则一点不难。我不知道如果改成我这个限制之后会简单一点还是难许多。

---

组合计数篇

例题1

原题：$\tt P1450\,\,[HAOI2008]$ 硬币购物
洛谷传送门

题意：给你 $c_0,c_1,c_2,c_3$ 四种数，$n$ 次询问，每次规定四种数分别有 $d_0,d_1,d_2,d_3$ 个，问有多少种选数方案使得选出来的数的和恰好为 $s$

思路：不难发现这是一个动态规划题。

作者一开始思路是设 $dp[i][a][b][c][d]$ 表示用 $a$ 个 $c_0$，$b$ 个 $c_1$，$c$ 个 $c_2$，$d$ 个 $c_3$ 凑出 $i$ 的方案数，然后一看数据范围吓哭了：$c_i,d_i,s\leq10^5$，时空复杂度都炸了

后来发现这是一道多重背包题，价格为 $c_i$ 的物品有 $d_i$ 个的限制，凑出总共为 $s$ 的价格，然后让你求方案，大致的转移式为 $dp[j]+=dp[j-c[i]]$

由于这个是组合计数专题，老师讲了容斥，因而考虑如何用容斥优化。

上文提到，$d_i$ 是对于 $c_i$ 的限制，不妨去掉限制，则变为完全背包求方案数，然后考虑超过限制的情况，即 $c_i$ 用了超过了 $d_i$ 个，然后就可以容斥求方案数了。

别忘了初始化 $dp[0]=1$！

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int c[4],d[4],a[4],q,s;
int dp[N];
void init(){
    //完全背包
    dp[0]=1; //初始化勿忘
    for(int i=0;i<4;i++)
        for(int j=c[i];j<N;j++)
            dp[j]+=dp[j-c[i]];
}
int solve(){
    cin>>d[0]>>d[1]>>d[2]>>d[3]>>s;
    for(int i=0;i<4;i++)a[i]=c[i]*(d[i]+1);
    //容斥
    int ans=dp[s]; //没有限制的情况
    //枚举只有第i个超过了限制
    for(int i=0;i<4;i++)
        if(s>=a[i])
            ans-=dp[s-a[i]];
    //枚举第i和第j个超过了限制
    for(int i=0;i<4;i++)
        for(int j=i+1;j<4;j++)
            if(s>=a[i]+a[j])
                ans+=dp[s-a[i]-a[j]];
    //提前统计全部超过限制的金额
    int all=0;
    for(int i=0;i<4;i++)all+=a[i];
    //枚举只有第i个没有超过限制
    for(int i=0;i<4;i++)
        if(s>=all-a[i])
            ans-=dp[s-all+a[i]];
    //全部超过限制
    if(s>=all)ans+=dp[s-all];
    //打表可能会更好理解，但这样可能更省力一些
    return ans;
}
signed main(){
    cin>>c[0]>>c[1]>>c[2]>>c[3]>>q;
    init();
    while(q--)cout<<solve()<<"\n";
    return 0;
}

时间复杂度：$O(s_{max})$ 预处理+$O(q)$ 查询

---

例题2

原题：$\tt CF559C$ Gerald and Giant Chess
洛谷传送门
$\tt CodeForces$传送门

题意：一个人从网格左上角 $(1,1)$ 走到右下角 $(h,w)$，只能往下或往右走，且不能经过黑色格子，问有多少种走法。

思路：考虑直接设 $dp[i][j]$ 表示走到 $(i,j)$ 的方案数，如果是黑色格子那就是 $0$，否则就是 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$，但是由于数据范围过大，$h,w\leq10^5$，空间炸了。

考虑用总方案数减去经过黑格的方案数，设 $dp[i]$ 表示走到第 $i$ 个黑格且不经过其它黑格的方案数，那么可以用容斥做，先用组合数求出所有走到第 $i$ 个黑格的方案数，再减去走到其它黑格之后再走到当前黑格的方案数即可。

由于要计算其它黑格到当前黑格的方案数，因而这里的“其它黑格”必须要在当前黑格的左上角，按照坐标先进行排序再 $\tt DP$。

过程中，由于起始位置是 $(1,1)$，因而走到第 $i$ 个黑格 $(x_i,y_i)$ 的方案数是 $C_{x_i+y_i-2}^{y_i-1}$

假设一个在第 $i$ 个黑格左上角的黑格 $j$ 坐标是 $(x_j,y_j)$，那么从 $j$ 走到 $i$ 的方案数为 $C_{x_i+y_i-x_j-y_j}^{y_i-y_j}$

因而，整个转移方程式为 $\displaystyle dp[i]=C_{x_i+y_i-2}^{y_i-1}-\sum_{1\leq j\leq i,x_j\leq x_i,y_j\leq y_i}dp[j]\times C_{x_i+y_i-x_j-y_j}^{y_i-y_j}$

如果把终点 $(h,w)$ 也理解成一个黑格，那么最终的答案就是 $dp[n+1]$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,MOD=1e9+7;
//快速幂求逆元
int qpow(int a,int n=MOD-2){
    int s=1;
    for(;n;n>>=1,a=a*a%MOD)if(n&1)s=s*a%MOD;
    return s;
}
//预处理阶乘和阶乘逆元
int fact[N]={1},inv[N]={1};
void init(int n=N-10){
    //正序递推处理阶乘
    for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i%MOD;
    //处理最后一个阶乘的逆元
    inv[n]=qpow(fact[n]);
    //倒序递推处理逆元
    for(int i=n;i-1;i--)inv[i-1]=inv[i]*i%MOD;
}
//组合数计算
int C(int n,int m){
    return fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int h,w,n;
struct node{
    int x,y;
}a[N];
int dp[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    init(h+w); //初始化
    //排序，从上到下，从左到右（动态规划基础）
    sort(a+1,a+n+1,[](const node&a,const node&b){
        if(a.x!=b.x)return a.x<b.x;
        return a.y<b.y;
    });
    //终点理解为黑格，一同进行dp
    a[n+1]={h,w};
    //递推求解
    for(int i=1;i<=n+1;i++){
        dp[i]=C(a[i].x+a[i].y-2,a[i].y-1);
        for(int j=1;j<i;j++){
            //容斥
            if(a[j].x<=a[i].x&&a[j].y<=a[i].y){ //判断是否在左上角
                dp[i]-=dp[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].y-a[j].y)%MOD;
                dp[i]=(dp[i]+MOD)%MOD;
            }
        }
    }
    cout<<dp[n+1];
    return 0;
}

时间复杂度：$O(n^2)$

---

杂题专栏篇

例题1

原题：$\tt P2827\,\,[NOIP2016S]$ 蚯蚓
洛谷传送门

题意：$n$ 个数，每个时刻选择最大的数 $x_i$ 分成 $\lfloor px_i\rfloor$ 和 $x_i-\lfloor px_i\rfloor$ 两个数，其余数 $+q$，每过 $t$ 个时刻输出被选中的数。

过了 $m$ 个时刻之后，输出所有数中排名为 $t$ 的倍数的数。

思路：一开始被这道题吓到了，但是仔细考虑一下，可以把所有数 $+q$ 变成分裂的两个数 $-q$，统一计算偏移量即可。

这样就变成了每次选择最大数的模拟操作，可以用堆来动态获取最大数

暴力代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q,u,v,t,a;
priority_queue<int>heap;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;i++){
        cin>>a;
        heap.push(a);
    }
    //过程
    for(int i=1,time=0;i<=m;i++){
        int tp=heap.top();
        tp+=q*(i-1); //加上偏移量
        if(++time==t){ //输出
            time=0;
            cout<<tp<<" ";
        }
        heap.pop();
        int left=tp*u/v; //计算偏移后的左半部分
        int right=tp-left; //计算偏移后的右半部分
        left-=q*i; //去除偏移量
        right-=q*i; //去除偏移量
        heap.push(left);
        heap.push(right);
    }
    cout<<"\n";
    //结果
    int rank=0;
    while(heap.size()){
        int tp=heap.top();
        tp+=q*m; //加上偏移量
        if(++rank==t){  //输出
            cout<<tp<<" ";
            rank=0;
        }
        heap.pop();
    }
    return 0;
}

时间复杂度：$>O(m\log{n})$

因而容易超时，实测 $85$ 分。考虑优化，可以从单调性入手。

首先考虑没有偏移量的情况，即 $q=0$，设两条蚯蚓长度分别是 $x_1,x_2$，不妨设 $x_1\geq x_2$

因而，在分成两部分之后，有 $px_1\geq px_2$，从而得到 $\lfloor px_1\rfloor\geq\lfloor px_2\rfloor$

说明左半部分的单调性同原来的单调性。那么如何证明右半部分的单调性也相同呢？

目标是证明 $x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloor$

由于题目交代了 $0<p<1$，因而有 $x_1-x_2\geq px_1-px_2$，其实等号取不到，但这些细节无所谓。

移项：$x_1-x_2+px_2\geq px_1$，这是为了构造单独的 $px_i$ 的向下取整。

两边同时取整：$\lfloor x_1-x_2+px_2\rfloor\geq\lfloor px_1\rfloor$

由于 $x_1,x_2\in\Z$，因而可以直接取出取整符号：$x_1-x_2+\lfloor px_2\rfloor\geq\lfloor px_1\rfloor$

最后移项：$x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloor$

没有偏移量的情况证明完毕，现在考虑有偏移量的情况。

有了偏移量之后，目标是证明 $\lfloor px_1\rfloor+q\geq\lfloor p(x_2+q)\rfloor$ 以及 $x_1-\lfloor px_1\rfloor+q\geq x_2+q-\lfloor p(x_2+q)\rfloor$

先来看第一个式子，由于 $q$ 是整数，放入取整符号对结果没有影响，因而有：

$\lfloor px_1\rfloor+q=\lfloor px_1+q\rfloor\geq\lfloor px_2+q\rfloor\geq\lfloor px_2+pq\rfloor=\lfloor p(x_2+q)\rfloor$

再来看第二个，即证：$x_1-\lfloor px_1\rfloor\geq x_2-\lfloor p(x_2+q)\rfloor$

根据上面没有偏移量的情况，知 $x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloor$

现在变成 $\lfloor p(x_2+q)\rfloor$，减得东西不可能变少，因而答案不可能变大，即：

$x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloor\geq x_2-\lfloor p(x_2+q)\rfloor$

因而得证。

综上，我们证明了蚯蚓被切断之后的单调性，因而可以把优先队列替换成普通的队列，切断后左右两段依然满足单调性。

维护三个队列，分别存储原来的蚯蚓、切断后左半部分蚯蚓、右半部分蚯蚓即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,q,u,v,t;
int a[N];
queue<int>None,Left,Right;
int get_top(){ //获取最大值，并弹出队列
    int ans=-9223372036854775807,c=0;
    if(None.size()&&None.front()>ans)ans=None.front(),c=1;
    if(Left.size()&&Left.front()>ans)ans=Left.front(),c=2;
    if(Right.size()&&Right.front()>ans)ans=Right.front(),c=3;
    if(c==1)None.pop();
    else if(c==2)Left.pop();
    else Right.pop();
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1,greater<int>()); //先排序，满足单调性
    for(int i=1;i<=n;i++)None.push(a[i]);
    //过程
    for(int i=1,time=0;i<=m;i++){
        int tp=get_top();
        tp+=q*(i-1);
        if(++time==t){
            time=0;
            cout<<tp<<" ";
        }
        int left=tp*u/v;
        int right=tp-left;
        left-=q*i;
        right-=q*i;
        Left.push(left);
        Right.push(right);
    }
    cout<<"\n";
    //结果
    int rank=0;
    while(None.size()+Left.size()+Right.size()){
        int tp=get_top();
        tp+=q*m;
        if(++rank==t){
            cout<<tp<<" ";
            rank=0;
        }
    }
    return 0;
}

时间复杂度：$O(m)$

---

例题2

原题：$\tt P10998$ Tuple+
洛谷传送门

题意：给定 $m$ 个三元组 $(u,v,w)$ 保证 $u<v<w$，求有多少个四元组 $(u,v,w,t)$ 满足 $u<v<w<t$

思路：设 $S(u,v)$ 表示能够和 $(u,v)$ 形成三元组的 $w$ 构成的集合，

则对于每个三元组 $(u,v,w)$ 统计 $S(u,v)\bigcap S(v,w)\bigcap S(u,w)$ 即可

代码:

//Fsy.Yanicco
//P10998
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int n,m,u,v,w,ans;
map<pair<int,int>,set<int>>mp;
vector<array<int,3>>q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        mp[{u,v}].insert(w);
        q.push_back({u,v,w});
    }
    for(const auto&[u,v,w]:q){
        set<int>*a=&mp[{u,v}],*b=&mp[{u,w}],*c=&mp[{v,w}];
        set<int>*p=a;
        if(p->size()>b->size())p=b;
        if(p->size()>c->size())p=c;
        for(const auto&i:*p)
            if(a->find(i)!=a->end()&&b->find(i)!=b->end()&&c->find(i)!=c->end())
                ans++;
    }
    cout<<ans;
    return 0;
}

时间复杂度：$O(m^\frac{4}{3})$