题解 | 翻之

矩阵行反转求全 '1' 列最大值

• 问题总结：给定 n × m 的 01 矩阵，可以对任意行进行全行反转（0变1, 1变0）。求操作后，最多能使多少列变成全为 '1'。
• 关键限制：n, m <= 3 × 10^3。

解决方案

1. 逻辑原理： 要使多列同时为全 '1'，这些列在初始状态下的“特征”必须是一致的。
2. 关键点：对于第 j 列和第 k 列，如果它们在某一行相同，则它们必须在所有行都相同
3. 更简单的思考：如果我们将每一列看作一个长度为 n 的字符串。对于某一列，我们可以选择“保持原样”或“反转全行”。为了让这列变全 '1'，我们必须反转所有初始为 '0' 的行。
4. 算法步骤：按列统计字符串出现的频率，然后输出最高频率。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String[] grid = new String[n];
        for (int i = 0; i < n; i++) grid[i] = sc.next();

        Map<String, Integer> map = new HashMap<>();
        for (int j = 0; j < m; j++) {
            StringBuilder sb = new StringBuilder();
            // boolean flip = (grid[0].charAt(j) == '0'); // 以第一行为基准归一化
            for (int i = 0; i < n; i++) {
                char c = grid[i].charAt(j);
                sb.append(c);
            }
            String key = sb.toString();
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        int maxCols = 0;
        for (int count : map.values()) maxCols = Math.max(maxCols, count);
        System.out.println(maxCols);
    }
}