【藍橋杯】 算法訓練 審美課

問題描述

　　《審美的曆程》課上有 n n n位學生，帥老師展示了 m m m幅畫，其中有些是梵高的作品，另外的都出自五歲小朋友之手。老師請同學們分辨哪些畫的作者是梵高，但是老師自己并沒有答案，因為這些畫看上去都像是小朋友畫的……老師隻想知道，有多少對同學給出的答案完全相反，這樣他就可以用這個資料去揭穿披着皇帝新衣的抽象藝術了（支援帥老師 _）。

　　答案完全相反是指對每一幅畫的判斷都相反。

輸入格式

　　第一行兩個數 n n n和 m m m，表示學生數和圖畫數；

　　接下來是一個 n ∗ m n*m n∗m的 01 01 01矩陣 A A A：

　　如果 a i j = 0 aij=0 aij=0，表示學生 i i i覺得第 j j j幅畫是小朋友畫的；

　　如果 a i j = 1 aij=1 aij=1，表示學生 i i i覺得第 j j j幅畫是梵高畫的。

輸出格式

　　輸出一個數 a n s ans ans：表示有多少對同學的答案完全相反。

樣例輸入

3 2

1 0

0 1

1 0

樣例輸出

2

樣例說明

　　同學1和同學2的答案完全相反；

　　同學2和同學3的答案完全相反；

　　是以答案是2。

資料規模和約定

　　對于50%的資料： n n n<=1000；

　　對于80%的資料： n n n<=10000；

　　對于100%的資料： n n n<=50000， m m m<=20。

個人思路：由于輸入的每一行都是0或者1，那麼可以考慮将每一行的輸入看成一個二進制數，采用位運算進行處

首先把第i個同學給出的答案由二進制轉換為數字，存入一個數組 m p [ a [ i ] ] mp[a[i]] mp[a[i]]【 a [ i ] a[i] a[i]為二進制轉換成的數字, m p [ a [ i ] ] mp[a[i]] mp[a[i]]即代表這個答案的個數】，該數組是用來記錄相同的答案個數，然後将 a [ i ] a[i] a[i]與 t t t【 t t t表示 m m m個 1 1 1的資料】進行異或得到d(這裡異或得到與第i個同學給出的答案相對的結果0，然後查找 m p mp mp中下标為 d d d的個數，就能計算出相反答案的個數

需要注意的是這裡沒有排除重複計算，最後得出的結果是答案的2倍，輸出時需要/2

#include <iostream>
using namespace std;
int a[50005];
int mp[2000000];
int ans;
int n,m;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int temp;
			cin >> temp;
			a[i] = (a[i] << 1) + temp;
		}
		mp[a[i]]++;
	}
	int t = (1 << m) - 1;  //得到全1數
	for (int i = 0; i < n; ++i) {
		int d = a[i] ^ t;  //異或
		ans += mp[d];
	}
	cout << ans / 2 << endl;
	return 0;
}