2021 秋季力扣杯 - 战队赛复盘

写在前面

今年发挥还算挺不错的。以后再接再励！
我 30 分钟写完了 2、4 两道题，队友一小时多写完了 1、3 两道题，然后就是啥都不会的几个小时。。。

争取以后不会出现这种情况。

第一题 开幕式焰火

1.1 题目

1.2 思路分析

数组 dp 存一下状态就行了，没有出现过就加一次。

1.3 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dp[1005];
    int count = 0;
    void deal(TreeNode * root) {
        if (!root) return ;
        if (!dp[root->val]) {
            count++;
            dp[root->val] = true;
        }
        deal(root->left);
        deal(root->right);
    }
    int numColor(TreeNode* root) {
        deal(root);
        return count;
    }
};

第二题 自行车炫技赛场

2.1 题目

2.2 思路分析

这道题是一个比较基础的 dfs 思路。 可能会要使用记忆化的技术去重。 仔细读题后发现，自行车到达一个地方，并非一定会有相同的速度，也就是说，不同的路径到达一个地方，速度可能并不相同。 在这种情况下，我们必须得记录一下，如果两次到达同一个地方，具有相同的速度，我们就可以考虑不再继续。如果不去判断这一点，就会导致循环的出现，也就是示例 1 中出现的情况，如果我们不判断重复，一定会导致死循环。

所以总结一下，思路就是 dfs 加上记忆化去重（剪枝）。只有两次到达同一个地方并且具有相同的速度，才会是剪枝条件。

我的代码中主要分成了两块，一块是主函数，一块是 dfs，dfs 函数接受三个参数，也就是当前的 x，y 坐标和 speed 速度。 当passed[x][y][speed]为true时候，就说明之前以相同的速度遍历过相同的地方，而且无需再遍历一次。res[x][y]为true的时候说明该坐标是答案的一个候选坐标。接下来就是非常常规的往四个方向进行遍历。速度小于 0 就截断之类的基操。

主函数中主要是处理了一下输入输出的逻辑，存了一些全局变量，对输出的答案格式做了一个简单的操作，包括将 res 变成答案所需的形式。

2.3 C++代码

using VI = vector<int>;
using VVI = vector<VI>;
const VI direc = {0, 1, 0, -1, 0};
class Solution {
public:
    VVI t, o;
    bool res[100][100] = {};
    bool passed[100][100][105] = {};
    int n, m;
    void dfs(int x, int y, int speed) {
        if (speed == 1) res[x][y] = true;
        if (speed < 1) return;
        if (passed[x][y][speed]) {
            return;
        }
        passed[x][y][speed] = true;
        for (int i = 0; i < 4; ++i) {
            int xt = x + direc[i];
            int yt = y + direc[i + 1];
            if (xt >= 0 && yt >= 0 && xt < n && yt < m)
                dfs(xt, yt, speed + t[x][y] - t[xt][yt] - o[xt][yt]);
        }
    }
    VVI bicycleYard(VI& p, VVI& terrain, VVI& obstacle) {
        t = terrain;
        o = obstacle;
        n = t.size();
        m = t[0].size();
        int x = p[0], y = p[1];
        dfs(x, y, 1);
        VVI res_v;
        res[x][y] = false;
        for (int i = 0; i < 100; ++i)
            for (int j = 0; j < 100; ++j)
                if (res[i][j])
                    res_v.push_back({i, j});
        return res_v;
    }
};

第三题 志愿者调配

3.1 题目

3.2 思路分析

我们只有一个值不知道，就是当前（最后时刻）第 0 号位的人数。 通过观察题目不难得出，三个操作都是线性操作，而且我们准确地知道每一步的操作，也就是说，只要知道知道了最后一个时刻的第 0 号位的人数，我们就可以严丝合缝地将结果递推到第一步。并且，在此时，第一步的总和应当严格等于totalNum。

既然如此，我们不妨设一个变量 x，作为最后时刻第 0 号位的人数。逆推来完成最终的推理，推理到第一步之后，每一个场馆的人数都应该是一个关于变量 x 的一次函数，我们将其求和之后仍然是一个一次函数，这个一次函数最终等于 totalNum ，代入就可以求得 x，代入每个场馆的表达式中即可获得每个场馆在第一步时的人数。

在具体代码中，设置两个数组 x_param 和 c_param ，分别代表指定场馆一次函数中的 x 系数项和常数项。最终递推回第一步，求得 x_param_sum 与 c_param_sum 。求解 x 的方程为:

${\sum }_{i=1}^n{x}_{param}[i]\ast x+{\sum }_{i=1}^n{c}_{param}[i]=totalNum$
简单变换后得到:

$x=\frac{(totalNum-{\sum }_{i=1}^n{c}_{param}[i])}{{\sum }_{i=1}^n{x}_{param}[i]}$

最后代入到表达式中即可完成计算。

3.3 C++代码

using VI = vector<int>;
using VVI = vector<VI>;
using ll = long long;
class Solution {
public:
    VI volunteerDeployment(VI& finalCnt, ll totalNum, VVI& edges, VVI& plans) {
        VI m[50005];
        int n = finalCnt.size() + 1;
        // x系数和常数
        int x_param[50005] = {}, c_param[50005] = {};
        for (auto & edge : edges) {
            m[edge[0]].push_back(edge[1]);
            m[edge[1]].push_back(edge[0]);
        }
        x_param[0] = 1;
        for (int i = 0; i < n - 1; ++i)
            c_param[i + 1] = finalCnt[i];
        while (plans.size()) {
            int kind = plans.back()[0];
            int place = plans.back()[1];
            plans.pop_back();
            if (kind == 1) {
                x_param[place] *= 2;
                c_param[place] *= 2;
            } else if (kind == 2) {
                for (auto & nxt : m[place]) {
                    x_param[nxt] -= x_param[place];
                    c_param[nxt] -= c_param[place];
                }
            } else {
                for (auto & nxt : m[place]) {
                    x_param[nxt] += x_param[place];
                    c_param[nxt] += c_param[place];
                }
            }
        }
        ll x_param_sum = 0, c_param_sum = 0;
        for (int i = 0; i < n; ++i) {
            x_param_sum += x_param[i];
            c_param_sum += c_param[i];
        }
        // 方程: x_param_sum * x + c_param_sum = totalNum
        int x = (totalNum - c_param_sum) / x_param_sum;
        vector<int> res(n);
        for (int i = 0; i < n; ++i)
            res[i] = x_param[i] * x + c_param[i];
        return res;
    }
};

第四题 入场安检

4.1 题目

4.2 思路分析

本题注意观察题目即可发现，先进先出对应的数据结构为队列，后进先出对应的数据结构为栈。 而注意看第二个gif，我们发现，当一个容器（实验室，我们在此统称为容器）为队列时，第一个进入的第一个出队列，也就是说，一个队列对于改变流程中的第一个人没任何影响。对比着来看栈，我们发现，一个长度为2的栈必须先填充1个元素，这一个元素就相当于固定在此处，没法移动，也就是说，对于流程中的第一个人，一个长度为c的栈能够拦截c-1个人。

那么就很简单了。因为我们想要让第k个人达到对首，我们必须使用栈来拦截前k个人。

所以我们把这道题翻译成一个我们喜闻乐见的形式：

有`N`个硬币，每个的金额都在`cap`数组中给出（需要一个减1操作）。我们从前往后选，求最终金额为`k`的方案数。

是不是一下就简单了呢！

最终的做法就是一个非常简单的dp。因为一个硬币只能用一次，所以要控制dp的方向。

4.3 C++代码

const int md = 1000000007;
class Solution {
public:
    int securityCheck(vector<int>& cap, int k) {
        for (auto & c : cap) c--;
        int sum = accumulate(cap.begin(), cap.end(), 0);
        if (sum < k) return 0;
        int dp[40005] = {1};
        for (auto & c : cap) {
            for (int i = k - c; i >= 0; --i) {
                (dp[i + c] += dp[i]) %= md;
            }
        }
        return dp[k];
    }
};