Buckle practice - 27 score after turning the matrix

27 Score after flipping the matrix

1. Problem description
There's a two-dimensional matrix A , The value of each of these elements is 0 or 1 .

Flipping refers to selecting any row or column , And convert each value in the row or column ： Will all 0 All changed to 1, Will all 1 All changed to 0.

After making any number of flips , Explain each line of the matrix as a binary number , The score of the matrix is the sum of these numbers .

Return as high a score as possible .

Example ：

Input ：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

Output ：39

explain ：

Convert to [[1,1,1,1],[1,0,0,1],[1,1,1,1]]

0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

2. Enter description
First, enter the number of rows of the matrix m、 Number of columns n,

Then input m That's ok , Each row n A digital , Every number is 0 or 1.

1 <= m <= 20

1 <= n <= 20
3. The output shows that
Output an integer
4. Example
Input
3 4
0 0 1 1
1 0 1 0
1 1 0 0
Output
39
5. Code

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

int traverse_score(vector<vector<int>>&nums)
{
    
	// thought ： Given a flipping scheme , Then after any exchange order between them , The results obtained remain unchanged . therefore , We can always consider all row flipping first , Consider all column flips .
	// Row flipping ： In order to get the highest score , The leftmost number in each row of a matrix must be  1, Therefore, the leftmost number of each line can be 0 All are flipped to 1
	// Column flip ： When you change the leftmost number in each row to  1  after , You can only flip Columns  ; Scan all columns after the first column , Let each column  1 As many as possible 
	// Scan every column except the leftmost column , If the column  0  More than  1  Number of , Just flip the column , The other columns remain unchanged .

	// Calculate the contribution value of each column to the element  ,  common m That's ok  n Column  , The first column is full of 1 when  , The contribution value is m*2^(n-1)
	// The first j Column  , Elements 1 The number of k ,  The contribution value is  k*2^(n-j-1) 

	int m = nums.size();// Row number 
	int n = nums[0].size();// Number of columns 
	// Contribution value obtained by row flipping 
	//int res = m * (1<<(n - 1)); //int res=m*(1<<(n-1)); 1<< Represents binary numbers 1 Move left one bit to become 10（2）
	int res = m * pow(2, n - 1);
	//int res=m*(2^(n-1));  This output is wrong  , It's written in  int res=m*pow(2,n-1);
	
	for (int j = 1; j < n; j++)// Traverse the other columns after the first column 
	{
    
		int s = 0;// Calculate the contribution value of each column after the first column  , If the column  0  More than  1  Number of , Just flip the column , The other columns remain unchanged .
		for (int i = 0; i < m; i++)// First, make sure that the first column element of each row is 1
		{
    
			if (nums[i][0] == 1)// The first i The elements in the first column of the row are 1
			{
    
				s += nums[i][j];// Calculate the contribution value of this row  【1 The number of 】
			}
			else
				s += (1 - nums[i][j]);// The line is reversed , So the result is 1-nums[i][j] 
	    }  
		int k = max(s, m - s);// use s Statistics 1 The number of ,m-s Statistics 0 The number of  , Understand why this is taking max？  When 0 The number ratio of 1 The number of , Flip  ; Otherwise unchanged , So take max
		res += k * (1<<(n - j - 1));
	}
	return res;
}
 
int main()
{
    
	int n,m,tmp; 
	cin >> n>>m;//n For the number of lines , m Represents the number of columns 
	vector<vector<int>>nums;
	vector<int> temp;
	for (int i = 0; i < n; i++)
	{
    
		temp.clear();
		for (int j = 0; j < m; j++)
		{
    
            cin >> tmp;
			temp.push_back(tmp);
		}
		
		nums.push_back(temp);
	}
	int res = traverse_score(nums);
	cout << res<<endl;
	
	return 0;
}