混合颜料

//

//  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+2 << endl ;

    }

}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
//求该数最高位是第几位
int getHighPosition(int a){
	int count = 0;
	while (a){
		a >>= 1;
		count++;
	}
	return count;
}
int main(){
	int n;
	vector<int> colors;
	while (cin>>n)
	{
		int temp;
		int res=0;
		int i = n;
		colors.clear();
		while (i--){
			cin >> temp;
			colors.push_back(temp);
		}
		sort(colors.begin(), colors.end());
		//endValue和cmpValue指向最后一个数和倒数第二个数
		int endValue = n-1;
		int cmpValue = endValue - 1;
		//两种颜色以上才有混合的可能，如果只需要两种颜色，那么最少就要购买两种，购买一种是不可能得到两种颜色的。
		while (colors.size()>2)
		{
			//只有最高位相同，那么他们的最高位一定可以消去
			if (getHighPosition(colors[endValue]) == getHighPosition(colors[cmpValue]))
			{
				
				int temp = colors[endValue] ^ colors[cmpValue];
				//如果异或出来的这个低维的颜色没有，就加入到colors里
				if (find(colors.begin(), colors.end(), temp) == colors.end())
				{
					colors.push_back(temp);
					sort(colors.begin(), colors.end());
					//因为新加入了一个数，所以为了让endValue和cmpValue还是指向倒数第一和倒数第二个数，需要++
					endValue++;
					cmpValue++;
				}
			}
			else
			{
				res++;
			}
			//每判断完一次，就把最后一个数扔掉，没什么用了
			colors.pop_back();			
			endValue = cmpValue;
			cmpValue--;	
		}
		cout << res + colors.size() << endl;

	}


}

'''
    说明：以下代码和思路均是参考各位大神，
    本人只做了额外的总结和解释，帮助大家理解。
    
    问题理解：
    输入n个数，将这些数之间进行多次xor（异或操作），
    其中一个数可能被xor多次，看最后能剩余多少不重复的数，输出数量即可。
    
    思路：
    类似矩阵求秩：首先将各数从大到小排序,
    对位数与该行相同的进行异或操作，操作结束后该行就“独立”了。
    
    具体过程如下：
        排序 i=0      异或      排序 i=1    异或
    101010 --> 111010 --> 111010 --> 111010 --> 
    111010 --> 110110 --> 001100 --> 010111 --> 
    101101 --> 101101 --> 010111 --> 010000 --> 
    110110 --> 101010 --> 010000 --> 001100 --> 

        排序 i=2   排序 i=3    排序 i=4 end     
    111010 --> 111010 --> 111010 --> 111010     
    010111 --> 010111 --> 010111 --> 010111     
    000111 --> 001100 --> 001100 --> 001100     
    001100 --> 000111 --> 000111 --> 000111     
    '''

# 求数字转化为2进制后的位数
def getHiBit(n):
    ans = 0
    while n:
        ans += 1
        n >>= 1
    return ans

n = int(input())
colors = list(map(int, input().split()))
colors.sort(reverse=True) # 从大到小排序
i = 0
while i<n and colors[i]:
    hibit = getHiBit(colors[i])
    for j in range(i+1, n):
        if getHiBit(colors[j])==hibit:
            colors[j] ^= colors[i]
        else: break
    colors.sort(reverse=True)
    i += 1
print(i)

def getHiBit(n):
    ans = 0
    while n:
        ans += 1
        n >>= 1
    return ans
n = int(input())
colors = list(map(int, input().split()))
colors.sort(reverse=True)
i = 0
while i<n and colors[i]:
    hibit = getHiBit(colors[i])
    for j in range(i+1, n):
        if getHiBit(colors[j])==hibit:
            colors[j] ^= colors[i]
        else: break
    colors.sort(reverse=True)
    i += 1
print(i)  

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int GetBitLength(int k){
    int j = 0;
    while(k > 0){
        k >>= 1;
        ++j;
    }
    return j;
}

int main(){
    int i, j, n;
    cin>>n;
    vector<int> v(n);
    for(i = 0; i < n; ++i){
        cin>>v[i];
    }
    sort(v.begin(), v.end());
    int res = 0;
    while(v.size() > 1){
        vector<int> xor_num;
        j = v.size() - 1;
        while(j > 0 && GetBitLength(v[j]) == GetBitLength(v[j - 1])){
            int xor_val = v[j] ^ v[j - 1];
            if(xor_val != 0 && find(v.begin(), v.end(), xor_val) == v.end()){
                xor_num.push_back(xor_val);
            }
            v.pop_back();
            --j;
        }
        ++res;
        v.pop_back();
        if(xor_num.size() > 0){
            v.insert(v.end(), xor_num.begin(), xor_num.end());
            sort(v.begin(), v.end());
        }
    }
    cout<<res + v.size()<<endl;
    return 0;
}

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;
    }
}

#include<bits/stdc++.h>
#define MAX 100
using namespace std;
/*
 大体思路是高斯消元法，数学背景就是XOR运算刚好是GF(2)上的加法，而所有的unsigned int刚好构成了GF(2)上32位的向量空间(本题只需30位)。
 我们要求的值,也就是颜色向量组的秩。求秩的一个基本思路是高斯消元法化成行标准形矩阵。由于GF(2)是一个域,矩阵也是定义在域上的矩阵,可以加减乘除。
 findFirstOne找到该数中非0的最高位,eg:findFirstOne(3)=2,findFirstOne(6)=3 findFirstOne(7)=3,仔细想想这就有点像线性代数里面找每行的第一个非0元。
 getMax很好看懂,如果a>=b,显然findFirstOne(a)>=findFirstOne(b),如果a>b,findFirstOne(a)也是大于等于findFirstOne(b),未必严格大于。
 我们先找第一个findFirstOne()最大的数,将它调到第一行,用异或操作消去该列的第一个非零元，然后指针指向第二个数,找第二个数到最后一个数中findFirstOne()
 最大的数，将它调到第二行,以此类推。
 for examle,输入:
 3
 1 2 3
 算法先将3和1交换
 3 2 1
 3要和2异或,但不能和1异或(if(findFirstOne(arr[scan]) == firstone)这个判断),因为1的第二位本来就是0
 变成
 3 1 1
 然后把3固定下来，指针指向2,变成3 1 0
 我们发现秩为2,就是cur-1,这个很好理解。本代码所有变量均使用unsigned,数组从1开始。对了,对于例子中的输入对应的二进制矩阵Binary是
 0 1 1
 0 1 0
 0 0 1
 rank(Binary) = 2
*/
unsigned findFirstOne(unsigned color)
{
    //cout<<(mask>1000000000)<<endl;
    unsigned cnt = 30,mask=0x20000000;//这个数字刚好是一个30位的二进制数,比1000000000稍大一些。
    while(mask)
    {
        if((mask&color)>0)//需要注意位运算优先级
            return cnt;
        else
        {
            mask = mask>>1;
            cnt--;
        }
    }
    return 0;
}

unsigned getMax(unsigned arr[],unsigned start,unsigned length)
{
    /*
        arr:一个unsigned数组，从1开始
        start:开始扫描的位置
        length:这个数组的长度
        返回:这个数组元素最大值对应的下标
    */
    unsigned cnt;
    unsigned maxunsign = 0,argmax = start;
    for(cnt = start;cnt<=length;++cnt)
    {
        if(arr[cnt] > maxunsign)
        {
            maxunsign = arr[cnt];
            argmax = cnt;
        }
    }
    if(maxunsign == 0)//已经全0,行标准型已经完成
        return 0;
    else
        return argmax;
}

int main()
{
    unsigned n,cur=1,arr[MAX],input,scan;
    unsigned ret,firstone;
    scanf("%u",&n);getchar();//使用getchar吸收换行符
    input = n;
    while(input--)
        cin>>arr[n-input];//从1开始输入
    for(cur = 1;cur<=n;++cur)
    {
        //依次扫描各行
        ret = getMax(arr,cur,n);
        if(!ret)
            break;
        else if(ret!=cur)
            swap(arr[cur],arr[ret]);
        firstone = findFirstOne(arr[cur]);//反复用到,先记下来
        for(scan = cur+1;scan<=n;++scan)
        {
            //行标准型要求每行首个非零元所在的列除了这个非零元以外全为0
            if(findFirstOne(arr[scan]) == firstone)
                arr[scan] = arr[cur] ^ arr[scan];
        }
    }
    cout<<cur-1<<endl;
    return 0;
}

	

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{     int n,a[51];     cin>>n;     for(int i=0;i<n;i++)         cin>>a[i];     for(int i=n-1;i>0;i--)     {         sort(a,a+i+1);         for(int j=i-1;j>=0;j--)         {             if((a[j]^a[i]) < a[j])                 a[j] ^= a[i];         }     }     int k;     for(k=0;a[k]==0;k++);     cout<<n-k<<endl;     return 0;
}

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[50][32],equ,var=32;
int solve(){
    int res=0,c,j,i,k;
    for(c=0;c<var&&res<equ;c++,res++){
        for(i=res;i<equ;i++)
            if(a[i][c]) break;
        if(equ==i) res--;
        else{
            for(k=0;k<var;k++) swap(a[res][k],a[i][k]);
            for(k=i+1;k<equ;k++)
                if(a[k][c])
                    for(j=c;j<var;j++)
                        a[k][j]^=a[res][j];
        }
    }
    return res;
} 
int main(){
    int i,tmp;
    for(scanf("%d",&equ),i=0;i<equ;i++){
        scanf("%d",&tmp);
        int index=31;
        while(tmp)
            a[i][index--]=tmp%2,tmp/=2;
    }
    printf("%d\n",solve());
}//求出矩阵的秩就可以了

// 从大到小遍历数组，当前元素与仅次于当前元素大小的元素如果长度相同， 异或之后消除第二个元素的最高位上的1，并把异或的结果复制给第二个元素，
每一个有1的位只留一个元素就够了。最后不是0的元素就是需要的原料。

/**  * Created by hudaoyun on 16/8/24.
 *参考一楼的答案，求矩阵的秩  */ import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args){
        Scanner in = new Scanner(System.in); int n = in.nextInt();
        ArrayList<Integer> colors = new ArrayList<Integer>(); for (int i = 0; i < n; i++){ int x = in.nextInt(); colors.add(x);
        }
        Collections.sort(colors); int bigest = n-1; int bigsecond = bigest - 1; int result = 0; while(colors.size() > 2){ if (getHighPosition(colors.get(bigest)) == getHighPosition(colors.get(bigsecond))){ int temp = colors.get(bigest) ^ colors.get(bigsecond); if (!colors.contains(temp)){ colors.add(temp);
                    Collections.sort(colors);
                    bigest = colors.size() - 1;
                    bigsecond = bigest - 1;
                }
            }else{
                result++;
            } colors.remove(colors.size() - 1);
            bigest = bigsecond;
            bigsecond--;
        }
        System.out.println(result + 2);

    } public static int getHighPosition(int a){ int count = 0; while(a > 0){
            count++;
            a = a >> 1;
        } return count;
    }
}

/*参考loolroco写出来的代码*/

#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<math.h>
#include<algorithm>
using namespace std;

int highPostion(int a){
	int res = 0;
	while (a){
		a >>= 1;
		res++;
	}
	return res;
}

int main(){
	int n;
	while (cin >> n){
		int res = 0;
		set<int> s;
		for (int i = 0; i<n; i++){
			int tmp; cin >> tmp;
			s.insert(tmp);
		}
		set<int>::reverse_iterator r = ++s.rbegin();
		int esVal, endVal;
		while (s.size()>2){
			esVal = *r--;
			endVal = *r;
			while (highPostion(endVal) == highPostion(esVal) && s.size() >= 2){
				int tmp = esVal ^ endVal;
				if (s.find(tmp) == s.end()){
					s.insert(tmp);
				}
				s.erase(endVal);
				r = ++s.rbegin();
				esVal = *r--;
				endVal = *r;
			}
			res++;
			s.erase(endVal);
			r = ++s.rbegin();
		}
		cout << res + s.size() << endl;
	}
	return 0;
}

//数组从小到大排列，从最下面一行开始，每次消去最高位的1，比如A行的系数减去B行，直接A = A^B就行
import java.util.*;
public class hunheyanliao {
	
	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--){
					if(highbit(col[i]) == highbit(col[j])){
						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){
		for(int i=31;i>=0;i--)
		{
		   int m = (x>>i)&1;
		   if(m != 0)
			   return i+1;
		}
		return 0;
	}
}