#贪心，线性基#BZOJ 2460 洛谷 4570 JZOJ 2439 元素

本文主要是介绍#贪心，线性基#BZOJ 2460 洛谷 4570 JZOJ 2439 元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

---

分析

首先取到权值和最大答案越优，所以要先进行权值大到小排序，接着若序号异或值为0那么显然会让答案变小，所以要尽量让异或值不为0，所以说需要用到线性基，当可以插入线性基中也就是说明序号异或值不为0，那么加上权值和即可

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
typedef long long ll;
struct recc{ll rk,w;}a[1001];
ll rec[61]; int n;
inline ll iut(){rr ll ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline ll add(ll x){for (rr int i=60;~i;--i)if ((x>>i)&1){if (!rec[i]){rec[i]=x;return 1;}x^=rec[i];}return 0;
}
bool cmp(recc a,recc b){return a.w>b.w;}
signed main(){n=iut();for (rr int i=1;i<=n;++i) a[i]=(recc){iut(),iut()};sort(a+1,a+1+n,cmp); rr int ans=0;for (rr int i=1;i<=n;++i)if (add(a[i].rk)) ans+=a[i].w;return !printf("%d",ans);
}

这篇关于#贪心，线性基#BZOJ 2460 洛谷 4570 JZOJ 2439 元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---