首页 > 试题广场 >

混合颜料

[编程题]混合颜料

热度指数：12836 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

你就是一个画家！你现在想绘制一幅画，但是你现在没有足够颜色的颜料。为了让问题简单，我们用正整数表示不同颜色的颜料。你知道这幅画需要的n种颜色的颜料，你现在可以去商店购买一些颜料，但是商店不能保证能供应所有颜色的颜料，所以你需要自己混合一些颜料。混合两种不一样的颜色A和颜色B颜料可以产生(A XOR B)这种颜色的颜料(新产生的颜料也可以用作继续混合产生新的颜色,XOR表示异或操作)。本着勤俭节约的精神，你想购买更少的颜料就满足要求，所以兼职程序员的你需要编程来计算出最少需要购买几种颜色的颜料？

输入描述:

第一行为绘制这幅画需要的颜色种数n (1 ≤ n ≤ 50)
第二行为n个数x_i(1 ≤ x_i ≤ 1,000,000,000)，表示需要的各种颜料.

输出描述:

输出最少需要在商店购买的颜料颜色种数，注意可能购买的颜色不一定会使用在画中，只是为了产生新的颜色。

示例1

输入

3
1 7 3

输出

算法知识视频讲解

Java

jade_liu_123

import java.util.*;
import java.io.*;
public class Main {
    /**
    *矩阵论中的知识表明，最大线性无关组是解的最基本的形式。
    *这个题目类似于求矩阵的最大线性无关组，用高斯消元法就可以了，正向算一遍即可，反向不用计算（我们只关心无关组的向量个数，不关心具体解的形式）。
    *多元方程，我们从左到右不为零开始消元，对于二进制数，那就是从大的数开始就可以了。
    *用一个函数判断每一位是否为零，为零才消元。遍历的时候注意方程有几个，我们每次遍历的目标是消灭一列的1，使每一列最多1个一，
    *但是方程不够的时候，就不必向下消了，已经可以结束了。
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] arrColor = new int[n];
        String[] arrInput = br.readLine().trim().split(" ");
        for (int i=0; i<n; i++) {
            arrColor[i]  = Integer.parseInt(arrInput[i]);
        }
        Arrays.sort(arrColor);//排序
        int computLoopCnt = 0;//记录循环的个数
        for (int i=31; i>=0; i--) {//遍历每一位，最大的数的该位为零就跳过
            int row = (n - 1) - computLoopCnt;
            if (row <= 0) {//如果行数不够了，直接停止
                break;
            }
            if (isNbitIsOne(arrColor[row],i)) {//判断该为是否为零
                computLoopCnt++;
                for (int j=row-1; j>=0; j--) {
                    if (isNbitIsOne(arrColor[j],i)) {
                        arrColor[j] = arrColor[row] ^ arrColor[j];
                    }
                }
                Arrays.sort(arrColor, 0, row );//每次计算后排序，因为异或后可能变大，要正确找到最大的
            }
        }
        int baseNum = 0;
        for (int i=0; i<n; i++) {
            if (arrColor[i] != 0) {
                baseNum++;
            }
        }
        System.out.println(baseNum);
    }
    public static boolean isNbitIsOne(int a, int n) {//判断第n位（顺寻方向：自右向左）是否为零
        if (n > 32) {
            throw new IllegalArgumentException();
        }
        int test = 1 << n;
        boolean isOne = false;
        if (test == (a & test)) {
            isOne = true;
        }
        return isOne;
    }
}

发表于 2018-11-06 12:22:58 回复(0)

Java

Dream offer

程序搬运工

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=n-1;i>0;--i){
            Arrays.sort(arr,0,i+1);
            for(int j=i-1;j>=0;--j){
                if((arr[i]^arr[j])<arr[j]){
                    arr[j]^=arr[i];
                }
            }
        }
        int count=0;
        for(count=0;arr[count]==0;++count);
        System.out.println(n-count);
    }
}

发表于 2018-07-24 15:33:08 回复(0)

Java

傻傻傻傻

/**
 * 思路：前面高票答案都说了，其实题目的本质是求矩阵的秩，矩阵中的每个
 * 向量即为每个数的二进制形式。但是矩阵秩的求法是加减运算（高斯消元法），
 * 而此题不同之处在于：以异或运算来代替加减运算。
 */
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int count = in.nextInt();
            int[] array = new int[count];
            for (int i = 0; i < count; i++)
                array[i] = in.nextInt();
            Arrays.sort(array);
            for (int i = count - 1; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--)
                    if ((array[i] ^ array[j]) < array[j])
                        array[j] ^= array[i];
            }
            int res = 0;
            for (int i = 0; i < count; i++) {
                if (array[i] != 0) res++;
            }
            System.out.println(res);
        }
    }
}

编辑于 2018-01-10 14:24:09 回复(0)

Java

安顾

//化上三角，求01矩阵的秩，只是操作是异或
//O(n^2) 每次取最大的数换到上面，然后下面的数去清除当前的最高位，再取清除后数中的最大，置换循环
import java.util.*;
public class Main {    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int[] a = new int[n];
            int maxi = 0;
            for(int i=0;i<n;i++){
                a[i] = input.nextInt();
                if(a[maxi]<a[i]) maxi = i;
            }
            swap(0,maxi,a);
            for(int b=0;b<n-1;b++){
                maxi = -1;
                for(int i=b+1;i<n;i++){
                    if((a[i]^a[b])<a[i]){
                        a[i] = a[i]^a[b];
                    }
                    if(maxi==-1||a[maxi]<a[i]) maxi = i;
                }
                swap(b+1,maxi,a);
            }
            int ans = 0;
            for(int i=0;i<n;i++){
                //System.out.println(Integer.toBinaryString(a[i]));
                if(a[i]>0) ans++;
            }
            System.out.println(ans);
        }
    }
    public static void swap(int i,int j,int[] a){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

发表于 2017-08-30 15:47:13 回复(0)

Java

StudyOfSlagD

/**
 * 综合了以上很多的见解
 * 数组从小到大排列，从最下面一行开始，每次消去最高位的1，比如A行的系数减去B行，直接A = A^B就行
 */
import java.util.*;
public class Main1 {
     
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int n = scan.nextInt();
            int[] col = new int[n];
            for(int i=0; i<n; i++){
                col[i] = scan.nextInt();       
            }
            Arrays.sort(col);
            int count = 0;
            for(int i=n-1; i>=0; i--){
                for(int j=i-1; j>=0; j--){
                	/**
                	 * 如果两者的最高位相同，说明最高位可以消掉，
                	 * 将两者 xor ，或者说将矩阵两行相减消掉最高位 
                	 */
                    if(highbit(col[i]) == highbit(col[j])){
/**           			 如果两个最大数的最高位可以消掉，那么消除之后，最大数已被消掉，没有用了
           			 如果两个最大数的最高位不可以消掉，那么结果＋ 1 ，最大数也没有用了。 */
                        col[j] = col[j] ^ col[i];
                    }
                }
                Arrays.sort(col);
            }
            for(int i=0 ;i<n;i++)
                if(col[i] !=0){
                    count ++;
            }
            System.out.println(count);
        }
    }
    public static int highbit(int x){
    	/*一个数是由32位表示的，那么我们可以把一个数看成是32维空间的一个向量。最后形成了一个n*32的矩阵*/
        for(int i=31;i>=0;i--)
        {
        	//相同则结果为0，不同则结果为1
           int m = (x>>i)&1;
           if(m != 0)
               return i+1;//找到高位，而不是i
        }
        return 0;
    }

}

编辑于 2016-08-29 08:44:42 回复(0)

Java

牛客643001号


	
	
		
		
			
		

	


import java.io.*;
import java.util.*;
public class Main
   {
     public static void main(String[] args) {
          
         mixedColour();
     }
      public static void mixedColour()
    {
        Scanner scanner=new Scanner(System.in);
        int num=scanner.nextInt();
        Integer[] colour=new Integer[num];
        int index=0;
        //注意不能写成 scanner.hasNextInt() && index<num，这样的话会先执行scanner.hasNextInt()，然后一直等待输入
        while(index<num && scanner.hasNextInt())
        {
            colour[index]=scanner.nextInt();
            index++;
        }
        HashSet<Integer> allColour=new HashSet<Integer>();
        int count=0;
        for(int i=0;i<colour.length;i++)
        {
            if(allColour.contains(colour[i]))
            {
                continue;
            }
            HashSet<Integer> tmpColour=new HashSet<Integer>();
            tmpColour.add(colour[i]);
            for(int tmp:allColour)
            {
                tmpColour.add(tmp^colour[i]);
            }
            allColour.addAll(tmpColour);
            count++;
            if(allColour.containsAll(Arrays.asList(colour)))
            {
                System.out.println(count);
                break;
            }
        }
    }
}
各位大神可以看看我这思路对吗？本地调试可以通过但是牛客网上超时，如果思路对的话有没有啥子优化方法呢？

编辑于 2016-08-16 11:39:20 回复(1)