G65 线性基+贪心法 P4570 [BJWC2011] 元素

/*
大致概括一下题意：有n个元素，每个元素有个序号和一个值，一个元素可以选择当且尽当其序号与已选元素序号的异或和不为0，求你可选择的元素值和的最大值。
我们设第i个数的序号为 a(i)，值为 b(i)，当a(i)⊕a(j)⊕a(k)=0时，我们要扔掉一个。
显然，我们扔最小的最优。于是贪心思想就派上用场了。
用线性基的性质，如果一个元素塞不进去，说明它会和某些数异或和为0，
为了让小一点的塞不进去，我们要将这些元素按 b 从大到小排个序，
然后能塞就塞进线性基，不能塞进去扔掉就可以了。 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005,B=60;
struct node{LL x;int y;}a[N];
LL p[B+5];
bool ins(LL x)
{
    for(int i=B;i>=0;--i)if(x>>i&1)
        if(!p[i]){p[i]=x;return 1;}
        else x^=p[i];
    return 0;
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,[](node n1,node n2){ return n1.y>n2.y;});
    int ans=0;
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;++i)
        if(ins(a[i].x))ans+=a[i].y;
    printf("%d\n",ans);
    return 0;
}

G65 线性基+贪心法 P4570 [BJWC2011] 元素

/*
大致概括一下题意：有n个元素，每个元素有个序号和一个值，一个元素可以选择当且尽当其序号与已选元素序号的异或和不为0，求你可选择的元素值和的最大值。
我们设第i个数的序号为 a(i)，值为 b(i)，当a(i)⊕a(j)⊕a(k)=0时，我们要扔掉一个。
显然，我们扔最小的最优。于是贪心思想就派上用场了。
用线性基的性质，如果一个元素塞不进去，说明它会和某些数异或和为0，
为了让小一点的塞不进去，我们要将这些元素按 b 从大到小排个序，
然后能塞就塞进线性基，不能塞进去扔掉就可以了。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005,B=60;
struct node{LL x;int y;}a[N];
LL p[B+5];
bool ins(LL x)
{
    for(int i=B;i>=0;--i)if(x>>i&1)
        if(!p[i]){p[i]=x;return 1;}
        else x^=p[i];
    return 0;
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,[](node n1,node n2){ return n1.y>n2.y;});
    int ans=0;
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;++i)
        if(ins(a[i].x))ans+=a[i].y;
    printf("%d\n",ans);
    return 0;
}