这道题的地址网页内推笔试题（二）——混合颜料
题目如下:
屏幕快照 2016-08-18 16.06.59.png
<u>题目翻译理解</u>
ok，这道题翻译过来，就是进行多次输入，每次输入n个数，将这些数之间进行多次xor（异或操作），其中一个数可能被xor多次，看最后能剩余多少不重复的数，输出数量即可。
<u>解题思路</u>
在C++中，将两个数进行xor，用的是^符号，但是实际上是将十进制转换为二进制之后，再进行xor，这样，这n个十进制的数，就被转换成了n个二进制的包含1，0的字符串，将每个数转换成二进制之后单成一行，位数小的前面被补全0，这样这n个数就变成了n行矩阵，由于1 ≤ xi ≤ 1,000,000,000，而2的30次幂是10亿多，所以这个矩阵最大是n＊30的矩阵。
现在将这个矩阵列出来，如：
101010
111010
101101
110110
然后进行行与行之间的xor，其中1^1=0; 0^0=0; 1^0=1; 0^1=1;
有没有发现这种运算很像求矩阵的秩？相同的相减为0，不同的相减为1.
矩阵的秩定义：是其行向量或列向量的极大无关组中包含向量的个数。
矩阵的秩求法：用初等行变换化成梯矩阵, 梯矩阵中非零行数就是矩阵的秩.
所以这道题就被转化成了求矩阵的秩, 求法如下。
//
// main.cpp
// NiuKe_HunHeYanLiao
//
// Created by 麦心 on 16/8/18.
// Copyright © 2016年 程序工匠0_0小姐. All rights reserved.
//
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
//求一个数的二进制的最高位是哪位
int getHighBit(int num){
int highbit = 0;
while (num) {
//将该数的二进制右移一位
num>>=1;
highbit++;
}
return highbit;
}
int main() {
vector<int> colors;
int n;
while(cin >> n){
colors.clear();
int result = 0;
int temp;
int i = n;
while (i--) {
cin>>temp;
colors.push_back(temp);
}
//将colors进行从小到大的排序
sort(colors.begin(), colors.end());
int bigger, smaller;
//bigger和smaller始终指向的是最后一位和倒数第二位数
bigger = n - 1;
smaller = bigger - 1;
while (colors.size()>2) {
//如果两者的最高位相同，说明最高位可以消掉，
//将两者xor，或者说将矩阵两行相减消掉最高位
if(getHighBit(colors[bigger]) == getHighBit(colors[smaller])){
int tem = colors[bigger]^colors[smaller];
//find函数头文件是<algorithm>
//泛型算法的 find，在非string类型的容器里，可以直接找出所对应的元素
//从vector的头开始一直到尾，找到第一个值为temp的元素，返回的是一个指向该元素的迭代器std::vector<int>::iterator类型
//因为现在xor的是两个最大的数，而且最高位已被消掉，所以xor得到的结果一定比这两个数小
//如果temp这个 比最大两个数小的 数没有被找到，则将temp加到colors数组中，进行再次xor
//找不到的话，返回colors.end应该是固定用法
if(find(colors.begin(), colors.end(), tem)==colors.end()){
colors.push_back(tem);
sort(colors.begin(), colors.end());
bigger++;//因为colors中多了一个数，所以需要位数＋1
smaller++;
}
}else{
result++;
}
//如果两者最高位不同，说明已经所有数的最高位已经只有最大的那个数是1了，这样它已经不可能被消掉了，结果＋1
//如果两个最大数的最高位可以消掉，那么消除之后，最大数已被消掉，没有用了
//如果两个最大数的最高位不可以消掉，那么结果＋1，最大数也没有用了。
//弹出最大数
colors.pop_back();
//因为弹出了一个数，所以bigger和smaller都要相应－1
bigger = smaller;
smaller--;
}
cout<<result+colors.size()<<endl;
}
}
提交，用例全部通过。
