AcWing 3814. 矩阵变换

原题链接

题目描述

给定一个 $n×n$ 的 $01$ 矩阵。

你可以选择若干列（也可以不选），并将这些列上的所有元素进行变换（$1$ 变 $0$，$0$ 变 $1$）。

你的目标是使得矩阵中有尽可能多的行满足：一行中的所有元素都为 $1$。

输出可以得到的满足条件的行的最大数量。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个长度为 $n$ 的 $01$ 字符串，表示整个矩阵。

输出格式

输出可以得到的满足条件的行的最大数量。

数据范围

$1≤n≤100$

样例

输入样例1：

4
0101
1000
1111
0101

输出样例1：

2

输入样例2：

3
111
111
111

输出样例2：

3

思路

可以发现，不同的字符串不可能在同样的操作下同时变为全 $1$ 字符串。所以只要找出出现次数最多的字符串，将这个类串中的 $0$ 改为 $1$ 即可。

代码

C++

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<string, int> S;
    int n, res = 0;
    string s;
    cin >> n;
    for ( int i = 0; i < n; i ++ )
    {
        cin >> s;
        res = max(res, ++ S[s]);
    }
    cout << res << endl;
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        Map<String, Integer> S = new HashMap<>();
        int n = in.nextInt(), res = 0;
        String s;
        for ( int i = 0; i < n; i ++ )
        {
            s = in.next();
            int cnt = S.getOrDefault(s, 0);
            S.put(s, cnt + 1);
            res = Math.max(res, cnt + 1);
        }
        System.out.printf("%d\n", res);
    }
    
}