飞往大厂梦之算法提升-7

今天主要给大家分享dfs以及动态转移中的数位dp问题，这两类问题可以很好地提升我们的思维。希望能对大家有所帮助。

第一题：

问题描述

小蓝有一天误入了一个混境之地。

好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息：

1. 混境之地的大小为 n⋅m，其中 # 表示这个位置很危险，无法通行，. 表示道路，可以通行。
2. 他现在所在位置的坐标为(A,B) ，而这个混境之地出口的坐标为 (C,D) ，当站在出口时即表示可以逃离混境之地。
3. 混境之地中有 kk 个单向传送门，当你站在上面时，你可以选择消耗 pi​ 点能量，从当前点(x1i​,y1i​) 传送至 (x2i​,y2i​) ，同样你也可以选择不通过该传送门。

坏消息是：小蓝仅剩下 E点能量。

小蓝可以往上下左右四个方向行走，每行走一步，消耗一点能量。

小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，请你帮他计算一下，他最多可以剩下多少能量，如果无法逃离则输出 -1 。

输入格式

第 1行输入两个正整数 n,m ，表示混境之地的大小。

第 2 行输入四个正整数 A,B,C,D ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。

第 3行至第 n+2 行，每行 m 个字符，表示混境之地的地图，其中 # 表示为危险的地方， . 表示普通的道路。

第 n+3 行输入一个正整数 kk ，表示传送门的数量。

接下来 k 行，每行五个正整数 x1i​,y1i​,x2i​,y2i​,pi​ ，表示(x1i​,y1i​) 处有一个单项传送门，可以消耗 pip点能量使用该传送门从 (x1i​,y1i​) 传送至（x2i​,y2i​) 。

最后一行输入一个 E ，表示小蓝剩下的能量值。

输出格式

输出数据共一行为一个整数：

• 若小蓝可以逃离混境之地，则输出他最多可以剩下的能量值。
• 若小蓝无法逃离混境之地，则输出 -1 。

输入案例：

5 5
1 1 2 5
...#.
..#..
#...#
...#.
.....
2
1 2 5 3 1
1 3 1 5 2
7

输出案例：

2

代码部分：

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
int n, m, a, b, c, dd, k, e;
const int N = 55;
pair<int, int> g[N][N];
char mp[N][N];
int vis[N][N];
int d[N][N], h[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dj() {
    memset(d, 0x3f, sizeof d);
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> > q;
    d[a][b] = 0;
    q.push({0, {a, b}});
    while (!q.empty()) {
        int x = q.top().y.x;
        int y = q.top().y.y;
        int z = q.top().x;
        q.pop();
        if(vis[x][y])continue;
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
          int nx=x+dx[i],ny=y+dy[i];
          if(nx<1||ny<1||nx>n||ny>m||mp[nx][ny]=='#'||vis[nx][ny])continue;
          if(d[nx][ny]>d[x][y]+1)
          {
            d[nx][ny]=d[x][y]+1;
            q.push({d[nx][ny],{nx,ny}});
          }
         
          }
           if(h[x][y])
          {
            int nx=g[x][y].x;
            int ny=g[x][y].y;
            if(d[nx][ny]>d[x][y]+h[x][y])
            {
              d[nx][ny]=d[x][y]+h[x][y];
              q.push({d[nx][ny],{nx,ny}});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    cin >> a >> b >> c >> dd;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    cin >> k;
    while (k--) {
        int x1, x2, y1, y2, w;
        cin >> x1 >> y1 >> x2 >> y2 >> w;
        g[x1][y1] = {x2, y2};
        h[x1][y1] = w;
    }
    cin >> e;
    dj();
    if (d[c][dd]>1e9) cout << "-1";
    else cout << e - d[c][dd];
    return 0;
}

这是一道经典的路径问题，这道题跟我们之前做的区别就在于，这道题路径中并没有直接的钥匙或者圣水什么，所以并不是简单的求解里面的某一点到入口或者出口的距离。所以这道题需要用priority_queue进行求解。

这里有几个注意点⚠️：

1.priority_queue使用小根堆，即更小的数在前面。

2.注意if（h[x][y]）的判断要在for外面，这里是我一开始一直做错的原因。

3.make_pair的输入方式（c++11版本）

第二题：

问题描述

从前有一个国王，他十分热爱数字，他认为数字的优雅程度可以从它们的位数上体现出来。数字的“优雅程度”越高，就越能够吸引他的眼球。他定义，只要一个正整数的十进制表示中包含不超过 3 个非零数字，就被认为是优雅的数字。例如，3、2000、123 是优雅的数字，而 4321、12306、120086 则不是。

这个国王曾经让他的数学家寻找一定范围内所有的优雅数字。但这些数学家并不满足于简单地列出这些数字，他们想要创造一个故事，使得这些数字更加有生命力、更加有意义。于是他们提出了一个挑战：给出一个数字区间，计算其中有多少个优雅的数字。你能够帮助这些数学家完成他们的任务吗？

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含一个整数 T(1≤T≤102)，表示要考虑的数字区间的数量。

接下来 T行，每行包含两个整数 Li​ 和 Ri(1≤Li​≤Ri​≤1018)，表示一个区间的左右端点。

输出格式

对于每个测试用例，输出一个整数，表示相应区间中优雅数字的数量。

输入案例：

2
1 1000
11111 22222

输出案例：

1000
552

代码部分：

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
ll dp[20][2][20];
int a[20];
ll dfs(int pos,bool snt,bool limit,int cnt){
  if(pos<0)return (int)(cnt<=3);
  if(!limit&&dp[pos][snt][cnt]!=-1)return dp[pos][snt][cnt];
  ll res=0;
  int up=limit?a[pos]:9;
  for(int i=0;i<=up;i++){
    res+=dfs(pos-1,snt||(i>0),limit&&(i==up),cnt+(i>0));
  }
  if(!limit)dp[pos][snt][cnt]=res;
  return res;
}

ll f(ll b){
  int pos=0;
  while(b){
    a[pos++]=b%10;
    b/=10;
  }
  return dfs(pos-1,false,true,0);
}
int main()
{
  int t;
  cin>>t;
   
  while(t--){
   memset(dp,-1,sizeof(dp));
    ll a,b;
    cin>>a>>b;
    cout<<f(b)-f(a-1)<<'\n';
  }
  return 0;
}

这道题是数位dp的标准问题，关于数位dp大家可以看看我之前的文章，有专门做过这一部分的题解，大家可以多多了解了解。

对于数位dp要注意⚠️：

1.limit==false时进行剪纸

2.a[n]是从低位开始存放的,但是从高位开始剪枝。

3.结果注意要是没有0，要减去1，看题意具体的描述。

第三题

问题描述

在一个神秘的魔法世界中，有一位年轻的魔法学徒叫做小李。小李是一个非常聪明的学徒，他一直在学习各种魔法，包括数学魔法。

有一天，小李找到了一本古老的魔法书，书中记载了很多神秘的数学问题和解法。小李对其中一个问题非常感兴趣，它是这样的：给定两个正整数 n 和 k，请计算在 1 到 n 中有多少个数的各位数字之和是 k 的倍数。

小李思考了很久，但是一直没有找到解决这个问题的方法。他知道这个问题与数位魔法有关，但是他不知道具体如何操作。于是，小李求助了你。

现在，请你帮助他编写一个程序，来解决这个数学问题。由于这个问题的答案很大，你只需要将答案对 998244353 取模的结果给他即可。

输入格式

输入共一行，包含两个正整数 n和 k（1≤n≤101000,1≤k≤100）。

输出格式

输出一个整数，表示在 1到 n 中有多少个数的各位数字之和是 kk 的倍数，对998244353 取模的结果。

输入案例：

20 4

输出案例：

4

代码部分：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll p=998244353;
const int N=1003;
map<ll,ll>dp[N];
int a[N];
int k;
string n;
ll dfs(int pos,int limit,ll sum){
  if(pos<0)return (sum==0);
  if(!limit&&dp[pos].find(sum)!=dp[pos].end())return dp[pos][sum];
  ll res=0;
  int up=limit?a[pos]:9;
  for(int i=0;i<=up;i++){
    res+=dfs(pos-1,limit&&(up==i),(sum+i)%k)%p;
  }
  if(!limit)dp[pos][sum]=res;
  return res;
}

int main()
{
  cin>>n>>k;
  for(int i=0;i<n.size();i++){
    a[n.size()-i-1]=n[i]-'0';
  }
  cout<<dfs(n.size(),1,0)-1<<'\n';
  return 0;
}

这道题思路与上一条一样，但是注意当题目数值较大时，可以选择用map<int,int>dp[][]来存储数据，这样可以让没有的值为空值。

第四题：

问题描述

给定 N,K，询问有多少个 N 的全排列，满足有 K个逆序对，答案对998244353 取模。

输入格式

第一行包含 2 个正整数N,K。

输出格式

输出共 1 行，包含 1 个整数，表示最终答案，答案对 998244353 取模。

输入案例：

3 1

输出案例：

2

代码部分：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e2+10;
ll dp[N][N];
const int mod = 998244353;
int main()
{
  int n,k;cin>>n>>k;
  for(int i=1;i<=n;i++){
    dp[i][0]=1;
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=k;j++){
      for(int l=0;l<i&&l<=j;l++){
        dp[i][j]=(dp[i][j]+dp[i-1][j-l])%mod;
      }
    }
  }
  cout<<dp[n][k];
  return 0;
}

理解这道题就可以更好地理解dp的实质，前后状态转移的实质，而不是死记硬背，这道题虽然简单，但是却可以很好地考察你对于动态规划转移的本质理解。

好了，今天的分享就到这里，希望大家可以多多关注博主，后续我也将继续分享相关内容。