2020-2021:teams:famerwzyyuki:线性基
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 17:45] yuki |
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 21:09] (当前版本) yuki |
||
|---|---|---|---|
| 行 114: | 行 114: | ||
| **题意：**给定一些矿石编号和矿石价值，问在保证矿石编号的任意子集的异或和不为0的情况下，最大价值是多少。\\ | **题意：**给定一些矿石编号和矿石价值，问在保证矿石编号的任意子集的异或和不为0的情况下，最大价值是多少。\\ | ||
| **题解：**很显然的贪心，按价值从大到小排序维护线性基。\\ | **题解：**很显然的贪心，按价值从大到小排序维护线性基。\\ | ||
| - | <std> | + | <hidden std> |
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 160: | 行 160: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| - | + | \\ | |
| + | ==== 洛谷3292 [SCOI2016]幸运数字 ==== | ||
| + | **题意**：一棵树每个点上有权值，多次查询不同路径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> | ||
| + | \\ | ||
2020-2021/teams/famerwzyyuki/线性基.1590745544.txt.gz · 最后更改: 2020/05/29 17:45 由 yuki
