CSP-S/NOIP提高组真题题解总结

Star_F

6个月前更新

DP：

线性dp
- P1091 [NOIP2004 提高组] 合唱队形
  
  比较简单的一道题。求出以 $i$ 结尾的最长上升子序列和以 $i$ 为头的最长下降子序列，相加 $-1$ 即可。
- P1052 [NOIP2005 提高组] 过河
  
  如果不考虑 $L$ 的范围，那么就是一道简单的线性 dp 。
  
  但是 $L$ 很大，石头数量很少，所以每相邻两个石头的空隙一定很大。
  
  前置知识：P3951 [NOIP2017 提高组] 小凯的疑惑
  
  给定两个数 $p$ 和 $q$ ，他们最大不能凑出的数是 $(p-1)(q-1)-1$ 。所以中间空隙过多一定是可以被凑出来的，即可以压缩中间的空隙，然后线性 dp 即可。
- P1006 [NOIP2008 提高组] 传纸条
  
  求出 $2$ 条从 $(1,1)$ 到 $(n,m)$ 的路径。重复只算一次，求最大路径和。
  
  水题，不多赘述。记录 $dp_{A,B,C,D}$ 表示第一条走到 $(A,B)$ , 第二条走到 $(C,D)$ 。由于 $A+B = C+D$ ，可以记录他们的和，优化掉一维。
- P1541 [NOIP2010 提高组] 乌龟棋
  
  记录 $dp_{A,B,C,D}$ 表示用了 $A$ 个 $1$ 号卡片， $B$ 个 $2$ 号卡片， $C$ 个 $3$ 号卡片， $D$ 个 $4$ 号卡片。
  
  暴力转移即可 $F_{A,B,C,D}=\max (F_{A-1,B,C,D},F_{A,B-1,C,D},F_{A,B,C-1,D},F_{A,B,C,D-1})+cost_{A+2B+3C+4D}$
- P2679 [NOIP2015 提高组] 子串
  
  前缀和优化线性 dp。（推式子题）
  
  首先考虑如何DP，然后再考虑如何优化。
  
  状态表示：$f_{i, j, k}$表示只用 $S$ 的前 $i$ 个字母，选取了 $k$ 段，可以匹配 $T$ 的前 $j$ 个字母的方案数。
  
  状态计算： 将 $f_{i,j,k}$表示的所有方案分成两大类：
  - 不用 $S_i$，则方案数是 $f_{i-1,j,k}$；
  - 使用 $S_i$，则方案数是 $ \sum f_{i-t,j-t,k-1}$，满足 $S_{i-t+1}=T_{i-t+1}$，$t$ 从小到大枚举。
  时间复杂度是 $ \mathcal{O} (nm2k)$。
  
  我们发先 $f_{i,j,k}$ 的第二项和 $f_{i-1,j-1,k}$ 很像，可以考虑维护一个 $tmp_{i,j,k}$
  - $S_i=T_j$ , $tmp_{i,j,k}=tmp_{i-1,j-1,k}+f_{i-1,j-1,k-1}$ 。
  - $S_i \neq T_j$，$tmp_{i,j,k}=0$ 。
  （把式子展开可以发现 $tmp$ 的规律）。
  
  然后空间会爆，写滚动数组或者 01背包倒序枚举优化掉第一维即可。
- P5664 [CSP-S2019] Emiya 家今天的饭
  
  求解所有方案数
  
  $f_{i,j}$ 表示前 $i$ 种烹饪方式，做了 $j$ 道菜的方案数。
  - 状态转移：
    第 $i$ 种烹饪方式不做 $f_{i,j}+= f_{i – 1,j}$
  - 第 $i$ 种烹饪方法做 $1$ 道主要食材是 $k$ 的菜：$f_{i,j} += f_{i-1,j-1} * a_{i, k}$
  所有方案数量 $ A = \sum\limits_{j = 1}^{n}f_{n,j}$ 。
  
  求解不合法方案：
  
  $dp_{i,j}$ 表示前 $i$ 中烹饪方法，越界食材数 $ – $ 其他食材数为 $j$ 的方案数。
  
  状态转移：
  - 第 $i$ 种烹饪方法不选：$dp_{i,j} += dp_{i-1,j}$
  - 选越界食材 $c$：$dp_{i,j} += dp_{i-1,j-1} * a_{i, c}$
  - 选其他食材 $dp_{i,j} += dp_{i-1,j+1} * (s_i – a_{i, c})$
  所有方案数量： $ B = \sum dp_{n,j} (j > 0)$ 。
  
  $A-B$ 即可。
  
  时间复杂度 $\mathcal{O}(n ^ 2m)$ 。
  
  Tips： 做差有可能为负数，把所有状态加一个 $+n$ 的偏移量即可。
- 总结：
  
  对于线性 dp的问题，一般状态定义为 $f_{前\ i\ 个,满足 \ ….\ 状态}$，状态可能很多，所以可能有很多维。
  
  状态转移：考虑这个集合是由谁构成的，进行分类。比如分成选 $a$ 和不选 $a$ ……
  
  优化：如果状态过多，考虑滚动数组或者背包优化，转移中有求和，求最值等考虑用前缀和，单调队列优化。
区间dp
- P1040 [NOIP2003 提高组] 加分二叉树
  
  考虑到左边和右边独立，可以想到区间 dp 。
  
  设 $f_{i,j}$ 为区间 $[i\cdots j]$ 的最大价值。
  
  转移：$f_{i,j} = \max\limits_{k=i}^{j} f_{i,k-1} \times f_{k+1,j} + w_k $
  
  因为要求出具体方案，可以边算边求，也可以算完答案反推回去。
- P1063 [NOIP2006 提高组] 能量项链
  
  很模板的一道题。和上一题类似。
  
  设 $f_{i,j}$ 为区间 $[i\cdots j]$ 的最大价值。
  
  转移：$f_{i,j} = \max\limits_{k=i}^{j} f_{i,k} + f_{k,j} + w_i \times w_j \times w_k $。
  
  套路：枚举长度 $l$，枚举左端点 $i$，计算右端点 $j$，进行转移。
  
  Tips： 环上问题，破环为链，$2$ 倍长度即可。
- P1005 [NOIP2007 提高组] 矩阵取数游戏
  
  考虑到每一行是独立的，可以做 $m$ 次dp
  
  设 $f_{i,j}$ 表示将 $[i \cdots j]$ 这段数取完的最大值。
  
  转移
  - 取左端点：$f_{i+1,j} + w_i \times 2^{m-j+i}$
  - 取右端点：$f_{i,j+1} + w_j \times 2^{m-j+i}$
  取 $\max$ 即可。
  
  需要高精度，附代码：
```
#include <bits/stdc++.h>
using namespace std;
const int N = 85, M = 31;
int n, m,w[N][N],f[N][N][M],p[N][M],ans[M];
void mul(int a[], int b[], int c){
   static int tmp[M];
   for (int i = 0, t = 0; i < M; i ++ ){
       t += b[i] * c;
       tmp[i] = t % 10;
       t /= 10;
   }
   memcpy(a, tmp, M * 4);
}
void add(int a[], int b[], int c[]){
   static int tmp[M];
   for (int i = 0, t = 0; i < M; i ++ ){
       t += b[i] + c[i];
       tmp[i] = t % 10;
       t /= 10;
   }
   memcpy(a, tmp, M * 4);
}
int compare(int a[], int b[]){
   for (int i = M - 1; i >= 0; i -- )
       if (a[i] > b[i]) return 1;
       else if (a[i] < b[i]) return -1;
   return 0;
}
void print(int a[]){
   int k = M - 1;
   while (k && !ans[k]) k -- ;
   while (k >= 0) printf("%d", ans[k -- ]);
   puts("");
}
void work(int w[]){
   int a[M], b[M];
   for (int len = 1; len <= m; len ++ )
       for (int i = 0; i + len - 1 < m; i ++ ){
           int j = i + len - 1;
           int t = m - j + i;
           mul(a, p[t], w[i]), mul(b, p[t], w[j]);
           add(a, a, f[i + 1][j]);
           if (j) add(b, b, f[i][j - 1]);
           if (compare(a, b) > 0)
               memcpy(f[i][j], a, M * 4);
           else
               memcpy(f[i][j], b, M * 4);
       }
   add(ans, ans, f[0][m - 1]);
}
int main(){
   scanf("%d%d", &n, &m);
   for (int i = 0; i < n; i ++ )
       for (int j = 0; j < m; j ++ )
           scanf("%d", &w[i][j]);
   p[0][0] = 1;
   for (int i = 1; i <= m; i ++ )
       mul(p[i], p[i - 1], 2);
   for (int i = 0; i < n; i ++ )
       work(w[i]);
   print(ans);
   return 0;
}
```
- P7914 [CSP-S 2021] 括号序列
  
  状态定义：
  
  设 $dp_{i,j}$ 表示从 $i$ 到 $j$ 合法序列数量。
  
  但是不同的形态可能会有不同的转移。
  
  将两维的dp扩充为三维，第三维表示不同的形态种类，dp状态就变成了 $dp_{i,j,[0,5]}$。
  - $dp_{i,j,0}$: 形态如***...*的括号序列（即全部是*）。
  - $dp_{i,j,1}$: 形态如(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。
  - $dp_{i,j,2}$: 形态如(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。
  - $dp_{i,j,3}$: 形态如(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾，注意：第2种形态也属于这种形态）。
  - $dp_{i,j,4}$: 形态如***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。
  - $dp_{i,j,5}$: 形态如***(...)**(...)**的括号序列（即左边以*开头，右边以*结尾，注意：第1种形态也属于这种形态）。
  $\forall i$ 满足 $1\le i \le n$，有 $dp_{i,i-1,0}=1$ 。
  
  状态转移：
  - $dp_{l,r,0}$（直接特判）
  - $dp_{l,r,1}=(dp_{l+1,r-1,0}+dp_{l+1,r-1,2}+dp_{l+1,r-1,3}+dp_{l+1,r-1,4})*compare(l,r)$
    1. $compare(i,j)$ 表示第 $i$ 位与第 $j$ 位能否配对成括号，能则为 $1$，否则为 $0$。
    2. 加括号时，里面可以是全*，可以是有一边是*，也可以是两边都不是*，唯独不能两边都是*且中间有括号序列。
  - $dp_{l,r,2}=\sum\limits_{i=l}^{r-1} dp_{l,i,3}\times dp_{i+1,r,0}$
    1. 左边以括号序列开头且以括号序列结尾的是第3种，右边接一串*，是第0种。
  - $dp_{l,r,3}=\sum\limits_{i=l}^{r-1} (dp_{l,i,2}+dp_{l,i,3})\times dp_{i+1,r,1}+dp_{l,r,1}$
    1. 左边以括号序列开头，结尾随便，符合的有第2和第3种，右边接一个括号序列，是第1种。
    2. 记得加上直接一个括号序列的。
  - $dp_{l,r,4}=\sum\limits_{i=l}^{r-1} (dp_{l,i,4}+dp_{l,i,5})\times dp_{i+1,r,1}$
    1. 左边以*开头，结尾随便，符合的有第4和第5种，右边接一个括号序列，是第1种。
  - $dp_{l,r,5}=\sum\limits_{i=l}^{r-1} dp_{l,i,4}\times dp_{i+1,r,0}+dp_{l,r,0}$
    1. 左边以*开头，以括号序列结尾，符合的是第4种，右边接一串*，是第0种。
    2. 记得加上全是*的。
  答案： $dp_{1,n,3}$。
  
  时间复杂度： $\mathcal{O}(n^3)$ 。
- 总结：
  
  对于区间dp的问题，一般状态定义为 $f_{i,j}$ 表示区间 $[i,j]$ 的…（最大值最小值等）
  
  条件每个区间相互独立，互不影响。
  
  转移： 外层枚举区间长度，内层枚举起点 $i$，算出终点 $j$ ，再进行转移。
  
  Tips： 如果状态里只包含区间不够，则考虑加维。（例如）P7914 [CSP-S 2021] 括号序列
背包
- [NOIP2006 提高组] 金明的预算方案
  
  分组背包问题。
  
  将每个组件和任意个附件看成一组，每种情况相互独立，所以可以看成分组背包。
  
  先枚举组，在倒序枚举体积，然后枚举一个二进制状态，最后枚举二进制的每一位，算出 $v$ 和 $w$ 。
- P1941 [NOIP2014 提高组] 飞扬的小鸟
  
  模拟+背包+细节。
  
  设$f_{i,j}$ 表示横坐标为 $i$ ，纵座标为 $j$ 的最少点击次数。
  
  $ f_{i,j}=\min(f_{i-1,j-kX}+k,f_{i-1,j+Y})$
  
  时间复杂度： $\mathcal{O}(nm^2)$
  
  优化： 考虑「点击$k$次」和「点击$k-1$次」之间的联系。最优方案中，点击了$k$ 次到达纵坐标$j$ ，则如果点击 $k-1$ 次，会到达纵坐标$j-X$。
  
  类似完全背包的优化思路。
  
  $f_{i,j}=min(f_{i-1,j-X}+1,f_{i,j-X}+1)$ 。
  
  即，「只点击一次」和「从点击若干次到达的将要位置上再点击一次」。
  
  超过区域的状态应该设为 $+ \infty $，答案简单统计即可。
- P5020 [NOIP2018 提高组] 货币系统
  
  排序+完全背包。
  
  思路很好想，从小到大排序。
  
  大的一定是从小的凑出来的，所以类似筛法，进行 | 运算即可。
  
  代码：
```
  sort(a, a + n);
  memset(f, 0, sizeof f);
  f[0] = true;
  int res = n;
    for (int i = 0; i < n; i ++ ){
        if (f[a[i]]) res -- ;
        else
            for (int j = a[i]; j <= a[n - 1]; j ++ )
                f[j] |= f[j - a[i]];
    }
  cout<<res<<endl;
```
- 总结：
  
  熟记背包模板（01背包，完全背包，多重背包，分组背包）。
  
  背包优化： 倒序枚举体积优化掉第一维。
状压dp
树形dp
倍增优化dp

贪心：

搜索：

DFS
BFS
剪枝

数学：

数论：
组合数学

图论：

拓扑排序
树
LCA
最短路
二分图

数据结构：

堆
并查集
线段树
单调队列

基础算法：

枚举
模拟
字符串
排序
二分
位运算
构造
哈希
找规律

评分

欢迎为Ta评分

DP：

线性dp

P1091 [NOIP2004 提高组] 合唱队形

P1052 [NOIP2005 提高组] 过河

P1006 [NOIP2008 提高组] 传纸条

P1541 [NOIP2010 提高组] 乌龟棋

P2679 [NOIP2015 提高组] 子串

P5664 [CSP-S2019] Emiya 家今天的饭

总结：

区间dp

P1040 [NOIP2003 提高组] 加分二叉树

P1063 [NOIP2006 提高组] 能量项链

P1005 [NOIP2007 提高组] 矩阵取数游戏

P7914 [CSP-S 2021] 括号序列

总结：

背包

[NOIP2006 提高组] 金明的预算方案

P1941 [NOIP2014 提高组] 飞扬的小鸟

P5020 [NOIP2018 提高组] 货币系统

总结：

状压dp

树形dp

倍增优化dp

贪心：

搜索：

DFS

BFS

剪枝

数学：

数论：

组合数学

图论：

拓扑排序

树

LCA

最短路

二分图

数据结构：

堆

并查集

线段树

单调队列

基础算法：

枚举

模拟

字符串

排序

二分

位运算

构造

哈希

找规律