翻转矩阵后的得分 图解题解

整行整列随便翻，怎么让每行读成的二进制数加起来最大

给一个只含 0 和 1 的矩阵，一次操作是挑一整行或一整列，把里面 0 变 1、1 变 0，翻几次都行。翻完后每一行读成一个二进制数，比如 1101 就是 13，各行的值相加就是得分。题面给的 grid=[[0,0,1,1],[1,0,1,0],[1,1,0,0]]，最优翻法能拿到 39，求的就是最大得分。

为什么不能只盯着「让 1 尽量多」去翻

一个直觉是让整张矩阵的 1 越多越好，哪行哪列 0 多就翻哪个。可同样是 1，位置不同值差很远：每行最左是最高位，4 列的行里首位的 1 值 8，末位的 1 只值 1。为凑几个末位的 1 放走首位的 1，总分反而下掉，所以数 1 的总数没用，得看每个 1 落在哪一位。

先翻行抢下最高位，再逐列让 1 不少于 0

把翻法拆成固定两步，顺序不能反。第一步只翻行：逐行看首位，首位是 0 就整行翻一次让它变 1，本来是 1 就不动，这样每行最高位都抢到 1、首列全变成 1。这一步是贪心，也就是先拿下最值钱的那一位、不为小的让步。第二步只翻列：首列已全 1 不必再碰，从第二列起逐列数 1 的个数，只要 1 比 0 少就整列翻过来，让这列 1 不少于 0。两步做完得分最大。

翻完行后各列彼此独立，一列的贡献能直接算出来

第一步定下后首列绝不再翻，各列就彼此独立，翻一列动不到别的列。既然独立，每列单独取「1 最多」的方向就是这列最优，合起来就是全局最优。一列翻或不翻只有两种结果：不翻是 cnt 个 1，翻了是 m 减 cnt 个 1，要较大的那个。每个 1 的价值都是这列的位权，也就是第 j 列贡献 2 的 (n 减 j 减 1) 次方(n 为列数)，所以这列添的分就是 max(cnt, m - cnt) 乘位权，矩阵不用真改。

拿题面这张 3×4 矩阵走一遍到 39

先翻行。第 0 行首位是 0，整行翻成 [1,1,0,0]；第 1、2 行首位都是 1，不动，仍是 [1,0,1,0] 和 [1,1,0,0]。

再逐列算，n=4。第 0 列 [1,1,1]，cnt=3，取 max(3,0)=3，位权 2³=8，贡献 24。第 1 列 [1,0,1]，cnt=2，取 max(2,1)=2，位权 2²=4，累计 32。第 2 列 [0,1,0]，cnt=1，取 max(1,2)=2，位权 2¹=2，累计 36。第 3 列 [0,0,0]，cnt=0，取 max(0,3)=3，位权 2⁰=1，累计 39。

另一条验法：翻过 1 少于 0 的第 2、3 列后每行是 1111、1001、1111，即 15、9、15，加起来 39。

两遍扫矩阵就够，行别回头、列别把等号翻反

翻行扫一遍、数列扫一遍，每个格子只碰常数次，时间 O(m·n)；原地做只用几个计数变量，空间 O(1)。翻完行别回头——首列已全是 1，再翻任一行都会把值 8 的最高位弄丢，行只在第一步处理一次。判断列翻不翻时等号别搞反：1 少于 0 才翻、相等不动，写成「1 不少于 0 就翻」会把好列翻坏。边界也想清：单格非 0 即 1，答案就是 1；全 0 矩阵也能靠翻行把首列凑满，得分不会是 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] ^= 1
        ans = 0
        for j in range(n):
            cnt = sum(grid[i][j] for i in range(m))
            ans += max(cnt, m - cnt) * (1 << (n - j - 1))
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                cnt += grid[i][j];
            }
            ans += max(cnt, m - cnt) * (1 << (n - j - 1));
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                cnt += grid[i][j];
            }
            ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
        }
        return ans;
    }
}