画家购买颜料

package second;

import java.util.Scanner;

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

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

输入例子1:
3
1 7 3

输出例子1:
3

*/
public class FaceTwelve {

public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int n=input.nextInt();
    int[] value=new int[n];
    
    for(int i=0;i<n;i++)
        value[i]=input.nextInt();
    
    /*for(int i=0;i<n-1;i++)
        System.out.print((value[i]^value[i+1])+" ");
    System.out.println(value[0]^value[2]);*/
    System.out.println(getColorNum(value));
    
    input.close();
}

/*
 * 分析： 
    本题的数学意思是根据给出的几个数，要找到最少的数字根据规则
    （异或：相同为0，不同为1）可以得到给出的几个数。
    
    1.根据异或的原则，很容易联想到位运算。例如001,010,100便
    可生成1~7之间的所有数。所以，本题答案的上限应该是最大数字的位数。
    
    2.在给出的N个数中，可能有一些数是可以由其他数字异或生成，
    我们需要找到最“基础”的几个数，也就是由这几个数通过异或运算
    可以生成给出的所有数。那么什么是“基础”的数呢？ 
    回想起矩阵当中的秩：通过矩阵初等变换求出的对角线上的元素个数。
    反应了矩阵元素样本所张成的线性子空间的维数。 
    换言之，只要求出了矩阵的秩，那么通过初等变换是可以还原原始矩阵的。
    
    3.根据上面的分析，我们只需要对给出的数，求出其二进制位矩阵，
    然后做高斯消元，最后得到秩的个数即为需要求的最少的数字个数。*/
public static int getColorNum(int[] value){
    int k=0;//矩阵的秩，即对角线上元素的个数。
    int n=value.length,col=0;
    int bitArray[][]=getBitArray(value);
    
    //高斯消元
    for(col=0;col<32&&k<n;col++,k++){//若有某一列有数则秩加一
        int i=0;
        for(i=k;i<n&&bitArray[i][col]==0;i++); //找到col列的第一个非0元素
        if(i==n){
            k--;//若某一列上均为0 则秩减一
            continue;
        }
        bitArray=changeLine(bitArray,k,i);//交换两行
        for(int j=i+1;j<n;j++){//第一个不为0的数，下方所有数需转换成0
            if(bitArray[j][col]==0)//等于0则跳过
                continue;
            for(int p=col;p<32;p++)
                bitArray[j][p]^=bitArray[k][p];//消元
        }
    }
    
    return k;
}

/*
 * 改变两行之间的关系
 * bitArray 改变的矩阵
 * m n  即交换的两行
 * */
public static int[][] changeLine(int[][] bitArray,int m,int n){
    for(int i=0;i<bitArray[0].length;i++){
        int temp=bitArray[m][i];
        bitArray[m][i]=bitArray[n][i];
        bitArray[n][i]=temp;
    }
    return bitArray;
}


//计算出二进制矩阵
public static int[][] getBitArray(int[] value){
    int n=value.length;
    int[][] bitArray=new int[n][32];
    for(int i=0;i<n;i++){
        for(int j=31;j>=0&&value[i]>0;j--){//从后往前计算第0位的值
            bitArray[i][j]=value[i]&1;
            value[i]>>=1;//向下一位移动，原本0   现在1->以便计算
        }
    }
    return bitArray;
}

}

画家购买颜料

推荐阅读更多精彩内容