4.1 并查集
4.1.1 1250. 格子游戏
代码：
#include<bits/stdc++.h> using namespace std; const int N=40010; int n,m; int p[N]; int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int main() { cin>>n>>m; for(int i=0;i<=N;i++) p[i]=i; bool success=false; for(int i=0;i<m;i++) { int x,y; char c; cin>>x>>y>>c; int a=(x-1)*n+y-1; int b=a; if(c=='R') { b++; } else b+=n; int pa=findP(a),pb=findP(b); if(pa==pb) { cout<<i+1<<endl; success=true; break; } else p[pa]=pb; } if(!success) cout<<"draw"<<endl; return 0; }
4.1.2 1252. 搭配购买
代码：
#include<bits/stdc++.h> //y总的 using namespace std; const int N = 10010; int n, m, vol; int v[N], w[N]; int p[N]; 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; int pa = find(a), pb = find(b); if (pa != pb) { v[pb] += v[pa]; w[pb] += w[pa]; p[pa] = pb; } } // 01背包 for (int i = 1; i <= n; i ++ ) 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; } /* 自己写的 #include<bits/stdc++.h> using namespace std; const int N=10010; int n,m,w; map<int,pair<int,int> > mp; int money[N],value[N]; int cnt; int M[N],V[N]; int dp[N]; int p[N]; int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int main() { cin>>n>>m>>w; for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=n;i++) { cin>>money[i]>>value[i]; } for(int i=0;i<m;i++) { int a,b; cin>>a>>b; p[findP(a)]=findP(b); } for(int i=1;i<=n;i++) { int pa=findP(i); mp[pa].first+=money[i]; mp[pa].second+=value[i]; } for(map<int,pair<int,int> >::iterator it=mp.begin();it!=mp.end();it++) { cnt++; M[cnt]=it->second.first; V[cnt]=it->second.second; } for(int i=1;i<=cnt;i++) { for(int j=w;j>=M[i];j--) { dp[j]=max(dp[j],dp[j-M[i]]+V[i]); } } cout<<dp[w]; return 0; } */
4.1.3 237. 程序自动分析
代码：
#include<bits/stdc++.h> using namespace std; const int N=200010; int cnt; struct Node{ int a,b,c; }op[100010]; unordered_map<int,int> mp; int p[N]; int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int main() { int t; cin>>t; while(t--) { int n; cin>>n; cnt=1; mp.clear(); for(int i=1;i<=N;i++) p[i]=i; for(int i=1;i<=n;i++) { int a,b,c; cin>>a>>b>>c; if(mp.count(a)==0) mp[a]=cnt++; if(mp.count(b)==0) mp[b]=cnt++; op[i].a=a,op[i].b=b,op[i].c=c; } for(int i=1;i<=n;i++) { int a=op[i].a,b=op[i].b,c=op[i].c; if(c==1) { p[findP(mp[a])]=findP(mp[b]); } } bool success=true; for(int i=1;i<=n;i++) { int a=op[i].a,b=op[i].b,c=op[i].c; if(c==0) { if(findP(mp[a])==findP(mp[b])) { success=false; break; } } } if(success) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
4.1.4 239. 奇偶游戏
代码：
#include<bits/stdc++.h> //带边权并查集 using namespace std; const int N=20010; int n,m; int p[N],d[N]; map<int,int> S; int get(int x) { if(S.count(x)==0) S[x]=++n; return S[x]; } int findP(int x) { if(p[x]!=x) { int root=findP(p[x]); d[x]^=d[p[x]]; p[x]=root; } return p[x]; } int main() { cin>>n>>m; n=0; for(int i=0;i<N;i++) p[i]=i; int res=m; 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=findP(a),pb=findP(b); if(pa==pb) { if(d[a]^d[b]!=t) { res=i-1; break; } } else { p[pa]=pb; d[pa]=d[a]^d[b]^t; } } cout<<res<<endl; return 0; } /* 扩展域 #include<bits/stdc++.h> using namespace std; const int N=40010,base=N/2; int n,m; int p[N],d[N]; map<int,int> S; int get(int x) { if(S.count(x)==0) S[x]=++n; return S[x]; } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int main() { cin>>n>>m; n=0; for(int i=0;i<N;i++) p[i]=i; int res=m; for(int i=1;i<=m;i++) { int a,b; string type; cin>>a>>b>>type; a=get(a-1),b=get(b); if(type=="even") { if(findP(a+base)==findP(b)) { res=i-1; break; } p[findP(a)]=findP(b); p[findP(a+base)]=findP(b+base); } else { if(findP(a)==findP(b)) { res=i-1; break; } p[findP(a)]=findP(b+base); p[findP(a+base)]=findP(b); } } cout<<res<<endl; return 0; } */
4.1.5 238. 银河英雄传说
代码：
#include<bits/stdc++.h> using namespace std; const int N=30010; int n; int p[N],sz[N],d[N]; int findP(int x) { if(p[x]!=x) { int root=findP(p[x]); d[x]+=d[p[x]]; p[x]=root; } return p[x]; } int main() { cin>>n; for(int i=1;i<=N;i++) { p[i]=i; sz[i]=1; } for(int i=0;i<n;i++) { string type; int a,b; cin>>type>>a>>b; int pa=findP(a),pb=findP(b); if(type=="M") { d[pa]=sz[pb]; sz[pb]+=sz[pa]; p[pa]=pb; } else { if(pa!=pb) cout<<-1<<endl; else cout<<max(0,abs(d[a]-d[b])-1)<<endl; } } return 0; }
4.2 树状数组
4.2.1 241. 楼兰图腾
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=200010; int n; int a[N],tr[N]; int big[N],little[N]; int lowbit(int x) { return x&(-x); } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) //从x开始 tr[i]+=c; } int sum(int x) { int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { int y=a[i]; big[i]=sum(n)-sum(y); little[i]=sum(y-1); add(y,1); } memset(tr,0,sizeof tr); LL res1=0,res2=0; for(int i=n;i>=1;i--) { int y=a[i]; res1+=big[i]*(LL)(sum(n)-sum(y)); res2+=little[i]*(LL)sum(y-1); add(y,1); } cout<<res1<<" "<<res2<<endl; return 0; }
4.2.2 242. 一个简单的整数问题
代码：
#include<bits/stdc++.h> //差分，树状数组综合应用 using namespace std; const int N=100010; int n,m; int a[N]; int b[N]; //差分数组 int tr[N]; //差分数组的树状数组 void myinsert(int l,int r,int c) //差分 { b[l]+=c,b[r+1]-=c; } int lowbit(int x) { return x&(-x); } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) //从x开始 tr[i]+=c; } int sum(int x) { int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) myinsert(i,i,a[i]); for(int i=1;i<=n;i++) add(i,b[i]); while(m--) { string op; cin>>op; if(op=="Q") { int x; cin>>x; cout<<sum(x)<<endl; } else { int l,r,c; cin>>l>>r>>c; add(l,c),add(r+1,-c); } } return 0; }
4.2.3 243. 一个简单的整数问题2
代码：
#include<bits/stdc++.h> //差分，树状数组综合应用 using namespace std; typedef long long LL; const int N=100010; int n,m; int a[N]; LL tr_b[N]; //差分数组b[i]的树状数组 LL tr_bi[N]; //差分数组b[i]*i的树状数组 int lowbit(int x) { return x&(-x); } void add(LL tr[],int x,LL c) { for(int i=x;i<=n;i+=lowbit(i)) //从x开始 tr[i]+=c; } LL sum(LL tr[],int x) { LL res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } LL prefix_sum(int x) { return sum(tr_b,x)*(x+1)-sum(tr_bi,x); } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { int b=a[i]-a[i-1]; add(tr_b,i,b); add(tr_bi,i,(LL)b*i); } while(m--) { string op; int l,r,d; cin>>op>>l>>r; if(op=="Q") { cout<<prefix_sum(r)-prefix_sum(l-1)<<endl; } else { cin>>d; add(tr_b,l,d),add(tr_b,r+1,-d); //均只要修改两处 add(tr_bi,l,l*d),add(tr_bi,r+1,(r+1)*-d); } } return 0; }
4.2.4 244. 谜一样的牛
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010; int n; int h[N]; int ans[N]; int tr[N]; int lowbit(int x) { return x&-x; } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } int sum(int x) { int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } int main() { cin>>n; for(int i=2;i<=n;i++) cin>>h[i]; for(int i=1;i<=n;i++) tr[i]=lowbit(i); for(int i=n;i>0;i--) { int k=h[i]+1; int l=1,r=n; while(l<r) { int mid=(l+r)/2; if(sum(mid)>=k) r=mid; else l=mid+1; } ans[i]=r; add(r,-1); } for(int i=1;i<=n;i++) cout<<ans[i]<<endl; return 0; }
