蓝桥杯 算法训练 审美课

蓝桥杯记录

算法训练 审美课

问题描述

　　《审美的历程》课上有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;
	}
}