解法：经典结论 & 前缀和

把 $x$ 变成 $0$ 至少需要 $p$ 步，其中 $p$ 是满足 $4^p > x$ 的最小整数。

知道了每个元素需要的操作步数后，怎么求出答案呢？这就是 leetcode 1953. 你可以工作的最大周数，结论是：设所有元素操作次数之和为 $s$，最大操作次数为 $m$，那么答案为 $\max(\lceil\frac{s}{2}\rceil, m)$。

可以用前缀和的方式把 $[l, r]$ 的操作次数之和算出来，详见参考代码。复杂度 $\mathcal{O}(q\log X)$，其中 $X = 10^9$ 是值域。

参考代码（c++）

class Solution {
public:
    long long minOperations(vector<vector<int>>& queries) {
        // 计算 [1, x] 的操作次数之和
        auto calc = [&](long long x) {
            long long ret = 0;
            long long p = 1;
            // [p, 4p) 范围内的元素，操作次数均为 i
            for (int i = 1; p <= x; i++, p *= 4) {
                long long cnt = min(p * 4 - 1, x) - p + 1;
                ret += cnt * i;
            }
            return ret;
        };

        long long ans = 0;
        for (auto &qry : queries) {
            int l = qry[0], r = qry[1];
            ans += max(
                // 用前缀和算出 [l, r] 操作次数之和 s，这里求的是 ceil(s / 2)
                (calc(r) - calc(l - 1) + 1) / 2,
                // 用前缀和算出 r 的操作次数，因为元素越大，操作次数最大
                calc(r) - calc(r - 1)
            );
        }
        return ans;
    }
};

解法：枚举

假设每次操作只会减去 $2^i$，大家都知道答案是 num1 的二进制表示中 $1$ 的数量。加入了 num2 之后不太好处理，所以我们尝试枚举操作次数，把 num2 的影响一次性处理掉。

假设我们要恰好执行 $k$ 次操作，令 x = num1 - k * num2，我们需要检查能否用恰好 $k$ 个 $2^i$ 凑成 $x$。

容易看出，至少需要 popcount(x) 个 $2^i$ 才能凑成 $x$（popcount(x) 就是 $x$ 的二进制表示中 $1$ 的数量）；同时，至多只能用 $x$ 个 $2^0 = 1$ 凑出 $x$。也就是说，只要 $k$ 满足 popcount(x) <= k <= x 就是一个合法的 $k$。

那么为什么 popcount(x) 和 $x$ 之间的所有值都能取到呢？这是因为，每个 $2^i$ 都能拆成两个 $2^{i - 1}$，数量增加 $1$，因此所有值都能取到。

因此，我们从 $1$ 开始枚举 $k$，发现合法的 $k$ 即可返回答案。

接下来分析这个做法的复杂度：

• 当 num2 == 0 时，popcount(x) 和 x 的值是固定的，只要枚举到 k == popcount(x) 即可返回答案。复杂度 $\mathcal{O}(\log x)$。
• 当 num2 < 0 时，x 每次至少增加 $1$，而 popcount(x) 是 $\mathcal{O}(\log x)$ 的。因为 $k$ 从 $0$ 开始，每次只增加 $1$，因此它永远不会超过 $x$。那么 $k$ 只要超过 popcount(x) 就够了。复杂度 $\mathcal{O}(\log x)$。
• 当 num2 > 0 时，x 会越来越小，当 $k > x$ 时即可返回无解。除此之外，当 $k$ 超过 popcount(x) 时即可返回答案，复杂度仍然为 $\mathcal{O}(\log x)$。

因此整体复杂度 $\mathcal{O}(\log x)$。

参考代码（c++）

###c++

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        for (int k = 1; ; k++) {
            long long x = num1 - 1LL * k * num2;
            if (k > x) return -1;
            if (__builtin_popcountll(x) <= k && k <= x) return k;
        }
    }
};

解法：枚举

先将所有点按 $x$ 坐标升序，$y$ 坐标降序进行排序。枚举矩形左上角 $P(x_p, y_p)$，然后枚举矩形右下角。容易发现随着 $x$ 坐标的增加，矩形右下角的 $y$ 坐标是严格上升的。这是因为，考虑两个点 $A(x_a, y_a)$ 和 $B(x_b, y_b)$ 满足 $x_p \le x_a \le x_b$ 以及 $y_p \ge y_a \ge y_b$，则以 $B$ 为右下角的矩形一定会包含点 $A$。

所以我们枚举右下角的过程中，维护一个变量 $l$ 表示之前的右下角最大的 $y$ 坐标是多少，只有 $y$ 坐标在 $[l + 1, y_p]$ 之间的点才有可能成为右下角。

复杂度 $\mathcal{O}(n^2)$。

附注

• 即使有 $x$ 坐标相同的点，这个做法依然是正确的。原因请读者结合参考代码思考。提示：和枚举的顺序有很大关联。
• 本题也有 $\mathcal{O}(n\log^2n)$ 的做法，感兴趣的读者请参考原题：<某代码力量网站>/problemsets/acmsguru/problem/99999/512

参考代码（c++）

###c++

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        // 将点按横坐标升序，纵坐标降序进行排序
        sort(points.begin(), points.end(), [](vector<int> &a, vector<int> &b) {
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });

        int ans = 0;
        // 枚举左上角
        for (int i = 0; i < n; i++) {
            // 维护变量表示之前的右下角最大纵坐标是多少
            int lim = -2e9;
            // 枚举右下角
            for (int j = i + 1; j < n; j++)
                // 只有纵坐标在 [lim + 1, points[i][1]] 之间的点才可以成为右下角
                if (points[j][1] <= points[i][1] && points[j][1] > lim)
                    ans++, lim = points[j][1];
        }
        return ans;
    }
};

解法：数学

因为所有花都得拿走，且拿走最后一朵的人获胜，所以 Alice 必胜的条件是鲜花总数是奇数。所以题目问的就是满足 $1 \le x \le n$ 且 $1 \le y \le m$ 且 $(x + y)$ 是奇数的 $(x, y)$ 数量。

奇数加偶数才等于奇数，所以答案就是 ([1, n] 里的奇数个数) * ([1, m] 里的偶数个数) + ([1, n] 里的偶数个数) * ([1, m] 里的奇数个数)。复杂度 $\mathcal{O}(1)$。

参考代码（c++）

###c++

class Solution {
public:
    long long flowerGame(int n, int m) {
        auto even = [&](int x) { return x / 2; };
        auto odd = [&](int x) { return (x + 1) / 2; };
        return 1LL * even(n) * odd(m) + 1LL * odd(n) * even(m);
    }
};

解法：模拟

枚举每条对角线，按题意模拟即可。复杂度 $\mathcal{O}(n^2\log n)$。

参考代码（c++）

class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        // 枚举左下角三角形的对角线
        for (int i = 0; i < n; i++) {
            vector<int> vec;
            for (int k = 0; i + k < n; k++) vec.push_back(grid[i + k][k]);
            sort(vec.begin(), vec.end(), greater<int>());
            for (int k = 0; i + k < n; k++) grid[i + k][k] = vec[k];
        }
        // 枚举右上角三角形的对角线
        for (int j = 1; j < n; j++) {
            vector<int> vec;
            for (int k = 0; j + k < n; k++) vec.push_back(grid[k][j + k]);
            sort(vec.begin(), vec.end());
            for (int k = 0; j + k < n; k++) grid[k][j + k] = vec[k];
        }
        return grid;
    }
};

解法：枚举

按题意枚举每个矩形并判断即可。可以改成记录对角线长度的平方，避免浮点数运算。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        int ans1 = 0, ans2 = 0;
        for (auto &rect : dimensions) {
            int len = rect[0] * rect[0] + rect[1] * rect[1];
            int area = rect[0] * rect[1];
            if (len > ans1) ans1 = len, ans2 = area;
            else if (len == ans1 && area > ans2) ans2 = area;
        }
        return ans2;
    }
};

解法：枚举

经典题。求包含所有点的，边与坐标轴平行的矩形的最小面积。

矩形的上（下）边界即为所有点中纵坐标最大（小）的，矩形的左（右）边界即为所有点中横坐标最大（小）的。枚举所有点计算边界即可。复杂度 $\mathcal{O}(nm)$。

参考代码（c++）

###cpp

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int U = n, D = -1, L = m, R = -1;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j]) {
            U = min(U, i); D = max(D, i);
            L = min(L, j); R = max(R, j);
        }
        return (D - U + 1) * (R - L + 1);
    }
};