CodeForces - 209C Trails and Glades
傳送門
題目大意：n個點，m條邊，從一號點出發，需要遍歷所有有邊相連的所有點最后要到一號點，(1 ≤ n ≤ 106; 0 ≤ m ≤ 106)
解法：跑出連通塊個數和每個連通塊所包含的度數為奇數的點，對于包含2個以上奇度頂點的連通塊，先兩兩相連到只剩兩個奇度頂點，然后所有連通塊由奇度頂點出發連到另外一個塊的奇度頂點，如果一個連通塊沒有奇度頂點，那就從任意一個偶度頂點出發，從同一偶度頂點回歸，統計連通塊用并查集
卡點：給的邊可能沒有連接1號頂點，需要從1號頂點出發和別的連通塊相連，邊數+1，但是如果一條邊都沒有，那結果就是0，因為沒有其他點了.（看cf樣例特判寫過.....）
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10 ; int fa[maxn], cnt[maxn], vis[maxn], arr[maxn] ; int fi(int x) { return x == fa[x] ? x : fa[x] = fi(fa[x]) ; } int main(int argc, char const *argv[]) { int n , m ; scanf("%d %d",&n,&m) ; for(int i = 1 ; i <= n ; ++ i) fa[i] = i, cnt[i] = 0, vis[i] = 0, arr[i] = 0 ; for(int i = 1, a, b ; i <= m ; ++ i) { scanf("%d %d",&a,&b) ; cnt[a] ++ ; cnt[b] ++ ; vis[a] = 1 ; vis[b] = 1 ; int fx = fi(a), fy = fi(b) ; if(fx != fy) fa[fx] = fy ; } int ans = 0 , tot = 0 ; for(int i = 1 ; i <= n ; ++ i) { if(cnt[i] % 2 == 1) { arr[fi(i)] ++ ; } } int ff = 0 ; int cnt2 = 0 , cnt1 = 0; for(int i = 2 ; i <= n ; ++ i) if(vis[i] == 1) ff = 1 ; int cnt = 0 ; for(int i = 1 ; i <= n ; ++ i) { if(vis[i] && fa[i] == i && arr[i] >= 2)//有奇度頂點的連通塊 { tot = tot + (arr[i] - 2) / 2 ; ++ cnt2 ;//奇度頂點數 } if(vis[i] && fa[i] == i) tot += 1, cnt ++ ;//頂點數 } cnt1 = cnt - cnt2 ; //printf("%d %d %d\n",cnt1,cnt2,cnt) ; if(cnt == 1) { if(cnt1 == 1) { if(vis[1] == 0) printf("2\n") ; else printf("0\n") ; } else if(cnt2 == 1) { if(vis[1] == 0) tot ++ ; printf("%d\n",tot) ; } } else if(cnt == 0) { printf("0\n") ; } else if(cnt >= 2) { if(vis[1] == 0) ++ tot ; printf("%d\n",tot) ; } return 0; }View Code
CodeForces - 468B Two Sets
傳送門
題目大意：第一行n,a,b， 第二行n個數，問能否分成兩個集合A B，對于集合A里面的數Ai ，滿足A-Ai也在A集合里，B同理，若可以分成兩個集合輸出YES，否則輸出NO
解法：假設序列滿足條件，那對每一個數而言，不在A，就在B，只需要設定n+1，n+2的兩個集合保存不在B，不在A的數，合并，對于在A的點，就把A-Ai和A合并，如果Find(n+1) == Find(n+2)成立的話,說明不存在合理方案，反之序列合理
卡點：一開始的做法分成了四個集合，存A存B存!A存!B，結果在判斷的時候寫炸了
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10 ; int fa[maxn], arr[maxn], brr[maxn] ; set<int> se ; map<int,int> mp ; int fd(int x) { return x == fa[x] ? fa[x] : fa[x] = fd(fa[x]) ; } void un(int x , int y) { int xx = fd(x) ; int yy = fd(y) ; if(xx != yy) fa[yy] = xx ; } int main(int argc, char const *argv[]) { int n, a, b ; se.clear() ; mp.clear() ; scanf("%d %d %d",&n,&a,&b) ; memset(brr,-1,sizeof brr) ; for(int i = 1 ; i <= n ; ++ i) { scanf("%d",&arr[i]) ; fa[i] = i ; se.insert(arr[i]) ; mp[arr[i]] = i ; } fa[n+1] = n+1 ; fa[n+2] = n+2 ; for(int i = 1 ; i <= n ; ++ i) { if(se.count(a-arr[i])) un(i,mp[a-arr[i]]) ; else un(i,n+1) ; if(se.count(b-arr[i])) un(i,mp[b-arr[i]]) ; else un(i,n+2) ; } if(fd(n+1) == fd(n+2)) { printf("NO\n") ; return 0 ; } printf("YES\n") ; for(int i = 1 ; i <= n ; ++ i) { printf("%d%c",(fd(i) == fd(n+1) ? 1 : 0)," \n"[i == n]) ; } return 0; }View Code
CodeForces - 722C Destroying Array
傳送門
題目大意：對于一個序列，每次洗掉一個位置的數，每次的值等于洗掉這個數之后每個子串的各自權值和的最大值
解法：反向操作，洗掉變插入，用并查集維護即可
卡點：無
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10 ; #define ll long long ll arr[maxn], val[maxn], val2[maxn] ; int brr[maxn], fa[maxn], vis[maxn] ; int fi(int x) { return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ; } int main(int argc, char const *argv[]) { int n ; scanf("%d",&n) ; memset(val,0,sizeof val) ; memset(vis,0,sizeof vis) ; memset(val2,0,sizeof val2) ; for(int i = 1 ; i <= n ; ++ i) scanf("%lld",&arr[i]), fa[i] = i ; for(int i = 1 ; i <= n ; ++ i) scanf("%d",&brr[n-i+1]) ; ll MAX = 0 ; for(int i = 1 ; i <= n ; ++ i) { val2[i] = MAX ; int pos = brr[i] ; vis[pos] = 1 ; int xx = fi(pos) ; int yy ; if(pos != 1) { if(vis[pos-1]) { yy = fi(pos-1) ; val[pos] += val[yy] ; if(xx != yy) fa[yy] = xx ; } } if(pos != n) { if(vis[pos+1]) { yy = fi(pos+1) ; val[pos] += val[fi(pos+1)] ; if(xx != yy) fa[yy] = xx ; } } val[pos] += arr[pos] ; MAX = max(MAX,val[pos]) ; } for(int i = n ; i >= 1 ; -- i) printf("%lld\n",val2[i]) ; return 0; }View Code
CodeForces - 1013D Chemical table
傳送門
題目大意：二維平面中一個矩陣的三個頂點存在就可以默認矩陣另一個頂點存在，問給了P個點之后最少需要添加多少個點
解法：對于一張表，我如果有一行一列就可以填滿，如果把這些點稱為有效點，我需要n+m-1個有效點，所以從P中確定有多少個有效點即可，確定該點是否有效借助并查集即可
卡點：思維
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 10 ; int fa[maxn] ; int fi(int x) { return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ; } int main(int argc, char const *argv[]) { int n, m, q ; int ans = 0 ; scanf("%d %d %d",&n,&m,&q) ; ans = m + n - 1 ; for(int i = 0 ; i <= n+m+5+m ; ++ i) fa[i] = i ; for(int i = 1, x, y ; i <= q ; ++ i) { scanf("%d %d",&x,&y) ; y += m+n ; int fx = fi(x) ; int fy = fi(y) ; if(fx != fy) { fa[fy] = fx ; ans -- ; } } printf("%d\n",ans) ; return 0; }View Code
CodeForces - 1131D Chemical table
傳送門
題目大意：給出n個點和m個點兩兩之間的n*m對關系，<,>,=，給出每個點合法的的最小權值，權值最小為1，權值大小關系即為兩兩之間關系，
解法：把相等的點用并查集縮成一個點，再跑拓撲排序
卡點：思維
代??
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e4 + 10 ; const int maxn = 1e3 + 10 ; #define pii pair<int,int> char mp[maxn][maxn] ; int fa[maxn*2] ; int vis[maxn*2] ; set<int> se ; vector<int> ve[maxn*2] ; int du[maxn*2] ; int ans[maxn*2] ; int Find(int x) { return x == fa[x] ? fa[x] : fa[x] = Find(fa[x]) ; } void merge(int x, int y) { int fx = Find(x), fy = Find(y) ; if(fx != fy) { fa[fx] = fy ; } } int main(int argc, char const *argv[]) { int n, m ; se.clear() ; memset(vis,0,sizeof vis) ; memset(ans,0,sizeof ans) ; scanf("%d %d",&n,&m) ; for(int i = 1 ; i <= m+n ; ++ i) fa[i] = i, du[i] = 0 ; for(int i = 1 ; i <= n ; ++ i) { scanf("%s",mp[i]+1) ; for(int j = 1 ; j <= m ; ++ j) if(mp[i][j] == '=') merge(i,j+n) ; } for(int i = 1 ; i <= n ; ++ i) { for(int j = 1 ; j <= m ; ++ j) { if(mp[i][j] == '=') merge(i,j+n) ; } } for(int i = 1 ; i <= n ; ++ i) { for(int j = 1 ; j <= m ; ++ j) { if(mp[i][j] == '>') ve[Find(j+n)].push_back(Find(i)), du[Find(i)] ++ ; else if(mp[i][j] == '<') ve[Find(i)].push_back(Find(j+n)) , du[Find(j+n)] ++ ; } } stack<int> st ; for(int i = 1 ; i <= n + m ; ++ i) { if(du[Find(i)] == 0 && vis[Find(i)] == 0) { vis[Find(i)] = 1 ; st.push(Find(i)) ; ans[Find(i)] = 1 ; } } while(!st.empty()) { int u = st.top() ; st.pop() ; for(int i = 0 ; i < ve[u].size() ; ++ i) { int v = ve[u][i] ; du[Find(v)] -- ; if(du[Find(v)] == 0 && vis[Find(v)] == 0) { st.push(Find(v)) ; vis[Find(v)] = 1 ; ans[Find(v)] = ans[Find(u)] + 1 ; } } } for(int i = 1 ; i <= n + m ; ++ i) { if(vis[Find(i)] == 0) { printf("NO\n") ; return 0 ; } } printf("YES\n") ; for(int i = 1 ; i <= n ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ; for(int i = n + 1 ; i <= n + m ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ; return 0; }View Code
CodeForces - 1166E Chemical table
傳送門
題解
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10 ; int arr[55][maxn] ; int vis[550][maxn] ; int main(int argc, char const *argv[]) { int m, n ; scanf("%d %d",&m,&n) ; memset(vis,0,sizeof vis) ; for(int i = 1, cnt ; i <= m ; ++ i) { scanf("%d",&cnt) ; arr[i][0] = cnt ; for(int j = 1 ; j <= cnt ; ++ j) scanf("%d",&arr[i][j]), vis[i][arr[i][j]] = 1 ; } int flag = 0 ; for(int i = 1 ; i <= m ; ++ i) { for(int j = 1 ; j <= m ; ++ j) { flag = 0 ; for(int k = 1 ; k <= n ; ++ k) { if(vis[i][k] && vis[j][k]) flag = 1 ; } if(flag == 0) { printf("impossible\n") ; return 0 ; } } } printf("possible\n") ; return 0; }View Code
HDU - 3047 Zjnu Stadium
傳送門
題目大意：給出m對關系，意味著Yi離Xi有多遠，圍城300個點的圈就坐，問有多少對關系是不合法的
解法：帶權并查集模板
卡點：模板，不用取模，因為每個點后右無限座位
代??
#include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; const int maxn = 1e5 + 10 ; const int mod = 300 ; int ans = 0 ; int fa[maxn], sum[maxn] ; int fi(int x) { if(fa[x] != x) { int root = fa[x] ; fa[x] = fi(fa[x]) ; sum[x] = sum[root] + sum[x] ; } return fa[x] ; } int main(int argc, char const *argv[]) { int n, m ; while(scanf("%d %d",&n,&m) != EOF) { ans = 0 ; for(int i = 1 ; i <= n ; ++ i) fa[i] = i, sum[i] = 0 ; for(int i = 1, x, y, s ; i <= m ; ++ i) { scanf("%d %d %d",&x,&y,&s) ; int fx = fi(x), fy = fi(y) ; if(fx == fy) { if(s != sum[x] - sum[y]) ans ++ ; } else { fa[fx] = fy ; sum[fx] = s - sum[x] + sum[y] ; } } printf("%d\n",ans) ; } return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71499.html
標籤：C++
上一篇：「BZOJ4173」數學
下一篇：涼肝的比賽