CodeForces 554B

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

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

Input

Output

Input

Output

题解：给定一个由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;

}

巴特西

CodeForces 554B（扫房间）

CodeForces 554B

最新文章

热门文章