首页 > 代码库 > Codeforces Round #408 (Div. 2)ABCD
Codeforces Round #408 (Div. 2)ABCD
A. Buying A House
分别向左右枚举，找到符合题意的点，输出最短的长度*10。
#include <bits/stdc++.h>using namespace std;int n, k, s, a[105];int main(){ scanf("%d%d%d", &n, &s, &k); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int m = 100; for(int i = s+1; i <= n; i++){ if(a[i] > 0 && a[i] <= k) { m = i-s; break; } } for(int i = s-1; i > 0; i--){ if(a[i] > 0&& a[i] <= k){ m = min(s-i, m); break; } } printf("%d\n", m*10); return 0;}
B. Find The Bone
模拟即可，如果掉进洞里输出，否则输出最后结果
#include <bits/stdc++.h>using namespace std;int n, m, k, a[1000005];int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1, x; i <= m; i++) { scanf("%d", &x); a[x] = 1; } if(a[1]) return 0*printf("1\n"); else { int u, v, x = 1; while(k--) { scanf("%d%d", &u, &v); if(x == u) { x = v; if(a[v]) return 0*printf("%d\n", x); } else if(x == v) { x = u; if(a[u]) return 0*printf("%d\n", x); } } printf("%d\n", x); } return 0;}
C. Bank Hacking
根据题意可知最大的结果不会超过 max{a_i}+2，
设寻找的第一个点为x, x周围的点为第二次寻找的点为y，设z为x外圈的点，寻找的第一点对答案的贡献为 a[x]
y对答案贡献为a[y]+1, z对答案恭喜为a[z]+2,因此决定答案的只有最大值max{a_i}和次大值{max_ai}-1（该值也可能不存在）
因此我们可以枚举每个点作为第一次寻找的点，并记录该点最大值和次大值对最后答案的贡献
#include <bits/stdc++.h>using namespace std;int n, m, k, s, a[300005];int vis_small[300005], vis_big[300005];map<int, int>Map;int main() { scanf("%d", &n); s = 1; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); Map[a[i]]++; if(a[i] > a[s]) s = i; } int big = a[s], small = big - 1, big_num = Map[big], small_num = Map[small]; //printf("%d %d %d %d\n", big, small, big_num, small_num); for(int i = 0, u, v; i < n-1; i++) { scanf("%d%d", &u, &v); if(a[u] == big) vis_big[v]++; else if(a[u] == small) vis_small[v]++; if(a[v] == big) vis_big[u]++; else if(a[v] == small) vis_small[u]++; } int ans = big+2; for(int i = 1; i <= n; i++) { int xx, yy; if(a[i] == big) { if(big_num == 1) xx = big; else if(vis_big[i] == big_num-1) { xx = big+1; } else xx = big+2; if(small_num == 0) yy = xx; else if(vis_small[i] == small_num) { yy = big; } else yy = big+1; } else if(a[i] == small) { if(vis_big[i] == big_num) { xx = big+1; } else xx = big+2; yy = xx; } else { if(vis_big[i] == big_num) { xx = big+1; } else xx = big+2; yy = xx; } ans = min(ans, max(xx, yy)); } printf("%d\n", ans); return 0;}
D. Police Stations
把所有的police同时放入队列，然后bfs.用map记录需要连接的边
#include <bits/stdc++.h>using namespace std;int n, k, d, cnt = 0;int vis[300005], x[300005], y[300005];typedef pair<int, int> P;vector<int>G[300005];queue<int>que;map<P, int>Map;int main() { scanf("%d%d%d", &n, &k, &d); for(int i = 1, x; i <= k; i++) { scanf("%d", &x); que.push(x); vis[x] = 1; } for(int i = 0, u, v; i < n-1; i++) { scanf("%d%d", &u, &v); x[i] = u, y[i] = v; Map[P(u, v)] = 1; G[u].push_back(v); G[v].push_back(u); } while(!que.empty()) { int u = que.front(); que.pop(); for(auto v : G[u]) { if(!vis[v]) { que.push(v); Map[P(u, v)] = 0; Map[P(v, u)] = 0; cnt++; vis[v] = 1; } } } printf("%d\n", n-1-cnt); for(int i = 0; i < n-1; i++) { if(Map[P(x[i], y[i])] > 0) printf("%d ", i+1); } //system("pause"); return 0;}
Codeforces Round #408 (Div. 2)ABCD
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。