Java實作 藍橋杯 算法訓練 審美課

算法訓練 審美課

時間限制：1.0s 記憶體限制：256.0MB

送出此題

問題描述

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

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

輸入格式

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

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

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

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

輸出格式

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

樣例輸入

3 2

1 0

0 1

1 0

樣例輸出

2

樣例說明

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

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

　　是以答案是2。

資料規模和約定

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

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

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

分析：0,1相反異或^即可。題目輸入資料很大，需要用字元流來讀寫資料。不然會逾時。

思路：用二進制表示每位同學的回答（狀壓）。（m<=20;2^20 在int的範圍内）。相反的答案用二進制與m個1,1,1…1（即2^m-1）的數maxn取異或即可。（如 01 == 1 ，10 == 2，2^3 == 1（異或），1^3 == 2 ）。

提高效率：map周遊可以取0~maxn/2即可。。設m個1,1,1…1（即2^m-1）的數為maxn，mid = maxn/2; 通過枚舉你會發現 maxn^x = maxn-x = y (x,y屬于[0,maxn]），(maxn與x逐位取異或 實際就是逐位做減法，因為maxn全為1（1>={0,1}），不存在減法借位),如（111-010 = 101 = 111^010）,則[0,mid]的一個數x與maxn取異的值y一定在(mid,maxn]中。如(maxn = 7, 7^0=7 - 0 = 7、71=7-1=6、72=7-2=5).如果你周遊了map中的[0mid]那麼後面的就不需要再周遊了，因為後面map中能與[0mid]比對的值肯定已經被比對過了。此步驟可要可不要，不會影響實際的通過。

Tips:這裡使用了io流進行優化,看中細節的小夥伴可以看一看io軟體包 ---------------------

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.HashMap;
import java.util.Map.Entry;
 
public class Main {
	private static Reader reader;
 
	public static void main(String[] args) {
		reader = new InputStreamReader(System.in);
		int n, m;
		n = getInt();
		m = getInt();
		HashMap<Integer, Integer> hm = new HashMap<>(n);
		for (int i = 0; i < n; ++i) {
			int num = 0, x = 0;
			for (int j = 0; j < m; j++) {
				x = getInt();
				num = (num << 1) + x;
			}
			hm.put(num, hm.containsKey(num) ? hm.get(num) + 1 : 1);
		}
		int sum = 0, maxn = (1 << m) - 1;
		for (Entry<Integer, Integer> entry : hm.entrySet()) {
			if (maxn / 2 < entry.getKey())
				continue;
			int key = entry.getKey() ^ maxn;
			if (hm.containsKey(key))
				sum += hm.get(key) * entry.getValue();
		}
		System.out.println(sum);
	}
 
	public static int getInt() {
		int res = 0, read;
		try {
			while ((read = reader.read()) != -1) {
				if (Character.isDigit(read)) {// 因為全是非負數，不需要判斷負号‘-’,隻要是數字就行
					res = read - '0';
					while ((read = reader.read()) != -1) {// 繼續得到能得到的數字
						if (Character.isDigit(read)) {
							res = res * 10 + (read - '0');
						} else {
							break;
						}
					}
					break;
				}
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return res;
	}
}