BJWC2011 元素

wjh15101051's space

卧薪尝胆，厚积薄发。

BJWC2011 元素

Date: Sat Sep 15 19:19:29 CST 2018

In Category: NoCategory

Description：

给出 $n$ 个物品，每个物品有两个属性，选出一个满足第一个属性值异或和不为 $0$ 且第二个属性之和最大的集合。

$1\le n \le 1000$

Solution：

异或的问题，一般要么是 $trie$ ，要么是线性基，这题是简化版的 JLOI2015装备购买，只是把实数线性基变成了异或线性基，贪心的证明也是利用拟阵。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

struct linear_base

{

	ll d[63];

	void insert(ll k)

	{

		for(ll i = 62;i >= 0;--i)

		{

			if(k & (1ll << i))

			{

				if(d[i] == 0)

				{

					d[i] = k;

					break;

				}

				else

				{

					k ^= d[i];

				}

			}

		}

		return;

	}

	bool query(ll k)

	{

		for(ll i = 62;i >= 0;--i)

		{

			if(k & (1ll << i))

			{

				k ^= d[i];

			}

		}

		return (k == 0);

	}

}LB;

int n;

#define MAXN 1010

struct stone

{

	ll num,val;

}s[MAXN];

bool cmp_val(stone a,stone b){return a.val > b.val;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		scanf("%lld%lld",&s[i].num,&s[i].val);

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

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		if(LB.query(s[i].num))continue;

		ans += s[i].val;

		LB.insert(s[i].num);

	}

	cout << ans << endl;

	return 0;

}

In tag: 数学-线性基

wjh15101051