线性基学习DAY2

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

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

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;
}

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

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