欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现 蓝桥杯 算法训练 审美课

程序员文章站 2022-06-26 11:56:14
...

算法训练 审美课
时间限制: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;
	}
}