Bzoj4568: [Scoi2016]幸運數字

線性基+倍增+LCA

原來線性基還能這么考……一開始看到這個題以為是樹上差分線性基，然而線性基不支持刪除，所以就掛了。

后來想到倍增線性基，其實到這里思路就很清晰了。

倍增線性基，A[i][j]表示從i開始向上2^j步的線性基，詢問時暴力合并即可。

1 xxj hb(xxj a,xxj b) 2 { 3 xxj ans;ans.qk(); 4 for(int i=0;i<=60;i++) 5 { 6 if(a.b[i])ans.ins(a.b[i]);//不加if會T 7 if(b.b[i])ans.ins(b.b[i]); 8 } 9 return ans; 10 } 1 //幸運數字 2 #include<iostream> 3 #include<cstdio> 4 #define MAXN 20010 5 #define LL long long 6 const int L=1<<20|1; 7 char buffer[L],*S,*T; 8 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) 9 using namespace std; 10 struct xxj 11 { 12 LL b[65]; 13 void qk() 14 { 15 for(int i=0;i<=64;i++)b[i]=0; 16 } 17 bool ins(LL x) 18 { 19 for(int i=60;i>=0;i--) 20 if(x&(1ll<<i)) 21 { 22 if(!b[i]){b[i]=x;break;} 23 else x=x^b[i]; 24 } 25 if(x)return 1; 26 else return 0; 27 } 28 LL findmax() 29 { 30 LL ans=0; 31 for(int i=60;i>=0;i--) 32 ans=max(ans,ans^b[i]); 33 return ans; 34 } 35 }A[MAXN][16],ta; 36 xxj hb(xxj a,xxj b) 37 { 38 xxj ans;ans.qk(); 39 for(int i=0;i<=60;i++) 40 { 41 if(a.b[i])ans.ins(a.b[i]); 42 if(b.b[i])ans.ins(b.b[i]); 43 } 44 return ans; 45 } 46 struct edge 47 { 48 int u,v,nxt; 49 #define u(x) ed[x].u 50 #define v(x) ed[x].v 51 #define n(x) ed[x].nxt 52 }ed[MAXN*2]; 53 int first[MAXN],num_e; 54 #define f(x) first[x] 55 LL n,q,g[MAXN]; 56 int fa[MAXN][16],dep[MAXN]; 57 void dfs(int x,int ff,int de) 58 { 59 fa[x][0]=ff;dep[x]=de;A[x][0].ins(g[x]);//A[x][0].ins(g[ff]); 60 for(int i=f(x);i;i=n(i)) 61 if(v(i)!=ff)dfs(v(i),x,de+1); 62 } 63 int LCA(int x,int y) 64 { 65 if(dep[x]>dep[y])swap(x,y); 66 for(int i=15;i>=0;i--) 67 if(dep[fa[y][i]]>=dep[x]) 68 y=fa[y][i]; 69 if(x==y)return x; 70 for(int i=15;i>=0;i--) 71 if(fa[x][i]!=fa[y][i]) 72 x=fa[x][i],y=fa[y][i]; 73 return fa[x][0]; 74 } 75 inline LL read() 76 { 77 LL s=0;char a=getchar(); 78 while(a<'0'||a>'9')a=getchar(); 79 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} 80 return s; 81 } 82 inline void adde(int u,int v); 83 signed main() 84 { 85 // freopen("10.in","r",stdin); 86 87 n=read(),q=read(); 88 for(int i=1;i<=n;i++)g[i]=read(); 89 int a,b; 90 for(int i=1;i<n;i++) 91 { 92 a=read(),b=read(); 93 adde(a,b);adde(b,a); 94 } 95 dfs(1,0,1); 96 for(int i=1;i<=15;i++) 97 for(int j=1;j<=n;j++) 98 { 99 fa[j][i]=fa[fa[j][i-1]][i-1]; 100 A[j][i]=hb(A[j][i-1],A[fa[j][i-1]][i-1]); 101 } 102 for(int i=1;i<=q;i++) 103 { 104 int xi=read(),yi=read(); 105 int lca=LCA(xi,yi); 106 ta.qk(); 107 for(int j=15;j>=0;j--) 108 if(dep[fa[xi][j]]>=dep[lca]) 109 ta=hb(ta,A[xi][j]),xi=fa[xi][j]; 110 for(int j=15;j>=0;j--) 111 if(dep[fa[yi][j]]>=dep[lca]) 112 ta=hb(ta,A[yi][j]),yi=fa[yi][j]; 113 ta.ins(g[lca]); 114 printf("%lld\n",ta.findmax()); 115 } 116 } 117 inline void adde(int u,int v) 118 { 119 ++num_e; 120 u(num_e)=u; 121 v(num_e)=v; 122 n(num_e)=f(u); 123 f(u)=num_e; 124 } 完整代碼

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11240190.html

總結

以上是生活随笔為你收集整理的Bzoj4568: [Scoi2016]幸运数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。