题目描述
N students took a test with M questions with two choices: 0 and 1. You are given N strings of length M each: S1,S2,…,SN. The k-th character of Si is 0 or 1, representing the response of the i-th student to the k-th question. Although we know the response of each student to each question, we do not yet know the correct answer ― 0 or 1 ― to each problem. Find the number of pairs (i,j) satisfying 1≤i<j≤N such that it is impossible for Student i and Student j to have the same number of correct answers.
Constraints
2≤N≤105
1≤M≤20
Si is a string of length M consisting of 0 and 1.
输入
Input is given from Standard Input in the following format:
N M
S1
S2
:
SN
输出
Print the answer.
样例输入 Copy
【样例1】
3 2
00
01
10
【样例2】
7 5
10101
00001
00110
11110
00100
11111
10000
样例输出 Copy
【样例1】
2
【样例2】
10
提示
样例1解释
For example, if the correct answers to the 1-st and 2-nd questions are both 0, Student 2 and Student 3 have the same number of correct answers ― 1. On the other hand, Student 1 and Student 2 never have the same number of correct answers, nor do Student 1 and Student 3.
题意:找出分数一定不相同的学生有多少组
思路:如果学生中有同奇同偶个1, 那么就可以构造出一个方案(假设A的1的数量=X, B中1的数量=Y, 假设X>Y, 把A中的(X-Y)/2个1放到B中为0的位上), 这个方案一定让两个人的最终分数相同, 一个奇一个偶的话改变答案只会让两个人正确题目的数量+2, -2或不变, 不可能达到目的
统计学生中多少个人是奇数个1, 多少个人是偶数个1, 相乘就是答案
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e5+10;
signed main()
{
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
int a = 0, b = 0;
while(n -- )
{
string s;
cin >> s;
int t = 0;
for(int i = 0; i < m; i ++)
if(s[i] == ‘1‘)t ++;
if(t % 2)a ++;
else b ++;
}
cout << a * b << endl;
return 0;
}