【BZOJ 4568】[Scoi2016] 幸运数字

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/

《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 20000+9; 

int n,q,head[N],nxt[N*2],to[N*2];
LL arr[N];

inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

namespace LCA{
	int fa[N][16],dep[N];
	LL f[N][16][61],POW[61];

	void DFS(int w, int f) {
		fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; 
		for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
	} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}
	
	inline void merge(LL *a, LL *b) {
		for (int i=60;~i;i--) if (b[i]) {
			LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
				if (!a[j]) {a[j] = w; break;}
				else w ^= a[j];
			}
		} 
	}
	
	inline void init() {
		for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
		for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
		for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) 
			fa[i][j] = fa[fa[i][j-1]][j-1], 
			memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
			merge(f[i][j],f[fa[i][j-1]][j-1]);
	}
	
	inline LL query(int x, int y) {
		static LL bas[61]; memset(bas,0,sizeof(bas));
		if (dep[x] < dep[y]) swap(x,y);
		for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) 
			merge(bas,f[x][i]), x = fa[fa[x][i]][1];
		if (x == y) merge(bas,f[x][0]);  
		else {
			for (int i=15;~i;i--)  if (fa[x][i] != fa[y][i])
				merge(bas,f[x][i]), merge(bas,f[y][i]), 
				x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
			merge(bas,f[x][0]); 
		} LL ret = 0;
		for (int i=0;i<=60;i++) if (bas[i]) 
		for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
		for (int i=0;i<=60;i++) ret ^= bas[i];
		return ret;
	}	
};

int main(){
	n = read(); q = read();
	for (int i=1;i<=n;i++) arr[i] = readL();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	LCA::DFS(); LCA::init(); 
	for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read()));
	return 0;
}

另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注