2020-2021:teams:famerwzyyuki:线性基
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 19:11] yuki |
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 21:09] (当前版本) yuki |
||
|---|---|---|---|
| 行 272: | 行 272: | ||
| </hidden> | </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/线性基.1590750677.txt.gz · 最后更改: 2020/05/29 19:11 由 yuki
