牛客算法周周练3

A、Jelly

给定三维地图，并且给出不能走的位置）星号，问从 $图片说明$ 到 $图片说明$ 的最短路径是多长。
挺裸的 $图片说明$ 题目，这里提醒一下走图最好别用DFS会爆内存死的很惨。
规定移动方向，判断是否越界，在判断这个点是否走过，在判断这个点是不是不能走的位置，如果都不是，就把这个点进队，位移长度是前一个走法加一，一直到 $图片说明$ ，因为是 $图片说明$ ，第一次到终点就是最短路了。直接 $图片说明$ 出循环。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532270

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
struct Node {
    int x, y, z, s;
};
queue<Node>    que;
char mp[N][N][N];
bool vis[N][N][N];

int dx[] = { 1,-1,0,0,0,0 };
int dy[] = { 0,0,1,-1,0,0 };
int dz[] = { 0,0,0,0,1,-1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                cin >> mp[i][j][k];
    if (mp[n][n][n] == '*')    puts("-1");
    else {
        bool flag = false;
        queue<Node> que;
        que.push(Node{ 1,1,1,1 });
        vis[1][1][1] = true;
        while (!que.empty()) {
            Node temp = que.front();
            que.pop();
            for (int i = 0; i < 6; ++i) {
                int xx = temp.x + dx[i], yy = temp.y + dy[i], zz = temp.z + dz[i];
                if (xx<1 || yy<1 || zz<1 || xx>n || yy>n || zz>n || mp[xx][yy][zz] == '*' || vis[xx][yy][zz])
                    continue;
                que.push(Node{ xx,yy,zz,temp.s + 1 });
                vis[xx][yy][zz] = true;
                if (xx == n && yy == n && zz == n) {
                    printf("%d\n", temp.s + 1);
                    flag = true;
                    break;
                }
            }
        }
        if (!flag)    puts("-1");
    }
    return 0;
}

B、「木」迷雾森林

又是一个走图题，不过这次问的是路径数，不是最短路径，我们从（n,1）走到（1，m），只能向上和向右，很浅显的一个动态规划题目。我们使用 $图片说明$ 表示出发点走到 $图片说明$ 的方法数。从出发点开始看起，沿着出发点，一路向上只有一种走法，一路向右也只有一种走法，所以，如果这个地方可以走，那么就把这个地方的方法数规定成1。那么其他位置，要么是从 $图片说明$ 过来，要么是从 $图片说明$ 过来，把两种方案数累加就是 $图片说明$ 的方案数。
所以我们得到状态转移方程
1、第n行中不是1的点，dp[n][j]=1;
2、第1列中不是1的点，dp[i][1]=1;
3、其余位置不是1的点，dp[i][j]=dp[i-1][j]+dp[i][j-1];
4、剩下1的点，dp[i][j]=0;

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532258

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N = 3001;
const int MOD = 2333;
int mp[N][N];
int dp[N][N];

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            mp[i][j] = read();
    for (int i = n; i >= 1; --i)
        if (!mp[i][1])    dp[i][1] = 1;
        else    break;
    for (int i = 1; i <= m; ++i)
        if (!mp[n][i])    dp[n][i] = 1;
        else    break;
    for (int i = n - 1; i >= 1; --i)
        for (int j = 2; j <= m; ++j) {
            if (mp[i][j]) {
                dp[i][j] = 0;
                continue;
            }
            else    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % MOD;
        }
    printf("%d\n", dp[1][m]);
    return 0;
}

C、小雨坐地铁

分层建图，求单源最短路，不带负权边。
如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。
我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二条地铁线在第二层，这层地铁线可能也用到了第一层某个站点，我们就要对应在M+1层开一个超级源点，从站点去超级源点假设花费为0，那么从超级源点去往某一条地铁线中的点就是转线或者上地铁了，花费记作上地铁的花费。
那么我们的迪杰斯特拉算法就变成了，从超级源点中的起点，去往超级源点中的终点。存在的最短路，直接求解即可，判断是否小于等于初始化的INF，直接输出答案就OK了。

vector相比于前向星码量小，适合我这种懒人，卡vector的 坑爹良心出题人想让我们多用用更好的方案

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43533955

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 5e5+3e3; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
ll d1[N];//d1正向图
struct Node {
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N];
int n, m, st, ed;

void dijkstra(int s, ll d[]) {
    priority_queue<Node>  pq;
    fill(d, d + N, INF);
    d[m * n + s] = 0;
    pq.push(Node{ m * n + s,0 });
    while (!pq.empty()) {
        Node    x = pq.top();
        pq.pop();
        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
        for (auto it : e[x.v]) {
            if (d[it.v] > x.cost + it.cost) {
                d[it.v] = x.cost + it.cost;
                pq.push(Node{ it.v,d[it.v] });
            }
        }
    }
}

int main() {
    n = read(), m = read(); st = read(), ed = read();
    for (int i = 0; i < m; ++i) {
        int a = read(), b = read(), c = read(), x = read();
        e[i * n + x].push_back(Node{ m * n + x, 0 });
        e[m * n + x].push_back(Node{ i * n + x, a });
        while (--c) {
            int y = read();
            e[i * n + x].push_back(Node{ i * n + y, b });
            e[i * n + y].push_back(Node{ i * n + x, b });
            e[i * n + y].push_back(Node{ m * n + y, 0 });
            e[m * n + y].push_back(Node{ i * n + y, a });
            x = y;
        }
    }
    dijkstra(st, d1);
    if (d1[m * n + ed] == INF)  puts("-1");
    else    printf("%lld\n", d1[m * n + ed]);
    return 0;
}

D、表达式求值

挺简单的模拟题，我的做法是开一个加法栈，把最终需要加的元素放在里面，一个个对字符串处理，把第一个数字直接放进加法栈，其余位置如果是乘号，取出加法栈的栈顶，与乘号后面的元素进行乘法，再进栈。如果是加号，直接读到后面一个运算符号的时候把读到的数放进栈。最后通过把栈中元素全部累加就可以得出最终答案。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532725

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    stack<int> st;
    string s;
    cin >> s;
    int len = s.length(), res = 0, m = 0;
    while (!st.empty())
        st.pop();
    for (int i = 0; i < len; ++i) {
        if (s[i] >= '0' && s[i] <= '9')
            res = res * 10 + s[i] - '0';
        else {
            res = res % 10000;
            if (!m || m == 1) {
                st.push(res);
            }
            else {
                int temp = st.top();
                st.pop();
                st.push((temp % 10000 * res % 10000) % 10000);
            }
            if (s[i] == '*')
                m = 2;
            else
                m = 1;
            res = 0;
        }
    }
    res %= 10000;
    if (!m || m == 1) {
        st.push(res);
    }
    else {
        int temp = st.top();
        st.pop();
        st.push((temp % 10000 * res % 10000) % 10000);
    }
    int ans = 0;
    while (!st.empty()) {
        ans += st.top();
        ans %= 10000;
        st.pop();
    }
    cout << ans << endl;
    return 0;
}

Python作弊代码，调用eval（）函数，注意调整一下递归深度~~Py写起来就是爽~~。

import sys
sys.setrecursionlimit(150000)# 调整递归深度，默认900多，表达式运算符过多，需要手动调一下，不然80分
print(eval(input())%10000)

E、Sunscreen

英文题面，简单说下题面意思，给定N头牛M种防晒霜，下面给出每头牛的最低值和最高值，再给出防晒霜的能力值和数量，我们给牛用了防晒霜，牛的能力值就变成防晒霜的能力值，我们要让牛位于它最大值和最小值中间，这头牛就会高兴，问最大可以让多少头牛高兴。
我们如果把全部的牛，按照最小值降序排下序，再把防晒霜按能力值升序排个序。
一个贪心思路，如果当前的牛，找到的最接近最大值要求的防晒霜，不能用来契合自己的最小值，那么后面最小值比你小的牛说不定可以。如果当前牛找不到最契合最大值的防晒霜，那么这头牛也不能高兴了。那么最小值比你小的牛，说不定最大值比你大，指不定可以找到防晒霜。综合来看，最小值比你小的牛，比你更容易找到可行的防晒霜，所以优先处理难处理的最小值大的牛，可以保证局部最优，最终结果就是整体达到最优解。
这里我再说一个错误的贪心思路，如果我们按照最小值升序排序，防晒霜也按照能力值升序排序，从最小值最小开始找第一个符合最小值要求的防晒霜，如果这头牛使用了这个防晒霜，后面的牛最大值又比你小，说不定就不能找到合适的防晒霜使用。所以不一定要使用最接近最小值的防晒霜。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43536253

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 2505;
struct Node {
    int mini, maxi;
    bool operator < (const Node b)const {
        return mini < b.mini;
    }
}a[N];
map<int, int> mp;

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        a[i].mini = read();
        a[i].maxi = read();
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= m; ++i) {
        int spf = read(), cnt = read();
        mp[spf] += cnt;
    }
    int ans = 0;
    mp[0] = n; //哨兵保证没有防晒霜不会出异常
    for (int i = n; i; --i) {
        auto it = mp.upper_bound(a[i].maxi);
        --it;
        if (it->first >= a[i].mini) {
            ++ans;
            it->second -= 1;
            if (it->second == 0)
                mp.erase(it);
        }
    }
    printf("%d\n", ans);
    return 0;
}