牛客-混合颜料

发表于 | 分类于 ，

题目

描述

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

输入

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

输出

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

Example

Input

3
1 7 3

Output

3

题解

思路

  • 类似求矩阵的秩,这里把 加减 操作换成了 异或 操作
  • 用集合模板 set 来模拟矩阵的 初等变换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

int getHighPos(int n)
{
    int c=0;
    while(n)
        n>>=1,++c;
    return c;
}

int main()
{
    int n,t,c;
    set<int>need;
    cin>>n;
    while(n--)
    {
        cin>>t;
        need.insert(t);
    }
    c=0;
    auto g=prev(need.end()),l=prev(g);
    while(need.size()>2)
    {
        if(getHighPos(*g)==getHighPos(*l))
        {
            need.insert((*g)^(*l));
            g=prev(need.end()),l=prev(g);
        }
        else
        {
            ++c;
        }
        g=prev(need.erase(g));
        l=prev(g);
    }
    cout<<c+need.size();
}