Codeforces #446 (Div. 2) 题解

本文主要是介绍Codeforces #446 (Div. 2) 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A Greed 

注意long long

#include <bits/stdc++.h>
using namespace std;const int maxn = 100005 ;
typedef long long ll ;
ll a[maxn] ;
ll b[maxn] ;int main(){int n ;while(~ scanf("%d" , &n) ){priority_queue<ll> pq ;while(!pq.empty()) pq.pop() ;ll suma = 0 , p = 0 , q = 0 ;for(int i = 0 ; i < n ; i ++ ){scanf("%lld" , &a[i]) ;suma += a[i] ;}for(int i = 0 ; i < n ; i ++ ){scanf("%lld" , &b[i]) ;pq.push(b[i]) ;}p = pq.top() ;pq.pop() ;q = pq.top() ;if(p + q >= suma) puts("YES") ;else puts("NO") ;}return 0 ;
}

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e6 + 5 ;
typedef long long ll ;int pre[maxn] ;int main(){int n , a ;scanf("%d" , &n) ;memset(pre , 0 , sizeof(pre)) ;scanf("%d" , &a) ;for(int i = 2 ; i <= n ; i ++ ){scanf("%d" , &a) ;a = min(a , i - 1) ;pre[ i - a ] ++ ;pre[i] -- ;}int temp = 0 ;int ans = 0 ;for(int i = 1 ; i <= n ; i ++ ){temp += pre[i] ;if(temp > 0) ans ++ ;}printf("%d\n" , n - ans) ;return 0 ;
}

#include <bits/stdc++.h>
using namespace std;const int maxn = 2005 ;
typedef long long ll ;
const int inf = 1e9 + 7 ;int gcd(int m,int n){if(m==0) return n;if(n==0) return m;if(m%2==0&&n%2==0) return 2*gcd(m/2,n/2);else if(m%2==0) return gcd(m/2,n);else if(n%2==0) return gcd(m,n/2);elsereturn gcd(min(m,n),fabs(m-n));
}int a[maxn] ;
int d[maxn] ;
int main(){int n ;while(~ scanf("%d" , &n) ){for(int i = 1 ; i <= n ; i ++ ){scanf("%d" , &a[i]) ;}for(int i = 1 ; i <= n ; i ++ ){d[i] = inf ;int x = a[i] ;if(a[i] == 1)d[i] = i ;for(int j = i + 1 ; j < n + 1 ; j ++ ){x = gcd(x , a[j]) ;if(x == 1){d[i] = j ;break ;}}}if(d[1] == inf){puts("-1") ;}else{int s , m = inf ;int n1 = 0 ;for(int i = 1 ; i < n + 1 ; i ++ ){if(a[i] != 1)n1 ++ ;if(d[i] - i < m ){s = i ;m = d[i] - i ;}}if(d[s] == s){printf("%d\n" , n1) ;}else{printf("%d\n" , d[s] - s + n1 - 1) ;}}}return 0 ;
}

#include <bits/stdc++.h>
using namespace std ;const int maxn = 105 ;typedef pair<int , int> p2 ;
p2 a[maxn] ;
int ans[maxn] ;
int main(){int n , b ;scanf("%d" , &n) ;for(int i = 0 ; i < n ; i ++ ){scanf("%d" , &b) ;a[i] = make_pair(b , i) ;}sort(a , a + n) ;for(int i = 0 ; i < n - 1 ; i ++ ){ans[ a[i].second ] = a[i + 1].first ;}ans[ a[n - 1].second ] = a[0].first ;for(int i = 0 ; i < n; i ++ ){printf("%d " , ans[i]) ;}return 0 ;
}

E   Envy

生成树的询问问题，用离线并查集维护

由kruscal ，边按权值排列，我们按照权值分层，即权值相同的边为同一层。

注意：上一层的生成树无论怎么构成，都不影响下一层的生成树构成。

将所有的询问分层，如果某一询问中包含权值为w的边，即在map<int , vector<int> > 中插入该询问的id，同时记录询问的所有边。（也是按照权值分别存边， 即用map<int , vector<int> >  a[maxn]， 在后面的每一层只询问权值为该层的边）

离线后，然后从最底层开始（即权值最小的层），遍历所有未被标记的询问在该层的边，即尝试建树，如果成环，即标记，break，如果未成环，说明该访问该层成立，撤销该询问在该层的所有操作（即并查集中对par修改操作，记录用两个vector记录，注意并查集的find操作也会修改par）该层结束后，对整幅图求出在该层的生成树，进行par修改。

#include <bits/stdc++.h>
using namespace std ;const int maxn = 5e5 + 10 ;
typedef long long ll ;struct edge{int st , ed , w ;bool operator < (const edge & k) const {return w < k.w ;}
};
int id[maxn] ;
edge E[maxn] ;bool cmp(int x , int y){return E[x].w < E[y].w ;
}int par[maxn] ;
bool ans[maxn] ;
map<int , vector<int> > ma , query[maxn] ;
//ma mean whether q has operation on w///in order to recovervector<int> pre_id ;
vector<int> pre_value ;void init(int n){for(int i = 1 ; i <= n ; i ++ ) par[i] = i ;memset(ans , false , sizeof(ans)) ;pre_id.clear() ;pre_value.clear() ;
}/*
int temp_unite(int son , int father){pre_id.push_back(son) ;pre_value.push_back(par[son]) ;par[son] = father ;return father ;
}int find1(int x){int fa = par[x] ;while(fa != par[fa]){fa = par[ fa ] ;}if(x == fa) return x ;if(fa == par[x]) return fa ;pre_id.push_back(x) ;pre_value.push_back(par[x]) ;par[x] = fa ;return fa ;
}*/int temp_unite(int x, int y){pre_id.push_back(x) ;pre_value.push_back(par[x]) ;par[x] = y ;return y;
}int find1(int x){if (x == par[x]) return x;return temp_unite(x , find1(par[x]));
}
int find2(int x){if(par[x] == x) return x ;return par[x] = find2(par[x]) ;
}
void unite(int x , int y){int a = find2(x) ;int b = find2(y) ;if(par[a] == par[b]) return ;par[a] = b ;a = find2(x) , b = find2(y) ;
}
/// the process of find may change the array par
void reload(){for(int i = pre_id.size() - 1 ; i >= 0 ; i -- ){par[pre_id[i]] = pre_value[i] ;}pre_id.clear() ;pre_value.clear() ;
}
int main(){int n , m ;scanf("%d %d" , &n , &m) ;for(int i = 1 ; i <= m ; i ++ ){scanf("%d %d %d" , &E[i].st , &E[i].ed , &E[i].w) ;id[i] = i ;}int op ; scanf("%d" , &op) ;for(int i = 1 , k ; i <= op ; i ++ ){scanf("%d" , &k) ;for(int j = 1 , x ; j <= k ; j ++ ){scanf("%d" , &x) ;int w = E[x].w ;if(ma[w].size() == 0 || ma[w][ma[w].size() - 1] != i)ma[w].push_back(i) ;query[i][w].push_back(x) ;}}sort(id + 1 , id + m + 1 , cmp) ;init(n) ;for(int i = 1 ; i <= m ; i ++ ){int L = i , R = i ;while(E[id[R + 1]].w == E[id[L]].w && R + 1 <= m) R ++ ;int w = E[id[i]].w ;for(int j = 0 ; j < ma[w].size() ; j ++ ){int query_id = ma[w][j] ;if(ans[query_id]) continue ;for(int k = 0 ; k < query[query_id][w].size() ; k ++ ){int temp_edge = query[query_id][w][k] ;int st = E[temp_edge].st ;int ed = E[temp_edge].ed ;//cout << k << " " << query_id << st << " " <<ed  << "??";if(find1(st) != find1(ed))temp_unite(find1(st) , find1(ed) ) ;else{ans[query_id] = true ;break ;}}reload() ;}for(int j = L ; j <= R ; j ++ ){int st = E[id[j]].st ;int ed = E[id[j]].ed ;/*if(find2(st) != find2(ed))temp_unite(find1(st) , find1(ed) ) ;*/unite(st , ed) ;}//for(int kk = 1 ; kk <= n ; kk ++ ) cout << par[kk] << " " ; cout << endl ;pre_id.clear() ;pre_value.clear() ;i = R ;}for(int i = 1 ; i <= op ; i ++ ){printf("%s\n" , ans[i] ? "NO" : "YES") ;}return 0 ;
}

这篇关于Codeforces #446 (Div. 2) 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！