$LCP$ 61. 气温变化趋势

class Solution {
public:
    bool check(int a, int b, int c, int d) {
        if (a < c && b < d) return true;
        if (a > c && b > d) return true;
        if (a == c && b == d) return true;
        return false;
    }

    int temperatureTrend(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            int j = i;
            while (j + 1 < n && check(a[j], b[j], a[j + 1], b[j + 1])) j ++ ;
            res = max(res, j - i);
            i = j;
        }
        return res;
    }
};

$LCP$ 62. 交通枢纽

const int N = 1010;

class Solution {
public:
    int transportationHub(vector<vector<int>>& path) {
        set<int> S;
        vector<int> ind(N), outd(N);
        for (auto &p: path) {
            auto a = p[0], b = p[1];
            ind[b] ++ , outd[a] ++ ;
            S.insert(a), S.insert(b);
        }

        int res = -1;
        for (auto &s: S)
            if (ind[s] == S.size() - 1 && outd[s] == 0)
                res = s;

        return res;
    }
};

$LCP$ 63. 弹珠游戏

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010, INF = 1e9;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

class Solution {
public:
    int n, m;
    vector<string> p;
    int g[N][N][4];

    int dfs(int x, int y, int d) {
        if (x < 0 || y < 0 || x >= n || y >= m) return INF;
        if (p[x][y] == 'O') return 0;
        if (g[x][y][d]) return g[x][y][d];

        int &res = g[x][y][d];
        if (p[x][y] == 'W') d = (d + 3) % 4;
        if (p[x][y] == 'E') d = (d + 1) % 4;
        x += dx[d], y += dy[d];

        res = dfs(x, y, d);
        return res + (res != INF);
    }

    vector<vector<int>> ballGame(int mx, vector<string>& plate) {
        p = plate;
        n = p.size(), m = p[0].size();

        vector<vector<int>> res;
        vector<PII> row{{0, 2}, {n - 1, 0}}, col{{0, 1}, {m - 1, 3}};

        for (auto t: row)
            for (int i = 1; i < m - 1; i ++ ) 
                if (p[t.x][i] == '.' && dfs(t.x, i, t.y) <= mx) 
                    res.push_back({t.x, i});

        for (auto t: col)
            for (int i = 1; i < n - 1; i ++ )
                if (p[i][t.x] == '.' && dfs(i, t.x, t.y) <= mx)
                    res.push_back({i, t.x});

        return res;
    }
};

$LCP$ 64. 二叉树灯饰

$Version 1$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct Node {
    int a[2], root[2];
};

class Solution {
public:
    Node dfs(TreeNode* u) {
        if (!u->left && !u->right) {
            if (u->val) return {{1, 0}, {1, 0}};
            else return {{0, 1}, {0, 1}};
        }
        auto l = u->left ? dfs(u->left): (Node){{0, 0}, {0, 0}};
        auto r = u->right ? dfs(u->right): (Node){{0, 0}, {0, 0}};

        Node res;
        int t = u->val, s[2];
        for (int i = 0; i < 2; i ++ ) s[i] = l.a[i] + r.a[i];

        int mi = min(s[0], s[1]);
        res.a[t] = s[t], res.root[t] = s[t ^ 1];
        res.a[t ^ 1] = min(mi, l.root[t] + r.root[t]) + 1;
        res.root[t ^ 1] = min(mi, l.root[t ^ 1] + r.root[t ^ 1]) + 1;

        for (int i = 0; i < 2; i ++ ) {
            res.a[i] = min(res.a[i], res.a[i ^ 1] + 1);
            res.root[i] = min(res.root[i], res.root[i ^ 1] + 1);
        }
        return res;
    }

    int closeLampInTree(TreeNode* root) {
        auto res = dfs(root);
        return res.a[0];
    }
};

$Version 2$

/**
 * 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:
    unordered_map<TreeNode*, vector<vector<int>>> h;

    int dfs(TreeNode* u, bool s2_odd, bool s3) {
        if (!u) return 0;
        if (h.count(u)) {
            if (h[u][s2_odd][s3] > 0) 
                return h[u][s2_odd][s3];
        }
        else h[u] = vector<vector<int>>(2, vector<int>(2));

        if ((u->val == 1) == (s2_odd == s3)) {
            int res1 = dfs(u->left, s2_odd, false) + dfs(u->right, s2_odd, false) + 1;
            int res2 = dfs(u->left, !s2_odd, false) + dfs(u->right, !s2_odd, false) + 1;
            int res3 = dfs(u->left, s2_odd, true) + dfs(u->right, s2_odd, true) + 1;
            h[u][s2_odd][s3] = min({res1, res2, res3});
            return h[u][s2_odd][s3];
        }
        else {
            int res0 = dfs(u->left, s2_odd, false) + dfs(u->right, s2_odd, false);
            int res13 = dfs(u->left, s2_odd, true) + dfs(u->right, s2_odd, true) + 2;
            int res23 = dfs(u->left, !s2_odd, true) + dfs(u->right, !s2_odd, true) + 2;
            h[u][s2_odd][s3] = min({res0, res13, res23});
            return h[u][s2_odd][s3];
        }
    }

    int closeLampInTree(TreeNode* root) {
        return dfs(root, false, false);
    }
};

$LCP$ 65. 舒适的湿度

Version 1

const int N = 2010;

class Solution {
public:
    vector<int> op;
    bitset<N> f, g;

    bool check(int mid) {
        g = 0;
        for (int i = 0; i <= mid; i ++ ) g[i] = 1;
        f = g;
        for (auto x: op)
            f = ((f << x) | (f >> x)) & g;
        return f.any();
    }

    int unSuitability(vector<int>& operate) {
        op = operate;
        int l = 0, r = N;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

Version 2

const int INF = 0x3f3f3f3f;

class Solution {
public:
    int unSuitability(vector<int>& op) {
        int mx = *max_element(op.begin(), op.end()) * 2 + 1;

        int f[mx], g[mx];
        memset(g, 0x3f, sizeof g);
        g[0] = 0;

        for (auto x: op) {
            memset(f, 0x3f, sizeof f);
            for (int j = 0; j < mx; j ++ ) {
                int d = g[j];
                if (d == INF) continue;
                if (j + x < mx) f[j + x] = min(f[j + x], max(d, j + x));
                if (j > x) f[j - x] = min(f[j - x], d);
                else f[0] = min(f[0], d - j + x);
            }
            memcpy(g, f, sizeof f);
        }

        return *min_element(f, f + mx);
    }
};

Version 3 —— 2024 / 9 / 3

原题：CF1579G

$dp[i][j]$ 表示考虑前 $i$ 个，落点到最下边的点的距离为 $j$，最上到最下的最小距离为 $dp[i][j]$。

• $j \geqslant op[i]$，说明对其加负号也不影响曾经最下边的点，$dp[i][j - op[i]] = dp[i - 1][j]$
• $j \lt op[i]$，说明将其改成负号让当前的落点成为最下边的点，$dp[i][0] = dp[i - 1][j] + (op[i] - j)$
• $j + op[i] \leqslant \max(op) \cdot 2$，其中 $\max(op)$ 为 $op$ 数组的最大值，因为如果放下去超过了最大值，不划算，不如加一个负号让它往下，这样一定会让落点 $\gt -max$。但要注意有可能超过了之前的 最上到最下的最小距离，因此有 $dp[i][j + op[i]] = \max(dp[i - 1][j], \ j + op[i])$

constexpr int inf = 1E7;

class Solution {
public:
    int unSuitability(vector<int>& op) {
        int max = *std::max_element(op.begin(), op.end());
        vector<int> dp(max * 2 + 1, inf);
        dp[0] = 0;
        for (int o: op) {
            vector<int> ndp(max * 2 + 1, inf);
            for (int i = 0; i <= max * 2; i++) {
                int l = i - o;
                int r = i + o;
                if (l >= 0) {
                    ndp[l] = std::min(ndp[l], dp[i]);
                } else { 
                    ndp[0] = std::min(ndp[0], dp[i] - l);
                }
                if (r <= max * 2) {
                    ndp[r] = std::min(ndp[r], std::max(dp[i], r));
                }
            }
            dp.swap(ndp);
        }
        return *std::min_element(dp.begin(), dp.end());
    }
};