A题丢瓶盖（计蒜客T1878）
复习一下二分查找吧，这题和我们以前做过的安排牛的位置那题一摸一样吧。
用二分查找不断去查找一个最优间距。从第一个点开始按这个间距找下一个点，如果找出的点的总数大于了题目的要求（B），那么让间距变大，如果小于了让间距变小。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
int f[N];
int a , b;

bool check(int mid)
{
    int sum = 1 , uppoin = 0;//上一个点
    for(int i = 1 ; i < a ; i++)
    {
        if(f[i] - f[uppoin] >= mid)
        {
            sum ++;
            uppoin = i;
        }
    }
    if(sum >= b) return true;
    else return false;
}

int main()
{
    cin >> a >> b;
    for(int i = 0 ; i < a ; i++)
        cin >> f[i];
    sort(f , f + a);
    int left = 1 , right = f[a-1] , mid;
    while(left <= right)
    {
        mid = (left + right ) >> 1;
        if(check(mid))left = mid + 1;
        else right = mid - 1;
    }
    cout << left - 1;
    return 0;
}

B题硬币找零（计蒜客T1781）
这是一个DP问题，像是一个完全背包问题，对于每一个硬币我们都可以多次使用，找到满足条件的最小使用硬币数，还有一个特别的是需要判断给的数据是否能够恰好满足需要的零钱。首先dp[ i ]储存的是当零钱为 i 时最优的选法（需要的硬币数）
状态转移 dp[ i ] = min (dp[i]) , dp[ i - 面额【当前判断的硬币】] + 1) （不选当前硬币）和（选当前硬币）
还需要判断给的数据能否满足 我们让dp = INF , 如果最后dp[ m ] == INF , 表示没能进入；

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 5;
long long int dp[N] , a[N];
int n , m;

int main()
{
    cin >> n >> m;
    int flag = 0;
    for(int i = 0 ; i < n ; i++)
            cin >> a[i];
    sort(a , a + n);
    for(int i = 0 ; i <= m ; i++)
        dp[i] = N;
    dp[0] = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = a[i] ; j <= m ; j++)
            dp[j] = min(dp[j] , dp[j - a[i]] + 1);
    if(dp[m] == N)cout << "-1";//比如样例40 30 25 ，选37 
    //dp[37] = min(dp[37] , dp[12] or dp[7] + 1),dp[12] = N
    else cout << dp[m];
    return 0;
}

C题拯救行动（计蒜客T1213）
宽度搜索 + 优先队列
关于优先队列：
博客：https://blog.csdn.net/weixin_36888577/article/details/79937886
不同于以前的迷宫问题，这里添加守卫的存在，最段路径却不一定满足最短时间。那么当我们宽搜时，队列内部应该优先时间更短的点，也就是在队列内如果到达该点的时间更短，那么我们就把它放在队列的top（) , 也就是当守卫和通道时，我们优先选择通道

#include<iostream>
#include<queue>
using namespace std;

struct poin
{
    int x;
    int y;//坐标
    int anspoin;
    poin(int x2 , int y2 , int anspoin2)
    {
        x = x2 , y = y2 , anspoin = anspoin2;
    }
    friend bool operator < (poin a , poin b)
    {
        return a.anspoin > b.anspoin;
    }
};//定义优先队列排序规则 小的先出
const int N = 201;
int jl[N][N];//记录数组
char mapx[N][N];//地图
int n , m , endx , endy , beginx , beginy , ans , aaa = 0;
int dirx[] = {-1,+1,0,0} , diry[] = {0,0,-1,+1};
void bfs()
{
    priority_queue<poin> que;//队列
    poin np(beginx,beginy,0);//将起点放进队列
    jl[beginx][beginy] = 1;
    que.push(np);//将起点放进队列
    int nx , ny;
    while(que.size())
    {
        np = que.top();
        que.pop();
        for(int i = 0 ; i < 4 ; i++)
        {
            nx = np.x + dirx[i];
            ny = np.y + diry[i];
            if(nx == endx && ny == endy)
            {
                ans = np.anspoin + 1;//到底公主时间再 +1
                aaa = 1;
                return;
            }
            if(nx >= 0 && nx < n && ny >=0 && ny < m && jl[nx][ny] == 0)
            {
              if(mapx[nx][ny] == '@')
              {
                  que.push(poin(nx,ny,np.anspoin+1));//时间加 1
                  jl[nx][ny] = 1;
              }
              if(mapx[nx][ny] == 'x')
              {
                  que.push(poin(nx,ny,np.anspoin+2));//时间加 2
                  jl[nx][ny] = 1;
              }
            }//if（条件）
        }//for 方向
    }//while
}
int main()
{
    cin >> n >> m;
    int x , y;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
        {
            cin >> mapx[i][j];
            if(mapx[i][j] == 'r') beginx = i , beginy = j;
            if(mapx[i][j] == 'a') endx = i , endy = j;
        }
        bfs();
    if(aaa == 1)cout << ans << endl;
    else cout << "Impossible" << endl;
    return 0;
}

如果我们要找出我们最短时间所走的路线呢？
我们可以用一个数组来记录 某一个点 是由哪一个点走过来的

typedef pair<int , int > zb;
zb prvex[N][N];
prvex[nx][ny] = zb(np.x,np.y);//记录

		int x = endx , y = endy;
        while(x != beginx || y != beginy)
        {
            cout << x << " " << y << endl;
            zb xx = prvex[x][y];
            x = xx.first , y = xx.second;
        }//倒叙输出

和题目相结合

#include<iostream>
#include<queue>
using namespace std;

struct poin
{
    int x;
    int y;
    int anspoin;
    poin(int x2 , int y2 , int anspoin2)
    {
        x = x2 , y = y2 , anspoin = anspoin2;
    }
    friend bool operator < (poin a , poin b)
    {
        return a.anspoin > b.anspoin;
    }
};
const int N = 201;
typedef pair<int , int > zb;
zb prvex[N][N];
int jl[N][N];
char mapx[N][N];
int n , m , endx , endy , beginx , beginy , ans , aaa = 0;
int dirx[] = {-1,+1,0,0} , diry[] = {0,0,-1,+1};
void bfs()
{
    priority_queue<poin> que;
    poin np(beginx,beginy,0);
    jl[beginx][beginy] = 1;
    que.push(np);
    int nx , ny;
    while(que.size())
    {
        np = que.top();
        que.pop();
        for(int i = 0 ; i < 4 ; i++)
        {
            nx = np.x + dirx[i];
            ny = np.y + diry[i];
            if(nx == endx && ny == endy)
            {
                ans = np.anspoin + 1;
                aaa = 1;
                prvex[nx][ny] = zb(np.x,np.y);
                break;
            }
            if(nx >= 0 && nx < n && ny >=0 && ny < m && jl[nx][ny] == 0)
            {
              if(mapx[nx][ny] == '@')
              {
                  que.push(poin(nx,ny,np.anspoin+1));
                  jl[nx][ny] = 1;
                  prvex[nx][ny] = zb(np.x,np.y);
              }
              if(mapx[nx][ny] == 'x')
              {
                  que.push(poin(nx,ny,np.anspoin+2));
                  jl[nx][ny] = 1;
                  prvex[nx][ny] = zb(np.x,np.y);
              }
            }
        }
        if(aaa == 1)break;
    }
    if(aaa == 1)
    {
        int x = endx , y = endy;
        while(x != beginx || y != beginy)
        {
            cout << x << " " << y << endl;
            zb xx = prvex[x][y];
            x = xx.first , y = xx.second;
        }
    }
}
int main()
{
    cin >> n >> m;
    int x , y;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
        {
            cin >> mapx[i][j];
            if(mapx[i][j] == 'r') beginx = i , beginy = j;
            if(mapx[i][j] == 'a') endx = i , endy = j;
        }
        bfs();
    if(aaa == 1)cout << ans << endl;
    else cout << "Impossible" << endl;
    return 0;
}

从公主点走向骑士 再用一个数组记录 就可以完整的有骑士走向公主

D题盒子和球（计蒜客T1900）
虽然知识是新的，但这确实是 放东西方案数中经典题 ，我们需要先了解第二类Stirling数 链接：https://baike.baidu.com/item/%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0/4938529?fr=aladdin

定义：第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数。和第一类Stirling数不同的是，集合内是不考虑次序的，而圆排列是有序的。常常用于解决组合数学中几类放球模型。
描述为：将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？
递推式：
（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数 S(n , m - 1)。
（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 mS(n,m) 。
综合两种情况得：**S(n + 1 , m) = S(n , m - 1) + mS(n,m)**;
知道了这里我们还需要一步 ， 注意前面的描述m个无差别的盒子 ， 但是这道题盒子是有差别的 ， 那么盒子摆放的顺序也会影响结果 ， 高中数学知识可以得出 盒子有 M！种不同摆放顺序 所以最终结果：
ans = S[n][r] * M！ << endl;

下面是代码

#include<iostream>
using namespace std;

const int N = 1e2;
int dp[N][N];
int n , r;

int main()
{
    cin >> n >> r;
    for(int i = 1 ; i <= n ; i++)
        dp[i][1] = 1;//如果只有一个盒子 那么只有以一种分法
    for(int i = 2 ; i <= n ; i++)
        for(int j = 1 ; j <= r && j <= i ; j++)
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * j;
    //dp[i-1][j-1]表示第i个球独占一个盒子 那么就是i-1个球 在 j-1 个盒子
    //有多少种放法，dp[i-1][j]第i个球和其他球公用一个盒子，那么就是 j个
//盒子放i-1个球，第i个球再在j个盒子选择放下 所以 *j
    long long int sum = 1;
    for(int i = 1 ; i <= r ; i++)
        sum *= i;
    cout << dp[n][r] * sum << endl;
    return 0;
}

E题工作城市分配（计蒜客T1286）
这是一道dp题 解题的关键是分析状态
dp[i][j] 我们用 i 表示分配北京的人数数， j 表示分配到上海的人数，那么dp[n][n]就是最终的结果了

dp[i][j] = max(dp[i-1][j] + b[i+j] , dp[i][j-1] + s[i+j]); //正常下的
//状态转移，选北京好还是上海好
if(i == 0 && j != 0)dp[i][j] = dp[i][j-1] + s[i+j];//分到北京的人数为0
if(i != 0 && j == 0)dp[i][j] =dp[i-1][j] + b[i+j];//分到上海的人数为0

#include<iostream>
using namespace  std;

const int N= 2005;
int dp[N][N];
int b[N],s[N];
int n;

int main()
{
    cin >> n;
    s[0] = 0 , dp[0][0] = 0;
    for(int i = 1 ; i <= 2*n ; i++)
        cin >> b[i] >> s[i];
    for(int i = 0 ; i <= n; i++)
        for(int j = 0 ; j <= n ; j++)
        {        
            if(i ==0 && j == 0) continue;
            else if(i == 0 && j != 0)dp[i][j] = dp[i][j-1] + s[i+j];
            else if(i != 0 && j == 0)dp[i][j] =dp[i-1][j] + b[i+j];
            else dp[i][j] = max(dp[i-1][j] + b[i+j] , dp[i][j-1] + s[i+j]); 
        }
    cout << dp[n][n];
    return 0;
}

这道题有很多种状态表示的方法 还可以dp[i][j] 表示 i 个人中 j个人分配到北京