您现在的位置：首页 > 实用文 > 其他范文

BZOJ 2460 BeiJing 元素贪心+高斯消元

时间：2022-11-26 09:02:39 其他范文收藏本文下载本文

下面是小编为大家整理的BZOJ 2460 BeiJing 元素贪心+高斯消元，本文共2篇，欢迎阅读与收藏。

篇1：BZOJ 2460 BeiJing 元素贪心+高斯消元

题目大意：给定一些元素，每个元素有两个值a和b，现在需要选出一些元素，在不存在a值异或和为0的子集的情况下使b之和最大

可以用拟阵证明贪心的正确性(我不会证，同学会)

于是我们将b值排序，从大到小插入

动态维护线性基即可

#include#include#include#include #define M 1010using namespace std;struct abcd{ long long a; int b; friend istream& operator >>(istream& _,abcd &x) { _>>x.a>>x.b; return _; } bool operator< (const abcd &x) const { return b >x.b ; }}a[M];int n;long long ans,linear_bases[70];int main{ int i,j; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(i=1;i<=n;i++) { for(j=62;~j;j--) if(a[i].a&(1ll<

篇2：BZOJ 3563 DZY Loves Chinese / BZOJ 3569 DZY Loves Chinese II 随机化+高斯消元解异或方程组

题目大意：给出一个无向图，问删掉k条边的时候，图是否联通，

思路：虽然我把这两个题放在了一起，但是其实这两个题可以用完全不同的两个解法来解决。

第一个题其实是DZY出错了。。。把每次的边数也异或了，那就直接用这个性质一个一个往后推就行了。。最后一个暴力求一下。。

第二个题才是本意啊。

听到做法的时候我惊呆了。。

首先是将整个图中拆出一个树，那么所有边就分为树边和非树边。将所有非树边都加一个随机权值。树边的权值是所有能够覆盖它的非树边的权值的异或和。

把整个图拆开的充要条件是拆掉一条树边，同时将所有覆盖它的非树边也要拆掉，这些边的异或和正好等于0.这个就可以用高斯消元解异或方程组来解决了。

神啊神啊神啊神啊。。。

CODE：

#include#include#include#include #define MAX 1000010using namespace std;struct Edge{ int x,y,len; bool tree_edge; void Read() { scanf(“%d%d”,&x,&y); }}edge[MAX];int points,edges,asks;int head[MAX],total = 1;int next[MAX],aim[MAX];bool v[MAX];int _xor[MAX];inline void Add(int x,int y){ next[++total] = head[x]; aim[total] = y; head[x] = total;}void BuildTree(int x,int last){ v[x] = true; for(int i = head[x]; i; i = next[i]) if(!v[aim[i]]) { edge[i >>1].tree_edge = true; BuildTree(aim[i],x); }}void DFS(int x,int last){ for(int i = head[x]; i; i = next[i]) if(edge[i >>1].tree_edge && aim[i] != last) { DFS(aim[i],x); edge[i >>1].len = _xor[aim[i]]; _xor[x] ^= _xor[aim[i]]; }}int temp[MAX];inline bool GaussElimination(int cnt){ int k = 0,i; for(int j = 1<< 30; j; j >>= 1) { for(i = k + 1; i<= cnt; ++i) if(temp[i]&j) break; if(i == cnt + 1) continue; swap(temp[i],temp[++k]); for(int i = 1; i<= cnt; ++i) if(temp[i]&j && i != k) temp[i] ^= temp[k]; } return temp[cnt];}int main(){ srand(19970815); cin >>points >>edges; for(int i = 1; i<= edges; ++i) { edge[i].Read(); Add(edge[i].x,edge[i].y); Add(edge[i].y,edge[i].x); } BuildTree(1,0); for(int i = 1; i<= edges; ++i) if(!edge[i].tree_edge) { edge[i].len = rand(); _xor[edge[i].x] ^= edge[i].len; _xor[edge[i].y] ^= edge[i].len; } DFS(1,0); cin >>asks; int last_ans = 0; for(int cnt,x,i = 1; i<= asks; ++i) { scanf(“%d”,&cnt); //cnt ^= last_ans; for(int j = 1; j<= cnt; ++j) { scanf(“%d”,&x); x ^= last_ans; temp[j] = edge[x].len; } bool flag = !GaussElimination(cnt); if(!flag) { puts(“Connected”); ++last_ans; } else puts(“Disconnected”); } return 0;}