差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 18:05]
yuki
+++ 2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 21:09] (当前版本)
yuki
@@ 行 164: / 行 164: @@
 **题意**：一棵树每个点上有权值，多次查询不同路径x->y的最大幸运值。幸运值：从x->y路径上的点选任意子集的异或和。\\
 **题解**：倍增lca+线性基\\
+<hidden std>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#include<set>
+#include<queue>
+#include<vector>
+#include<cmath>
+#include<cstdlib>
+#include<map>
+#include<stack>
+using namespace std;
+typedef long long ll;
+typedef pair<int,ll> pi;
+const int N=20005;
+ll getint(){
+    char c;bool flag=0;ll num=0ll;
+    while((c=getchar())<'0'||c>'9')if(c=='-')flag=1;
+    while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
+    if(flag) num=-num;
+	return num;
+}
+int n,q,fa[N],dep[N];
+ll luck[N],A[N][17][63],f[N][17],a[63];
+int cnt,fir[N],tar[N<<1],nxt[N<<1];
+inline void link(int a,int b){
+	tar[++cnt]=b,nxt[cnt]=fir[a],fir[a]=cnt;
+}
+void insert(ll*a,ll x){
+	for(int i=60;i>=0;i--)if(x&(1ll<<i)){
+		if(a[i]) x^=a[i];
+		else{a[i]=x;break ;}
+	}
+}
+void merge(ll*x,ll*y){
+	for(int i=0;i<=60;i++)
+		if(y[i]) insert(x,y[i]);
+}
+inline void init(){
+	for(int i=2;i<=n;i++){
+		insert(A[i][0],luck[i]);
+		insert(A[i][0],luck[f[i][0]]);
+	}
+	for(int i=1;i<=15;i++)
+		for(int j=1;j<=n;j++){
+			f[j][i]=f[f[j][i-1]][i-1];
+			merge(A[j][i],A[j][i-1]);
+			merge(A[j][i],A[f[j][i-1]][i-1]);
+		}
+}
+void dfs(int x,int fa){
+	for(int i=fir[x];i;i=nxt[i])
+		if(tar[i]!=fa){
+			f[tar[i]][0]=x;
+			dep[tar[i]]=dep[x]+1;
+			dfs(tar[i],x);
+		}
+}
+inline ll getMax(){
+	ll ans=0;
+	for(int i=60;i>=0;i--)
+		ans=max(ans,ans^a[i]);
+	return ans;
+}
+int getk(int x,int k){
+	if(!k) return x;
+	for(int i=15;i>=0;i--)if(k&(1<<i))
+		merge(a,A[x][i]),x=f[x][i];
+	return x;
+}
+int getd(int x,int d){
+	return getk(x,dep[x]-d);
+}
+inline ll query(int x,int y){
+	memset(a,0,sizeof a);
+	insert(a,luck[x]);
+	insert(a,luck[y]);
+	if(dep[x]!=dep[y]){
+		int md=min(dep[x],dep[y]);
+		x=getd(x,md),y=getd(y,md);
+	}
+	if(x==y) return getMax();
+	for(int i=15;i>=0;i--)
+		if(f[x][i]!=f[y][i]){
+			merge(a,A[x][i]),x=f[x][i];
+			merge(a,A[y][i]),y=f[y][i];
+		}
+	insert(a,luck[f[x][0]]);
+	return getMax();
+}
+int main(){
+	n=getint(),q=getint();
+	for(int i=1;i<=n;i++)
+		luck[i]=getint();
+	for(int i=1;i<n;i++){
+		int x=getint(),y=getint();
+		link(x,y),link(y,x);
+	}
+	dfs(1,0);
+	init();
+	while(q--)
+		cout<<query(getint(),getint())<<endl;
+}
+</code>
+</hidden>
+\\
+==== 洛谷3857 [TJOI2008]彩灯 ====
+**题意：**每个开关可以控制一部分的灯，改变它们的开关状态，计算灯的状态有多少种可能。（对2008取模）灯的数量和开关的数量都小于50\\
+**题解：**设线性基的长度为$x$，答案为$2^x$
+<hidden std>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#include<set>
+#include<queue>
+#include<vector>
+#include<cmath>
+#include<cstdlib>
+#include<map>
+#include<stack>
+using namespace std;
+typedef long long ll;
+const int N=20005;
+int n,m;ll a[55];char str[55];
+inline void insert(ll x){
+	for(int i=50;i>=0;i--)if(x&(1ll<<i)){
+		if(a[i]) x^=a[i];
+		else{a[i]=x;break ;}
+	}
+}
+inline int qpow(int x,int p){
+	int ans=1;
+	while(p){
+		if(p&1) ans=ans*x%2008;
+		x=x*x%2008,p>>=1;
+	}
+	return ans;
+}
+int main(){
+	scanf("%d%d",&n,&m);
+	for(int i=1;i<=m;i++){
+		scanf("%s",str+1);
+		ll x=0ll;
+		for(int j=1;j<=n;j++){
+			x<<=1;
+			if(str[j]=='O') x|=1;
+		}
+		insert(x);
+	}
+	int cnt=0;
+	for(int i=0;i<=50;i++)
+		if(a[i]) cnt++;
+	printf("%d\n",qpow(2,cnt));
+}
+</code>
+</hidden>
+\\
+==== 洛谷4151 [WC2011]最大XOR和路径 ====
+**题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\
+**题解：**首先注意到一个结论：对于所有的简单环，环上边权的异或和都可以无代价的获取。原因是可以从一号点出发进入该环绕一圈后原路返回。由于一条路径绕两边对答案的贡献为 $0$，所以这些简单环的异或和都可以无代价取得。那么现在问题就转化成了寻找一条 $1$到 $n$的路径，再异或上一些简单环的异或和，最大化答案。\\
+我们考虑应该寻找哪一条路径：事实上任选一条路径即可。原因是选择的路径和答案路径一定可以构成一个环，所以异或上该环的权值就可以得到最优解。
+<hidden std>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#include<set>
+#include<queue>
+#include<vector>
+#include<cmath>
+#include<cstdlib>
+#include<map>
+#include<stack>
+using namespace std;
+typedef long long ll;
+const int N=50005;
+const int M=200005;
+ll getin(){
+    char c;bool flag=0;ll num=0ll;
+    while((c=getchar())<'0'||c>'9')if(c=='-')flag=1;
+    while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
+    if(flag) num=-num;
+	return num;
+}
+int n,m,cnt=1,fir[N],tar[M],nxt[M];
+ll w[M],f[N],a[65];bool dfn[N];
+inline void link(int a,int b,ll c){
+	tar[++cnt]=b,w[cnt]=c;
+	nxt[cnt]=fir[a],fir[a]=cnt;
+}
+inline void insert(ll x){
+	for(int i=61;i>=0;i--)if(x&(1ll<<i)){
+		if(a[i]) x^=a[i];
+		else{a[i]=x;break ;}
+	}
+}
+void dfs(int x,int last){
+	dfn[x]=1;
+	for(int i=fir[x];i;i=nxt[i]){
+		if(i==(last^1)) continue ;
+		if(!dfn[tar[i]]){
+			f[tar[i]]=f[x]^w[i];
+			dfs(tar[i],i);
+		}
+		else insert(f[x]^f[tar[i]]^w[i]);
+	}
+}
+int main(){
+	n=getin(),m=getin();
+	while(m--){
+		int x=getin(),y=getin();
+		ll w=getin();
+		link(x,y,w),link(y,x,w);
+	}
+	dfs(1,0);
+	ll ans=f[n];
+	for(int i=61;i>=0;i--)
+		ans=max(ans,ans^a[i]);
+	cout<<ans<<endl;
+}
+</code>
+</hidden>
+\\

CVBB ACM Team

用户工具

站点工具

差别

页面工具