网易笔试题：混合颜料

你就是一个画家！你现在想绘制一幅画，但是你现在没有足够颜色的颜料。为了让问题简单，我们用正整数表示不同颜色的颜料。你知道这幅画需要的n种颜色的颜料，你现在可以去商店购买一些颜料，但是商店不能保证能供应所有颜色的颜料，所以你需要自己混合一些颜料。混合两种不一样的颜色A和颜色B颜料可以产生(A XOR B)这种颜色的颜料(新产生的颜料也可以用作继续混合产生新的颜色,XOR表示异或操作)。本着勤俭节约的精神，你想购买更少的颜料就满足要求，所以兼职程序员的你需要编程来计算出最少需要购买几种颜色的颜料？  输入描述: 第一行为绘制这幅画需要的颜色种数n (1 ≤ n ≤ 50) 第二行为n个数xi(1 ≤ xi ≤ 1,000,000,000)，表示需要的各种颜料. 输出描述: 输出最少需要在商店购买的颜料颜色种数，注意可能购买的颜色不一定会使用在画中，只是为了产生新的颜色。 输入例子: 29 4096 8192 16384 32768 65536 131072 262144 524288 1048576 16 32 64 128 256 512 1024 2048 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 999999999 1000000000 15 输出例子:

27

思路：将所有的数二进制展开，构成一个矩阵，通过消元只保留对角线上 1，即求矩阵的秩，最后得到 1 的个数即秩的大小，也就是最少需要的颜色数。

C++实现：

#include <iostream> #include <set> #include <vector> const int N = 8 * sizeof(int);// 整型 int 的二进制位数 using namespace std; void getBinaryMat(const set<int>& s, vector<vector<int> >& bMat) {// 求每个数的二进制，存储在vector里面，最后得到二进制矩阵 if(s.empty()) return; for(set<int>::iterator it=s.begin(); it != s.end(); it++) { vector<int> v(N); int flag = 1; for(int i=0; i < N; i++) { v[i] = (*it) & flag; flag <<= 1; } bMat.push_back(v); } } int getNumOfLeastColors(set<int>& colorSet) {// 求二进制矩阵的秩，即消元，最后看斜对角线上有几个 1 if(colorSet.empty()) return -1; vector<vector<int> > bMat; getBinaryMat(colorSet, bMat); const int Row = bMat.size(); int r = 0, c = 0; for(c=0; c < N && r < Row; c++, r++) {// 从每一列开始，将每一列消到只有 1 个 1 或者全 0 int i = 0; for(i = r; i < Row; i++) {// 寻找这一列第一个非 0 的行 if(bMat[i][c] != 0) break; } if(Row == i) --r; else { swap(bMat[r], bMat[i]); for(int k=i+1; k < Row; k++) { if(0 != bMat[k][c]) { for(int j=c; j < N; j++) { bMat[k][j] ^= bMat[r][j];// 用第 r 行的 1 消除这一列上其他所有行的 1 } } } } } return r; } int main() { int n; while(cin >> n) { set<int> colorSet; int color; for(int i=0; i < n; i++) { cin >> color; colorSet.insert(color); } cout << getNumOfLeastColors(colorSet) << endl; } return 0; }