自动搬运

查看原文

来自洛谷，原作者为

	Si_tang **

搬运于2025-08-24 22:01:30，当前版本为作者最后更新于2019-09-15 15:06:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

虽然我的代码和其它题解的几乎没什么不同，但貌似其它题解讲的并不是很详细，很多关键的内容都跳过了，所以我在这里尽量详细地将每行代码的具体作用都讲清楚。

题目大意： 有n块石头，每块石头有一个序号和一个魔力值，你可以使用任意数量的石头，但你使用的石头中任意几块异或起来不能为0，求最大总魔力值。

思路

贪心

首先讲一个异或运算的性质
若 $a$ ^ $b$ = $c$ ， 则 $b$ ^ $c$ = $a$ , $a$ ^ $c$ = $b$ ;
虽然这很容易证明，但为了方便大家理解，这里还是证明一下：
1 ^ 0 = 1 , 0 ^ 0 = 0;
1 ^ 1 = 0 , 0 ^ 1 = 1;
由第一排可以看出，无论1还是0，与0异或的结果都是其本身，
由第二排可以看出，无论1还是0，与1异或的结果都会与其不同（0变1,1变0）
所以异或运算的最终结果只和用于运算的数的各位上1的数量有关，与各数字运算的顺序无关
∴$a$ ^ $b$ ^ $c$ = $b$ ^ $c$ ^ $a$ = $c$ ^ $a$ ^ $b$=……
∴$a$ ^ $b$ = $c$ , $b$ ^ $c$ = $a$ , $a$ ^ $c$ = $b$
那么，若x无法使用，则有:

$d[a]$ ^ $d[b]$ ^ … ^ $d[i]$ = $x$ ;

根据刚才的性质，如果先放入x，后放入$d[i]$，可得:

$x$^ $d[a]$^ … = $d[i]$ ;

显然，原本是x不能使用，改变顺序后，变成了的d[i]不能使用，而且使用的石头总数没有改变，那么，我们直接先使用魔力值最大的石头就行了，
所以我们可以按魔力值从大到小排序：

struct stone
{
    long long num;//序号 
    long long val;//魔力值 
}a[1001];

bool cmp(stone x,stone y)
{
    return x.val>y.val;//按魔力值从大到小排序 
}

线性基

虽然这道题可以说是线性基的模板题，但考虑到并不是所有人都知道线性基和其性质，所以我尽量用基础的语言讲线性基有关的代码，让完全不懂线性基的人也能看懂。

详解：既然使用的石头不能有任意几块异或为0，那么，对于每一块石头，我们都要在使用前用已使用的石头对它异或，判断能否得到0。
要得到0，可行的方法是逐个消掉每一位上的1，看能否全部消掉，同时在消掉这位的1后不能使前面有异或出新的1，
所以我们在对一块石头的序号异或时，要用一个数组的 $d[i]$ 保存用于消掉第 $i$ 位1的序号，由于不能是前面产生新的1，所以的这个数字必须是 $i$ 位的

举例：
要判断 $xi$ (10110)能否使用，先找到最左边的1，即第5位，然后用 $d[5]$ 存储的5位数进行异或消掉1，假如异或完后是101，而 $d[3]$ 还未存储数字，说明不能消掉此位的1，也就是说这块石头可以使用，就将101存储到 $d[3]$ 。

你可能会问，为什么不存它的序号10110而是存与 $d[5]$ 的运算结果101，这不会影响最终结果吗？
当然不会，因为假如你同时用一个序号与 $d[5]$ 和 $d[3]$ 异或了，由于 $d[3]$ 已经是与 $d[5]$ 运算过的了，但一个数与同一个数异或两次是不会改变结果的（异或两次1会改变两次，相当于没变，而异或两次0也不会变），所以存储101等价于同时存储了10110和 $d[5]$ ,不仅不会影响结果，而且能刚方便地用于以后消掉第3位的1。

代码

#include<bits/stdc++.h>
using namespace std;
int  n,ans;
long long d[64];

struct stone
{
	long long num;//序号 
	long long val;//魔力值 
}a[1001];

bool cmp(stone x,stone y)
{
    return x.val>y.val;//按魔力值从大到小排序 
}

bool LiuZeYu_ak_IoI(long long x)
{
    for(int i=62;i>=0;i--)
    {
        if((x>>i)&1)//从左向右判断每一位的1 
        {
            if(d[i+1]==0)//表示此位的1消不掉 
            {
                d[i+1]=x;
                return true;//能使用 
            }
            else x^=d[i+1];//保存异或结果 
        }
    }
    return false;//每一位的1都被消掉后，由于异或到0，所以不能使用 
} 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    scanf("%lld" "%d",&a[i].num,&a[i].val);
    sort(a+1,a+n+1,cmp);//贪心 
    
    for(int i=1;i<=n;i++)
    if(LiuZeYu_ak_IoI(a[i].num))
    ans+=a[i].val;
    
    printf("%d",ans);
    return 0;
}