当前位置：首页 > news >正文

线性基学习DAY2

news 来源：原创 2024/9/30 13:45:18

今天是第二题学习线性基，让我对线性基的认识更多了，线性基其实就是去处理整个区间异或最值问题的

我们来看一下昨天的一道题

P4570 [BJWC2011] 元素

昨天其实这题我尝试了两次，一种是普通消元去求解，另一种是高斯消元去求解，但是发现高斯消元的方法只有30分，哪里有问题呢？

原来是因为可能会将排好序的元素换到下方，导致出现结果有问题，因此我们用高斯消元去求解的时候，每次交换后，要将有效区间以下的元素再排一次序，然后进行高斯消元就可以完美ak了

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n;
int len=1;
int bit=60;
struct node{int x;//该矿石的编号 int y; 
}a[1005];bool cmp(node a,node b)
{return a.y>b.y;
}void solve()
{len=1;for(int i=bit;i>=0;i--){for(int j=len;j<=n;j++){if((a[j].x>>i)&1LL){swap(a[len],a[j]);sort(a+len+1,a+n+1,cmp);break;}}if((a[len].x>>i)&1){for(int j=1;j<=n;j++){if(j==len)continue;if((a[j].x>>i)&1LL){a[j].x^=a[len].x;}}len++;}}
}signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}sort(a+1,a+1+n,cmp);solve();int sum = 0;for (int i = 1; i <= len-1; i++) {sum+=a[i].y;}cout << sum;return 0;
}

今日份例题

P4301 [CQOI2013] 新Nim游戏

题意：就是说在正常的nim博弈前面加上一组特殊的操作，我们可以拿多堆石子一次性拿一堆，然后问让自己能赢最少拿的火柴数，那么我们就应该有这种思维，什么情况下我们才能获胜呢？也就是说，无论让后手拿到几堆石子，都无法形成异或为0的形式，那么我们就可以用线性基的性质，如果要异或为0，那么就是说明插入的时候出现了0，这样会插入不进去，因此会与线性基里面的内容异或为0，因此我们只需要判断有几堆插不进去即可，将插不进去的元素累加在一起就是最终的答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[105];
int d[32];
bool cmp(int a,int b)
{return a>b;
}bool solve(int x)
{for(int i=32;i>=0;i--){if((x>>i)&1LL){if(!d[i]){d[i]=x;return true;}else{x^=d[i];}}}return false;
}signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n,cmp);int ans=0;for(int i=1;i<=n;i++){if(!solve(a[i])){ans+=a[i];}}cout<<ans;return 0;
}

P4151 [WC2011] 最大XOR和路径

这题我也是没解出来，看了评论区的大犇才知道该怎么去写出来这个题。

我们可以将整个无向图拆分为一个主链a和一些小环b，我们的的异或最大值，如果只是一个线性的，我们就每次去判断是否比以前更大就行了，我们该如何去处理这个环呢？

我们发现，如果要走一个环的话，当前的点和下一个点之间的路径就白走了，也就是贡献就是0，因此，我们只需要每次将环加入到线性基当中，然后去求取最大值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int u,v,w;
struct node{int to;int w;
};
vector<node> e[500005];
int ans[500005];//表示从起点到i这个点所用的最大异或值
int vis[500005];
int base[70];void solve(int x)
{for(int i=63;i>=0;i--){if((x>>i)&1){if(!base[i]){base[i]=x;return ;}x^=base[i];}}return ;
}void dfs(int v,int sum)
{ans[v]=sum;vis[v]=1;for(auto u:e[v]){if(vis[u.to]==0){dfs(u.to,sum^u.w);}else{solve(sum^u.w^ans[u.to]);}}
}signed main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v>>w;e[u].push_back((node){v,w});e[v].push_back((node){u,w});}dfs(1,0);int z=ans[n];for(int i=63;i>=0;i--){if((z^base[i])>z){z=z^base[i];}}cout<<z<<'\n';return 0;
}

总结：线性基就是为了去求解区间中的异或最值问题

希望各位在长大之前能找到属于自己的宝物，并且能够好好珍惜，我也早就已经找到那一份宝物了