[BJWC2011]元素线性基

题面

题解

一个方案合法，当且仅当选取的01串凑不出0.

因此就是要使得选取的01串全在线性基内，具体原因可以看这道题：[CQOI2013]新Nim游戏线性基

要使得魔力值最大，只需要按法力值从大到小，贪心的往线性基中加串就可以了

#include<bits/stdc++.h>

using namespace std;

#define R register int

#define AC 1100

#define LL long long

int n; LL ans;

LL f[AC];

struct node{LL x, w;}s[AC];

inline bool cmp(node a, node b){return a.w > b.w;}

inline LL read()

{

    LL x = 0;char c = getchar();

    while(c > '9' || c < '0') c = getchar();

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x;

}

void pre()

{

    n = read();

    for(R i = 1; i <= n; i ++) s[i].x = read(), s[i].w = read();

    sort(s + 1, s + n + 1, cmp);

}

void work()

{

    for(R i = 1; i <= n; i ++)//从高开始贪心

    {

        LL x = s[i].x, maxn = 1LL << 60; bool done = false;

        for(R j = 60; ~j; j --, maxn >>= 1)

        {

            if(!(x & maxn)) continue;

            if(!f[j]) {f[j] = x, done = true; break;}

            else x ^= f[j];

        }

        if(done) ans += s[i].w;//加入线性基就要拿走

    }

    printf("%lld\n", ans);

}

int main()

{

//	freopen("in.in", "r", stdin);

    pre();

    work();

//	fclose(stdin);

    return 0;

}

巴特西

[BJWC2011]元素线性基

题面

题解

最新文章

热门文章

巴特西

[BJWC2011]元素 线性基

题面

题解

最新文章

热门文章

[BJWC2011]元素线性基