故障键盘

水题。

class Solution {
public:
    string finalString(string s) {
        string res;
        for (char c : s) {
            if (c == 'i') {
                reverse(res.begin(), res.end());
            } else {
                res += c;
            }
        }
        return res;
    }
};

判断能否拆分数组

要把长度为n的数组拆成n个子数组，就说明最后的所有子数组长度都为1。这个肯定是可以做到的，那么问题就是中间拆分过程中产生的长度不为1的子数组，能否满足其值≥m？如果能找到一个长度为2的子数组，其值≥m，那么就可以保证中间产生的所有子数组都≥m。
假设那个子数组在左边，我们第一次一分为二，可以右边只留一个，那么右边长度为1，必然合法，左边因为子数组存在，也不可能小于m，也合法。就这样温水煮青蛙，一次拿一个出来，所有这种方案是必然合法的。

所有检测是否存在长度为2的子数组值≥m即可。

class Solution {
public:    
    bool canSplitArray(vector<int>& nums, int m) {
        if (nums.size() <= 2) {
            return true;
        }
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] + nums[i + 1] >= m) {
                return true;
            }
        }
        return false;
    }
};

找出最安全路径

先用多源BFS，预处理出每一个点的安全系数。
然后二分答案，用BFS检测，要求节点不小于这个安全系数的情况下，是否存在一条从起点到终点的路径。

class Solution {
public:
    constexpr static int dx[4] = {0, 1, 0, -1};
    constexpr static int dy[4] = {-1, 0, 1, 0};
    int n, m;
    vector<vector<int>> st;
    vector<vector<int>> dist;

    bool check(int mid)
    {
        if (dist[0][0] < mid) return false;

        using PII = pair<int, int>;
        queue<PII> q;
        q.push({0, 0});

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                st[i][j] = false;
        st[0][0] = true;

        while (!q.empty())
        {
            auto t = q.front(); q.pop();
            if (t.first == n - 1 && t.second == m - 1) return true;

            for (int i = 0; i < 4; ++i)
            {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !st[x][y] && dist[x][y] >= mid)
                    q.push({x, y}), st[x][y] = true;
            }
        }
        return false;
    }
    
    int maximumSafenessFactor(vector<vector<int>>& grid) 
    {
        n = grid.size(), m = grid[0].size();
        if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) return 0;
        
        st = vector<vector<int>>(n, vector<int>(m));
        dist = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f)); // 预处理所有格子到小偷的最短曼哈顿距离
        using PII = pair<int, int>;
        queue<PII> q;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (grid[i][j] == 1)
                    q.push({i, j}), dist[i][j] = 0;
        while (!q.empty())
        {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int sx = x + dx[i], sy = y + dy[i];
                if (sx >= 0 && sx < n && sy >= 0 && sy < m && dist[sx][sy] == 0x3f3f3f3f)
                    dist[sx][sy] = dist[x][y] + 1, q.push({sx, sy});
            }
        }

        int l = 0, r = min(dist[0][0], dist[n - 1][m - 1]);
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
            printf("---%d\n", r);
        }
        puts("-----");
        return r;
    }       
};

子序列的最大优雅度

优雅度由两个维度，一个是利润，一个是种类数。
可以使用反悔贪心来做，首先按照利润从大到小排序，选取前k个，这个就是可能的最大利润和了。
之后对剩下的每一个项，有以下几种情况：

1. 这个项目的类别和前k个项目的类型重复，选它必然不会使得答案变好。
2. 这个项目的类别和前k个项目的类型不重复，选他可能使得答案变好。
   1. 从前k个项目里选一个项目移除，如果这个项目的类型只出现一次，那么类型数不变，利润数下降，答案不会变好。
   2. 从前k个项目里选一个项目移除，如果这个项目的类型出现多次，那么类型数提高，利润数下降，答案可能会变好。

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        sort(items.begin(), items.end(), [] (const auto &a, const auto &b) {
            return a[0] > b[0];
        });

        long long res = 0, total_profit = 0;
        unordered_set<int> st;
        stack<int> profit;

        for (int i = 0; i < items.size(); ++i)
        {
            int a = items[i][0], b = items[i][1];
            if (i < k)
            {
                total_profit += a;
                if (st.count(b)) profit.push(a);
                else st.insert(b);
            }
            else if (!profit.empty() && !st.count(b))
            {
                st.insert(b);
                total_profit += a - profit.top();
                profit.pop();
            }
            res = max(res, total_profit + (long long)st.size() * (long long)st.size());
        }
        return res;
    }
};