CodeForces 554B（掃房間），codeforces554b

                             CodeForces 554B

Description

Ohana Matsumae is trying to clean a room, which is divided up into an n by n grid of squares. Each square is initially either clean or dirty. Ohana can sweep her broom over columns of the grid. Her broom is very strange: if she sweeps over a clean square, it will become dirty, and if she sweeps over a dirty square, it will become clean. She wants to sweep some columns of the room to maximize the number of rows that are completely clean. It is not allowed to sweep over the part of the column, Ohana can only sweep the whole column.

Return the maximum number of rows that she can make completely clean.

Input

The first line of input will be a single integer n (1 ≤ n ≤ 100).

The next n lines will describe the state of the room. The i-th line will contain a binary string with n characters denoting the state of the i-th row of the room. The j-th character on this line is '1' if the j-th square in the i-th row is clean, and '0' if it is dirty.

Output

The output should be a single line containing an integer equal to a maximum possible number of rows that are completely clean.

Sample Input

4
0101
1000
1111
0101

2

3
111
111
111

3

題解：給定一個由n*n塊地磚鋪成的房間，每塊磚用0表示未打掃，1表示已打掃。要求每次打掃只能掃一整列地磚，對於其中的地磚未打掃的會變為已打掃，已打掃的會變為未打掃。即1會變成0，而0會變成1，求一種打掃方案，使得打掃完後整行地磚均為已打掃的行數最大。

看似無解，實則有解，其實很簡單。。

首先，可以看出，如果兩行地磚狀態完全相同，那麼無論如何打掃，這兩行地磚的狀態始終都是完全相同的（因為打掃的時候必須打掃整列）。倒過來想，假設打掃完後某些行的地磚處於整行為1，那麼打掃之前這些行的對應列的地磚狀態也是完全相同的。那麼既然我們要使最後整行為1的行數最大，實際上就是求開始時整行地磚處於相同狀態的行數最大。將整行看做一個字符串，直接用map實現。記錄出現次數最多的字符串。

#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;  
char a[102][102];  
int max(int x,int y)
{
if (x<y)
  return y;
 else
  return x;
}
int main()  
{  
    int n,i,j,k = 0;  
    scanf("%d",&n);  
    for(i = 1;i<=n;i++)  
    {  
        scanf("%s",a[i]);  
    }  
    for(i=1;i<=n;i++)  
    {  
        int s=0;  
        for(j=1;j<=n;j++)  
        {  
            if(strcmp(a[i],a[j])==0) //比較兩個數組 
                s++;  
        }  
        k = max(k,s);  
    }  
    printf("%d\n",k);  
	return 0;
}