首页 > 其他分享 >F. Trees and XOR Queries Again

F. Trees and XOR Queries Again

时间:2023-12-06 13:22:06浏览次数:41  
标签:Again XOR merge Trees define add ans include fo

首先容易想到lca+线性基,\(O(nlognB^2+qlognB^2)\),显然T飞了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	void init(){
		memset(a,0,sizeof(a));
	}
	void add(int x){
		fd(i,20,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; break;
			}
		}
	}

	bool ask(int x){
		fd(i,20,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[N][21],ans;
int f[N][21],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,k,q;

void merge(lb &x,lb y){
	fo(i,0,20) {
		x.add(y.a[i]);
	}
}
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[x][0].add(a[x]);
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[v][0]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
void ask(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,20,0) {
		if (d[f[x][k]]>=d[y]) {
			merge(ans, g[x][k]);
			x=f[x][k];
		}	
	}
	if (x==y) {
		ans.add(a[x]);
		return;
	}
	fd(k,20,0) {
		if (f[x][k]^f[y][k]) {
			merge(ans, g[x][k]);
			merge(ans, g[y][k]);
			
			x=f[x][k]; y=f[y][k];
		}
	}
	ans.add(a[x]);
	ans.add(a[y]);
	ans.add(a[f[x][0]]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	

	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	
	fo(i,1,n-1){
		scanf("%d %d",&x,&y);
		add(x,y); add(y,x);
	}
	
	f[1][0]=1;
	g[1][0].add(a[1]);
	dfs(1,0);

	fo(j,1,20) fo(i,1,n) {
		f[i][j]=f[f[i][j-1]][j-1];

		merge(g[i][j], g[i][j-1]);
		merge(g[i][j], g[f[i][j-1]][j-1]);
	}
	
	scanf("%d",&q);
	while (q--){
		scanf("%d %d %d",&x,&y,&k);
		ans.init();
		
		ask(x,y);
		if (ans.ask(k)) A; else B;
	}
	return 0;
	
} 
 
  
 

来点优化,预处理第一次,完全没必要merge,直接赋值就行

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	void init(){
		memset(a,0,sizeof(a));
	}
	void add(int x){
		fd(i,20,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; break;
			}
		}
	}

	bool ask(int x){
		fd(i,20,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[N][21],ans;
int f[N][21],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,k,q;
void R(int &x){
	int t=0;
	char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for(;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
void merge(lb &x,lb y){
	fo(i,0,20) {
		x.add(y.a[i]);
	}
}
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[x][0].add(a[x]);
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[v][0]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
void ask(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,20,0) {
		if (d[f[x][k]]>=d[y]) {
			merge(ans, g[x][k]);
			x=f[x][k];
		}	
	}
	if (x==y) {
		ans.add(a[x]);
		return;
	}
	fd(k,20,0) {
		if (f[x][k]^f[y][k]) {
			merge(ans, g[x][k]);
			merge(ans, g[y][k]);
			
			x=f[x][k]; y=f[y][k];
		}
	}
	ans.add(a[x]);
	ans.add(a[y]);
	ans.add(a[f[x][0]]);
}
int main()
{
//	freopen("data.txt","r",stdin);
//	freopen("ans.out","w",stdout);
	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	R(n);
	fo(i,1,n) R(a[i]);
	
	fo(i,1,n-1){
		R(x); R(y);
		add(x,y); add(y,x);
	}
	
	f[1][0]=1;
	g[1][0].add(a[1]);
	dfs(1,0);

	fo(j,1,20) fo(i,1,n) {
		f[i][j]=f[f[i][j-1]][j-1];
		
		fo(k,0,20) g[i][j].a[k]=g[i][j-1].a[k];
		
//		merge(g[i][j], g[i][j-1]);
		merge(g[i][j], g[f[i][j-1]][j-1]);
	}
	
//	return 0;
	
	R(q);
	while (q--){
		R(x); R(y); R(k);
		ans.init();
		
		ask(x,y);
		if (ans.ask(k)) A; else B;
	}
	return 0;
	
} 
 
  
 

还是T,再来点优化
想起来之前动物园那题,开始写的是倍增,但是T,看到别的大佬说可以交换顺序,让它尽量连续访问,交换之后就过了。

试着改一下
同时原来先将x跳到与y同高,这样的话要合并3k次,x,y分别跳只要2k次。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	void init(){
		memset(a,0,sizeof(a));
	}
	inline void add(int x){
		fd(i,19,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; break;
			}
		}
	}

	bool ask(int x){
		fd(i,19,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[19][N],ans;
int f[19][N],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,k,q;
void R(int &x){
	int t=0;
	char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for(;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
inline void merge(lb &x,lb y){
	fo(i,0,19) {
		x.add(y.a[i]);
	}
}
inline void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[0][x].add(a[x]);
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[0][v]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,18,0) {
		if (d[f[k][x]]>=d[y]) x=f[k][x];
	}
	if (x==y) return x;
	fd(k,18,0) {
		if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
	}
	return f[0][x];
}
void ask(int x,int y){
	int l=lca(x,y);
	
	fd(k,18,0) {
		if (d[f[k][x]]>=d[l]) {
			merge(ans, g[k][x]);
			x=f[k][x];
		}
	}
	
	fd(k,18,0) {
		if (d[f[k][y]]>=d[l]) {
			merge(ans, g[k][y]);
			y=f[k][y];
		}
	}
	ans.add(a[l]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	R(n);
	fo(i,1,n) R(a[i]);
	
	fo(i,1,n-1){
		R(x); R(y);
		add(x,y); add(y,x);
	}
	
	f[0][1]=1;
	g[0][0].add(a[1]);
	dfs(1,0);
	
	fo(j,1,18) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
//	return 0;
	
	R(q);
	while (q--){
		R(x); R(y); R(k);
		ans.init();
		
		ask(x,y);
		if (ans.ask(k)) A; else B;
	}
	return 0;
	
} 
 
  
 

还可以继续优化,当j足够大,已经能够到根的话,就没必要合并了,直接赋值就行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (register int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	void init(){
		memset(a,0,sizeof(a));
	}
	inline void add(int x){
		fd(i,19,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; break;
			}
		}
	}

	bool ask(int x){
		fd(i,19,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[19][N],ans;
int f[19][N],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,k,q;
void R(int &x){
	int t=0;
	char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for(;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
inline void merge(lb &x,lb y){
	fo(i,0,19) {
		x.add(y.a[i]);
	}
}
inline void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[0][x].add(a[x]);
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[0][v]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,18,0) {
		if (d[f[k][x]]>=d[y]) x=f[k][x];
	}
	if (x==y) return x;
	fd(k,18,0) {
		if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
	}
	return f[0][x];
}
void ask(int x,int y){
	int l=lca(x,y);
	
	fd(k,18,0) {
		if (d[f[k][x]]>=d[l]) {
			merge(ans, g[k][x]);
			x=f[k][x];
		}
	}
	
	fd(k,18,0) {
		if (d[f[k][y]]>=d[l]) {
			merge(ans, g[k][y]);
			y=f[k][y];
		}
	}
	ans.add(a[l]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	R(n);
	fo(i,1,n) R(a[i]);
	
	fo(i,1,n-1){
		R(x); R(y);
		add(x,y); add(y,x);
	}
	
	f[0][1]=1;
	g[0][0].add(a[1]);
	dfs(1,0);
	
	fo(j,1,18) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
//	return 0;
	
	R(q);
	while (q--){
		R(x); R(y); R(k);
		ans.init();
		
		ask(x,y);
		if (ans.ask(k)) A; else B;
	}
	return 0;
	
} 
 
  

还能优化,当ans能够表示k的话就直接退出,对于大部分为yes的数据,加速明显。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (register int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	int t;
	void init(){
		t=0;
		memset(a,0,sizeof(a));
	}
	inline void add(int x){
		fd(i,19,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; t++; break;
			}
		}
	}

	bool ask(int x){
		fd(i,19,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[19][N],ans;
int f[19][N],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,z,q;
void R(int &x){
	int t=0;
	char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for(;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
inline void merge(lb &x,lb y){
	fo(i,0,19) {
		if (x.t==20) break;
		x.add(y.a[i]);
	}
}
inline void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[0][x].add(a[x]);
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[0][v]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,18,0) {
		if (d[f[k][x]]>=d[y]) x=f[k][x];
	}
	if (x==y) return x;
	fd(k,18,0) {
		if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
	}
	return f[0][x];
}
void ask(int x,int y){
	int l=lca(x,y);
	
	fd(k,18,0) {
		if (d[f[k][x]]>=d[l]) {
			merge(ans, g[k][x]);
			x=f[k][x];
			if (ans.ask(z)) return;
		}
	}
	
	fd(k,18,0) {
		if (d[f[k][y]]>=d[l]) {
			merge(ans, g[k][y]);
			y=f[k][y];
			if (ans.ask(z)) return;
		}
	}
	ans.add(a[l]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	R(n);
	fo(i,1,n) R(a[i]);
	
	fo(i,1,n-1){
		R(x); R(y);
		add(x,y); add(y,x);
	}
	
	f[0][1]=1;
	g[0][0].add(a[1]);
	dfs(1,0);
	
	fo(j,1,18) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
//	return 0;
	
	R(q);
	while (q--){
		R(x); R(y); R(z);
		ans.init();
		
		ask(x,y);
		if (ans.ask(z)) A; else B;
	}
	return 0;
	
} 
 
  
 

怎么办?
别忘了,我们还有终极手段,循环展开。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (register int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int b[30];
struct lb{
	int a[21];
	int t;
	void init(){
		t=0;
		memset(a,0,sizeof(a));
	}
	inline void add(int x){
		fd(i,19,0){
			if (!(x&b[i])) continue;
			if (a[i]) x^=a[i];
			else {
				a[i]=x; t++; break;
			}
		}
	}

	inline bool ask(int x){
		fd(i,19,0) {
			if (x&b[i]) x^=a[i];
		}
		return x==0;
	}
};
lb g[19][N],ans;
int f[19][N],d[N],a[N];
int to[N*2],nex[N*2],head[N],tot,n,x,y,z,q;
inline void R(int &x){
	int t=0;
	char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for(;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
inline void merge(lb &x,lb y){
	fo(i,0,19) {
		if (x.t==20) break;
		x.add(y.a[i]);
	}
}
inline void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	g[0][x].add(a[x]);
	for (register int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		
		f[0][v]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,18,0) {
		if (d[f[k][x]]>=d[y]) x=f[k][x];
	}
	if (x==y) return x;
	fd(k,18,0) {
		if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
	}
	return f[0][x];
}
void ask(int x,int y){
	int l=lca(x,y);
	
	fd(k,18,0) {
		if (d[f[k][x]]>=d[l]) {
			merge(ans, g[k][x]);
			x=f[k][x];
			if (ans.ask(z)) return;
		}
	}
	
	fd(k,18,0) {
		if (d[f[k][y]]>=d[l]) {
			merge(ans, g[k][y]);
			y=f[k][y];
			if (ans.ask(z)) return;
		}
	}
	ans.add(a[l]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	b[0]=1;
	fo(i,1,20) b[i]=b[i-1]*2;
	
	R(n);
	fo(i,1,n) R(a[i]);
	
	fo(i,1,n-1){
		R(x); R(y);
		add(x,y); add(y,x);
	}
	
	f[0][1]=1;
	g[0][0].add(a[1]);
	dfs(1,0);
	
	fo(j,1,4) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
	fo(j,5,8) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
	fo(j,9,12) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
	fo(j,13,16) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
	fo(j,17,18) fo(i,1,n) {
		f[j][i]=f[j-1][f[j-1][i]];
		
		if (f[j-1][i]==1) {
			g[j][i]=g[j-1][i];
			continue;
		}
		fo(k,0,19) g[j][i].a[k]=g[j-1][i].a[k];
		merge(g[j][i], g[j-1][f[j-1][i]]);
	}
	
	
//	return 0;
	
	R(q);
	while (q--){
		R(x); R(y); R(z);
		ans.init();
		
		ask(x,y);
		if (ans.ask(z)) A; else B;
	}
	return 0;
	
} 
 
  
 


ohhhhhh!

正解待补。

标签:Again,XOR,merge,Trees,define,add,ans,include,fo
From: https://www.cnblogs.com/ganking/p/17879290.html

相关文章

  • 汇编-xor异或
     XOR指令在两个操作数的对应位之间进行(按位)逻辑异或(XOR)操作,并将结果存在目标操作数中两个操作数的每一对对应位都应用如下操作原则:如果两个位值相同(同为0或同为1),则结果位等于0;否则结果位等于1。下标描述的是布尔运算x⊕y: 与0异或值不变,与1异或则被触发(求补)。对相同操作数进......
  • [AGC052B] Tree Edges XOR 题解
    题目链接点击打开链接题目解法怎么感觉这场\(B\)比\(C\)思维量更大考虑一步很妙的操作:把边权变成点权,以达到简化操作的目的使每条边的边权为两端点的异或和,手画一下可以发现,操作简化成了交换两端点的点权我们定义\(d_{1/2,i}\)定义为在\(1/2\)树上,\(i\)到根的权值......
  • vue-treeselect使用案例
    https://vue-treeselect.js.org/父子节点没有关联<TreeSelectflatstyle="background-color:#0e3977"placeholder="请选择"v-model="org":multiple="true":options="state.orgData&qu......
  • D2. Xor-Subsequence (hard version)
    D2.Xor-Subsequence(hardversion)Itisthehardversionoftheproblem.Theonlydifferenceisthatinthisversion$a_i\le10^9$.Youaregivenanarrayof$n$integers$a_0,a_1,a_2,\ldotsa_{n-1}$.Bryapwantstofindthelongestbeautifulsub......
  • 简单的文件加密程序(md5xor异或winlinux)
    简介小程序是基于md5+password+xor的组合方式来加密文件。程序支持跨平台(Windows/Linux)。使用方法: 源文件清单:main.c  md5.c  md5.h  setup.sh 完整代码(main.c):#include<stdio.h>#include<stdlib.h>#include<string.h>#include<errno.h>#i......
  • TreeSet
    TreeSet中的元素不可重复,可自动排序。TreeSet<Integer>treeset=newTreeSet<>();//构建TreeSet 排序功能演示publicclassMain{publicstaticvoidmain(Stringargs[]){TreeSet<Integer>treeset=newTreeSet<>();treeset.add(12);......
  • Java中的Set集合之TreeSet
    TreeSet:TreeSet是一个有序集合,它扩展了AbstractSet类并实现了NavigableSet接口。以下是此实现最重要方面的快速摘要:它存储唯一的元素它不保留元素的插入顺序它按升序对元素进行排序它不是线程安全的在该实现中,对象根据其自然顺序以升序排序和存储。该TreeSet中使用的是一......
  • CART(Classification and Regression Trees)
    CART(ClassificationandRegressionTrees)是一种常用的决策树算法,既可以用于分类问题,也可以用于回归问题。CART算法由Breiman等人于1984年提出,是一种基于递归二分划分的贪婪算法。以下是对CART算法的详细解释:1.决策树的构建过程:CART算法通过递归地将数据集划分为越来越纯的子集......
  • TreeSet
      ......
  • Linux openssh问题解决: Permission denied, please try again
    1.vim打开sshd_config文件vim/etc/ssh/sshd_config2.搜索PermitRootLogin ,将 PermitRootLoginprohibie-password 改为如下:PermitRootLoginyes  ......