题解 | 混合颜料

混合颜料

https://www.nowcoder.com/practice/5b1116081ee549f882970eca84b4785a

解题思路

这是一个基于异或运算的线性基问题。关键是理解异或运算的性质，并利用线性基来求解最小所需颜料数。

关键点：

异或运算的性质：
- 交换律： $a\oplus b = b\oplus a$
- 结合律： $(a\oplus b)\oplus c = a\oplus (b\oplus c)$
- 自反性： $a\oplus a = 0$
线性基的概念：
- 一组数的线性基是能通过异或运算表示原集合中所有数的最小集合
最小购买数量就是线性基的大小

算法步骤：

构建线性基
统计线性基中非零元素的个数

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    static const int MAX_BIT = 30;  // log2(10^9)
    vector<int> basis;
    
    void insert(int x) {
        // 从高位到低位尝试插入
        for (int i = MAX_BIT; i >= 0; i--) {
            if (!(x & (1 << i))) continue;
            
            // 如果当前位还没有基
            if (!basis[i]) {
                basis[i] = x;
                return;
            }
            
            // 否则异或掉这一位
            x ^= basis[i];
        }
    }
    
public:
    int minColors(int n, vector<int>& colors) {
        basis.assign(MAX_BIT + 1, 0);
        
        // 构建线性基
        for (int color : colors) {
            insert(color);
        }
        
        // 统计非零基的个数
        int count = 0;
        for (int i = 0; i <= MAX_BIT; i++) {
            if (basis[i]) count++;
        }
        
        return count;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> colors(n);
    for (int i = 0; i < n; i++) {
        cin >> colors[i];
    }
    
    Solution solution;
    cout << solution.minColors(n, colors) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private static final int MAX_BIT = 30;  // log2(10^9)
        private int[] basis;
        
        private void insert(int x) {
            // 从高位到低位尝试插入
            for (int i = MAX_BIT; i >= 0; i--) {
                if ((x & (1 << i)) == 0) continue;
                
                // 如果当前位还没有基
                if (basis[i] == 0) {
                    basis[i] = x;
                    return;
                }
                
                // 否则异或掉这一位
                x ^= basis[i];
            }
        }
        
        public int minColors(int n, int[] colors) {
            basis = new int[MAX_BIT + 1];
            
            // 构建线性基
            for (int color : colors) {
                insert(color);
            }
            
            // 统计非零基的个数
            int count = 0;
            for (int i = 0; i <= MAX_BIT; i++) {
                if (basis[i] != 0) count++;
            }
            
            return count;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) {
            colors[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.minColors(n, colors));
        
        sc.close();
    }
}

class Solution:
    def __init__(self):
        self.MAX_BIT = 30  # log2(10^9)
        self.basis = []
    
    def insert(self, x: int):
        # 从高位到低位尝试插入
        for i in range(self.MAX_BIT, -1, -1):
            if not (x & (1 << i)):
                continue
            
            # 如果当前位还没有基
            if not self.basis[i]:
                self.basis[i] = x
                return
            
            # 否则异或掉这一位
            x ^= self.basis[i]
    
    def min_colors(self, n: int, colors: list) -> int:
        self.basis = [0] * (self.MAX_BIT + 1)
        
        # 构建线性基
        for color in colors:
            self.insert(color)
        
        # 统计非零基的个数
        return sum(1 for x in self.basis if x)

# 读取输入
n = int(input())
colors = list(map(int, input().split()))

solution = Solution()
print(solution.min_colors(n, colors))