网易--混合颜料

2024-04-13 01:48

文章标签 混合网易颜料

本文主要是介绍网易--混合颜料，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

解题思路

首先分析题目给出的示例1
输入为1 7 3
你可以购买1，2，4这三种颜料，1已经有了，3可以通过由 1 XOR 2 = 3得到，7可以通过1 XOR 4 = 5，5 XOR 2 = 7 得到，所以最少为3种。
理解1
想象一下对于两个给定的数(向量),他们可以生成的新的数,本质就是两个向量的所有线性表示。因为此处实际是在做一个mod 2的操作,那么线性表示的系数就是0或1。于是原问题就抽象为,给定一些向量(数)组成的向量空间,增加一个最小的向量集合,使向量的线性组合都可以生成向量空间中的所有向量。这个叫做向量空间的基。

怎么算出这个基呢？线性代数里面我们都学过：可以对原来所有向量组成的矩阵用高斯消元法直到让剩余的向量都是线性无关的,非0向量的个数就是答案。每次将最高位的1进行^运算，使得数组里面从后往前数最高位每个1只保留一个，最终得到类似于{0,0,00000001,00000011，00011000,00100010}这样的结构，那么答案就出来了。

理解2
给定多个数字，将这些数之间进行多次xor（异或操作），其中一个数可能被xor多次，看最后能剩余多少不重复的数（任何两个数字异或都没有出现在现在的数组中），这些不重复的数字就是一组基，输出数量即可。这种方法可以用暴力求解。

一些规律（下面会用到）
1. 0001,0010,0100,1000（这四个数”线性无关”，注意运算规则是异或（和线性代数有区别），任意两个数组进行XOR运算结果都不在这个数组中，也即是一个基，可以表示任何4位数），可以通过^生成任意4位的数字
2. a^b=c那么a^c=b

AC代码

这道题见过的最简洁的解法

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int i,j,n,x[55];cin>>n;for(i=0;i<n;++i)cin>>x[i];for(i=n-1;i>0;--i){sort(x,x+i+1);//从小到大排序for(j=i-1;j>=0;--j) //从大到小依次遍历小于 x[i] 的数字if((x[i]^x[j])<x[j]) //两个数字高位相同的情况。(如果高位不相同，且x[i] > x[j],则XOR后 x[i] ^ x[j] > x[j])x[j]^=x[i]; //将 x[j]的高位去掉，根据异或的性质 a^b=c那么a^c=b，现在的 x[j] 可以算出来以前的原始 x[j]，等于是换了个形式表示，所以整个算法等于是求可以表示数组的最小的基础(不同的是运算规则是XOR)}for(i=0;x[i]==0;++i); //数组是从小到大排列的,记录第一个不为0的索引cout<<n-i; //计算数字里面非零个数return 0;
}