1.格子游戏
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=40010; int p[N]; int n,m; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int get(int x,int y)//二维坐标映射到一维 { return x*n+y; } int main() { cin>>n>>m; for(int i=0;i<N;i++) p[i]=i; int res=0; for(int i=1;i<=m;i++) { int x,y,a,b; char type; cin>>x>>y>>type; x--,y--;//因为下标是从1开始的，映射到从0开始 a=get(x,y);//把二位坐标映射到一维里 if(type=='D') b=get(x+1,y); else b=get(x,y+1); int pa=find(a),pb=find(b); if(pa==pb)//假如有环的 { res=i; break; } p[pa]=pb; } if(res) cout<<res<<endl; else puts("draw"); return 0; }
2.搭配购买
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
把搭配购买的看成一个整体，然后做一遍01背包就可
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int p[N],v[N],w[N]; int n,m,vol; int f[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>n>>m>>vol; for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; while(m--) { int a,b; cin>>a>>b; a=find(a),b=find(b); if(a!=b) { v[b]+=v[a];//把a的价钱绑定在b中 w[b]+=w[a];//把a的价值绑定在b中 p[a]=b;//把ad节点合并在b中 } } for(int i=1;i<=n;i++)//做一遍01背包 if(p[i]==i)//假如是根节点 for(int j=vol;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout<<f[vol]<<endl; return 0; }
3.程序自动分析
把点离散化了，然后相等就和合并同个集合，在判断不相等有没有矛盾即可
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int p[N],n; struct Q//存询问 { int a,b,e; }q[N]; unordered_map<int,int> ha; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int get(int x)//把坐标进行映射 { if(!ha.count(x)) ha[x]=++n; return ha[x]; } bool solve() { n=0; int k; scanf("%d",&k); ha.clear();//清空上一层的状态 for(int i=1;i<=k;i++) { int a,b,e; scanf("%d%d%d",&a,&b,&e); q[i]={get(a),get(b),e}; } for(int i=1;i<=n;i++) p[i]=i;//初始化 for(int i=1;i<=k;i++) if(q[i].e)//假如是相等就合并 { int a=find(q[i].a),b=find(q[i].b); p[a]=b; } for(int i=1;i<=k;i++) if(!q[i].e)//假如不相等看看在不在一个集合里，假如在则矛盾 { int a=find(q[i].a),b=find(q[i].b); if(a==b) return false; } return true;//反之没矛盾 } int main() { int T; scanf("%d",&T); while(T--) if(solve()) puts("YES"); else puts("NO"); return 0; }
4.奇偶游戏
1.带边权的做法
异或就是二进制不进位加法
dx表示跟根节点的关系
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离 int n,m; unordered_map<int,int> ha; int get(int x) { if(!ha.count(x)) ha[x]=++n; return ha[x]; } int find(int x) { if(p[x]!=x) { int root=find(p[x]); d[x]^=d[p[x]];//更新路径长其他的值 p[x]=root; } return p[x]; } int main() { cin>>n>>m; n=0; int res=m; for(int i=0;i<N;i++) p[i]=i;//初始化 for(int i=1;i<=m;i++) { int a,b; string type; cin>>a>>b>>type; a=get(a-1),b=get(b);//获取离散化后的值 int t=0; if(type=="odd") t=1;//假如是奇数 int pa=find(a),pb=find(b); if(pa==pb)//假如在一个集合 { if((d[a]^d[b])!=t)//假如跟t不同类 { res=i-1; break; } } else//反之不在一个集合就合并 { p[pa]=pb; d[pa]=d[a]^d[b]^t;//合并到同一类中 } } cout<<res<<endl; return 0; }
2. 用扩展域的做法
假如条件少的话可以用，因为这里只有奇数和偶数，两个条件，可以用
#include<bits/stdc++.h> using namespace std; const int N=2e4+10,M=N/2;//M是分界线在0-M是偶数，大于M是奇数 int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离 int n,m; unordered_map<int,int> ha; int get(int x) { if(!ha.count(x)) ha[x]=++n; return ha[x]; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>n>>m; n=0; int res=m; for(int i=0;i<N;i++) p[i]=i;//初始化 for(int i=1;i<=m;i++) { int a,b; string type; cin>>a>>b>>type; a=get(a-1),b=get(b);//获取离散化后的值 int a1=find(a),a2=find(a+M),b1=find(b),b2=find(b+M);//获取a跟b的偶数和奇数情况 if(type=="odd")//假如是奇数类型 { if(a1==b1||a2==b2)//但是a跟b同类了 { res=i-1; break; } p[a1]=b2;//反之把a的偶数合并到b的奇数 p[a2]=b1;//反之把a的奇数合并到b的偶数 } else//假如是偶数 { if(a1==b2||a2==b1)//假如不同类 { res=i-1; break; } p[a1]=b1;//把偶数合并到偶数里 p[a2]=b2;//把奇数合并到奇数里 } } cout<<res<<endl; return 0; }
5.银河英雄传说
#include<bits/stdc++.h> using namespace std; const int N=3e4+10; int p[N],d[N],s[N];//s表示集合的长度，d表示每个点到根节点的距离 int find(int x) { if(p[x]!=x) { int root=find(p[x]);//先弄出根 d[x]+=d[p[x]];//把路径长的长度都加上，给这个点 p[x]=root;//最后让p[x]等于根 } return p[x]; } int main() { int m; scanf("%d",&m); for(int i=1;i<N;i++) p[i]=i,s[i]=1; while(m--) { char op[2]; int a,b; scanf("%s%d%d",op,&a,&b); int pa=find(a),pb=find(b); if(op[0]=='M') { if(pa==pb) continue;//假如已经合并过了 d[pa]=s[pb];//让根+pb的长度 s[pb]+=s[pa];//更新新的b的长度 p[pa]=pb;//把a合并到b里 } else { if(pa!=pb) puts("-1");//假如不在一列中 else printf("%d\n",max(0,abs(d[a]-d[b])-1));//假如在一列中输出距离 } } return 0; }
