藍橋杯 算法訓練 審美課

藍橋杯記錄

算法訓練 審美課

問題描述

　　《審美的曆程》課上有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。

解題思路

最最開始是想把所有的答案存放起來，然後再一一對比，看了資料規模馬上就知道不可行。

然後想到用一個HashMap來存放答案，把答案存成String類型，相同的答案就值加一，這樣隻要判斷答案是否相反，然後把值相乘就可以，但是String類型再處理進行對比還是有點麻煩的，雖然寫出來了但并不知道為什麼第一行資料讀取不到，為空。

以下為第一次嘗試的代碼

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 審美課 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int stu = in.nextInt();
		int paint = in.nextInt();
		int[] answ = new int[stu];
		Map<String,Integer> answers = new HashMap<String,Integer>();
		for(int i=0;i<stu;i++) {
			String str = in.next();
			if(answers.containsKey(str)) {
				answers.put(str, answers.get(str)+1);
			}
			else answers.put(str, 1);
		}
		in.close();
		int sum =0;
		int sum1=0;
		int sum2=0;
		for(Map.Entry<String, Integer> entry : answers.entrySet()) {
			String strs = entry.getKey();
			char[] chs = strs.toCharArray();
			for(Map.Entry<String, Integer> entry2 : answers.entrySet()){
				String strs2 = entry2.getKey();
				char[] chs2 = strs2.toCharArray();
				for(int i=0;i<paint*2;i++) {
					if((chs[i]==1|chs[i]==0) && (chs2[i]==1|chs2[i]==0)) {
						if(chs[i]==chs2[i]) {
							break;
						}
						else {
							if(i==paint*2-1) {
								sum+=entry.getValue()*entry2.getValue();
							}
						}
					}
					
				}
			}
		}
		System.out.println(sum);
}
           

測試用例都沒有通過，讀不到第一行的1 0。

後來還是百度了一下， 讀了幾篇大佬們的文章，主要參考如下：

算法訓練 審美課 java – Nicolas Lee

https://blog.csdn.net/qq_42835910/article/details/87448444

首先是原本隻知道Scanner這種方法，而文章裡用的是InputStreamReader來讀取字元流資料，應該是輸入資料規模很大的時候會用到，效率更高。

其次是可以用二進制來表示每位同學的回答。太妙了，答案都是1或0，完全可以用二進制來表示，而且因為m<=20，還不會出現超出int範圍的情況。

還有是移位運算符和異或運算符，是學過但是從來沒有用過的東西，這次算是熟悉一下。

再自己整理一下解題思路：

1.因為資料龐大，是以用字元流來讀寫資料。

2.答案用二進制來表示，其相反的答案用其二進制表達與m個1的數maxn取異或（^）得到。

3.此外，由于maxn^ x = maxn-x = y (x,y屬于[0,maxn]），maxn與x取異或實際就是逐位做減法，例如：111-010 = 111 = 111 ^ 010 ，maxn = 7, 7 ^ 0=7 - 0 = 7、7 ^ 1=7-1=6、7 ^ 2=7-2=5 。是以周遊maxn/2長度的HashMap就可以，後半段的答案肯定已經得到過了。

完整代碼如下

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.HashMap;
import java.util.Map.Entry;

public class 審美課2 {
	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> ans = new HashMap<Integer,Integer>(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;
			}
			ans.put(num, ans.containsKey(num) ? ans.get(num)+1 : 1);
		}
		int sum = 0, maxn = (1<<m)-1;
		for(Entry<Integer,Integer> entry : ans.entrySet()) {
			if(maxn/2 < entry.getKey()) continue;
			int key = entry.getKey()^maxn;
			if(ans.containsKey(key)) 
				sum+=ans.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){
			e.printStackTrace();
		}
		return res;
	}
}