首页 > 试题广场 >

翻之

[编程题]翻之
  • 热度指数:3617 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 1024M,其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 nm 列的矩阵,每一个元素要么是 \texttt{`0'},要么是 \texttt{`1'}
\hspace{15pt}每一轮,你可以进行一次以下操作:
\hspace{23pt}\bullet\,选择一行的元素,将其全部反置,即 \texttt{`0'} 变为 \texttt{`1'}\texttt{`1'} 变为 \texttt{`0'}
\hspace{15pt}请你帮助小歪判断,若能进行任意多轮操作(也可以不进行操作),至多能使得多少列的元素均为 \texttt{`1'}。你只需要输出这个最大值。

输入描述:
\hspace{15pt}第一行输入两个正整数 n,m\left(1\leqq n,m\leqq 3 \times 10^3\right) 代表矩阵的行数和列数。
\hspace{15pt}此后 n 行,每行输入一个长度为 m 、仅由 \texttt{`0'}\texttt{`1'} 构成的字符串,代表矩阵每一行中的元素。


输出描述:
\hspace{15pt}输出一个整数,表示至多能使得多少列的元素均为 \texttt{`1'}
示例1

输入

3 4
1111
1111
1111

输出

4

说明

\hspace{15pt}在这个样例中,不需要进行操作,所有列的元素均为 \texttt{`1'}
示例2

输入

3 2
01
10
11

输出

1

说明

\hspace{15pt}在这个样例中,我们可以选择对第一行进行操作,使得第一行变为 \texttt{,此时,第一列的元素均为 \texttt{`1'}
n,m = list(map(int,input().split()))
s = ''
dic ={}
for i in range(n):
    s = s+input()
for i in range(m):
    x = s[i::m]
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1
print(max(dic.values()))

发表于 2025-06-09 16:57:41 回复(0)
n,m = map(int,input().split())
matrix = []
for i in range(n):
    matrix.append(input())

dic = {}
for j in range(m):
    tmp = ''
    for k in range(n):
        tmp += matrix[k][j]
    if tmp not in dic.keys():
        dic[tmp] = 1
    else:
        dic[tmp] += 1

print(max(dic.values()))
发表于 2025-03-21 14:59:36 回复(6)
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 读取n和m
	var n, m int
	fmt.Fscan(reader, &n, &m)

	// 读取矩阵
	matrix := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &matrix[i])
	}

	// 统计每列字符串的出现次数
	count := make(map[string]int)

	// 使用strings.Builder来构建列字符串
	var sb strings.Builder
	sb.Grow(n) // 预分配空间

	for j := 0; j < m; j++ {
		sb.Reset()
		for i := 0; i < n; i++ {
			sb.WriteByte(matrix[i][j])
		}
		count[sb.String()]++
	}

	// 找出最大值
	max := 1
	for _, v := range count {
		if v > max {
			max = v
		}
	}

	fmt.Println(max)
}

发表于 2025-04-08 09:20:55 回复(1)
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
/**
*   不要误区在这个选择一行元素反置这里
*   这里直接将每列元素放到无序的map中,统计相同的数量即为所求
*/
int solve(vector<string> hash, int n, int m) {
    int num_count = 0;
    unordered_map<string, int> m_map;
    for(int i = 0; i < m; i++) {
        string s;
        for (int j = 0; j < n; j++) {
            s += hash[j][i];
        }
        m_map[s]++;
    }

    return max_element(m_map.begin(), m_map.end(), [](const auto &it1, const auto &it2){
        return it1.second < it2.second;
    })->second;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> hash(n);
    for (int i = 0;  i < n; i ++) {
        cin >> hash[i];
    }
    int out = solve(hash, n, m);
    cout << out << endl;
}
// 64 位输出请用 printf("%lld")

发表于 2025-10-21 22:37:52 回复(0)
难受,用golang超时。
package main

import (
    "fmt"
)

func main() {
    var n, m int
    fmt.Scanf("%d %d", &n, &m)

    grid := make([]string, n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%s", &grid[i])
    }

    colBytes := make([]byte, n) // 复用
    count := make(map[string]int)

    for j := 0; j < m; j++ {
        for i := 0; i < n; i++ {
            colBytes[i] = grid[i][j]
        }
        count[string(colBytes)]++
    }

    maxCount := 0
    for _, c := range count {
        if c > maxCount {
            maxCount = c
        }
    }

    fmt.Println(maxCount)
}


发表于 2025-09-06 21:55:02 回复(0)
import sys

n,m = map(int,input().split())
matrix = []
for i in range(n):
    matrix.append([int(i) for i in input()])

way = []
for i in range(1<<n):
    way.append(bin(i)[2:])

def count_li(ma):
    count = 0
    sum = 0
    for j in range(m):
        for i in range(n):
            if ma[i][j] == 1:
                count += 1
        if count == n:
            sum += 1
            count = 0
        else:
            count = 0
    return sum

def reverse(s):
    res = matrix.copy()
    for i in range(len(s)):
        for j in range(m):
            if s[i] == "1":
                res[i][j] = 1-res[i][j]
    ans = count_li(res)
    return ans

dic = {v:reverse(v) for v in way}
print(max(dic.values()))
发表于 2025-08-04 18:45:49 回复(0)
// 遍历每一列,每一列的字符组成一个字符串,相同的字符串可以在变换的情况下是的全为 1
// 不同的字符串不可能通过变换使得全为 1  ( 能发现这一点就好了 ) 引用一个c++大佬写的注释
// 只需要统计每列字符串相同的数量就行
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 读取输入
let dp = []
let condition = undefined;
rl.on("line", function (line) {
    if(!condition){
        condition = line.split(" ").map(Number)
        // [1,1,1,1]
        dp = new Array(condition[1]).fill(1)
    }else{
        let arr = line.split('');
        for(let i=0; i<arr.length; i++){
            // 不能用字符串拼接,不然运算会超时
            // 把dp中所有的掩码往左移一位这时候每一列都一样
            // 然后再和输入的这列中的数 0 或 1进行 或运算后就得到一个不一样的唯一数
            dp[i] = (dp[i]<<1) | Number(arr[i])
        }
    }
}).on("close", function() {
    // 把相同列用位运算做统计
    let countMap = {} 
    for(let i=0; i<dp.length; i++){
        if(countMap[dp[i]]){
            countMap[dp[i]]++
        }else{
            countMap[dp[i]] = 1
        }
    }

    // 找出对象中最大的值
    let sum = 0
    Object.keys(countMap).forEach(key=>{
        if(countMap[key]>sum){
            sum = countMap[key]
        }
    })
    console.log(sum)
})

发表于 2025-07-23 18:27:00 回复(0)
把矩阵保存到数组里,遍历数组的每一列,若列字符串相等,说明无论翻转哪几行,这两个字符串始终都是相同的(能把它翻转为全为1),记录相等列字符串的最大值即为所求。
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            int rows = in.nextInt();
            int cols = in.nextInt();
            in.nextLine();
            int res = 0;
            String[] row = new String[rows];
            for (int i = 0; i < rows; i++){
                row[i] = in.nextLine();
            }
            HashMap<String, Integer> map = new HashMap<>();
            for (int j = 0; j < cols; j++){
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < rows; i++){
                    sb.append(row[i].charAt(j));
                }
                String s = sb.toString();
                map.merge(s, 1, Integer :: sum);
                res = Math.max(res, map.get(s));
            }
           
            System.out.println(res);
        }
}

发表于 2025-07-21 17:00:33 回复(0)
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;

    vector<string> vec;
    for(int i=0; i<n; i++) {
        string str;
        cin >> str;
        vec.push_back( str );
    }

    unordered_map<string, int> ord_map;
    for ( int i = 0; i < m; i++ ) {
        string s;
        for ( int j = 0; j < n; j++ ) {
            s += vec[j][i];
        }
        ord_map[s]++;
    }

    int res = 0;
    for (auto map : ord_map) {
        res = max( res, map.second );
    }

    cout << res << endl;
    return 0;
}


发表于 2025-05-08 04:28:53 回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));

    string line;
    for (int i = 0; i < n; i++) {
        cin >> line;
        for (int j = 0; j < m; j++) {
            matrix[i][j] = line[j] - '0';
        }
    }

    unordered_map<string, int> count;

    for (int i = 0; i < m; i++) {
        string str;
        for (int j = 0; j < n; j++) str += to_string(matrix[j][i]);
        count[str]++;
    }

    auto max_it = max_element(count.begin(),
    count.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
        return a.second < b.second;
    });

    cout << max_it->second << endl;
    return 0;
}
发表于 2025-04-09 10:47:05 回复(0)
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
//通过分析可知 本题变为 按照每一列的初始值 这样的列去统计次数 次数最多的值就是列全为1的值

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        in.nextLine();
        String[] row = new String[n];
        for (int i = 0; i < n; i++) {
                row[i] = in.nextLine();
            }
        //x为原数据数组 是按行排列的 现在改为按列排列
        Map<String,Integerz = new HashMap<>();
        for(int j = 0;j<m;j++){
            StringBuilder y = new StringBuilder();//每个列处理出来 然后记录哈希比较
            for(int i = 0;i<n;i++){
                y.append(row[i].charAt(j));
            }
            //这里 得到一列就添加进hashmap中一列处理掉
            String key = y.toString();
            z.put(key,z.getOrDefault(key,0)+1);
        }
        int count = 0;
        for(int k:z.values()){
            count = Math.max(count,k);
        }
        System.out.println(count);
    }
}
发表于 2025-03-16 13:16:58 回复(1)

EASY

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> array(n);
    for (int i = 0; i < n; ++i)
        cin >> array[i];

    unordered_map<string, int> map;
    for (int i = 0; i < m; ++i) {
        string s;
        for (int j = 0; j < n; ++j)
            s += array[j][i];
        ++map[s];
    }

    int max = max_element(map.begin(), map.end(), [](const auto & a,
    const auto & b) {
        return a.second < b.second;
    })->second;

    cout << max;
}
发表于 2025-03-07 13:13:37 回复(0)