AtCoder|AtCoder Beginner Contest 239（A~E）题解 c语言|算法|图论|A~E

AtCoder Beginner Contest 239题解
文章目录

AtCoder Beginner Contest 239题解
- A - Horizon
- B - Integer Division
- C - Knight Fork
- D - Prime Sum Game
- E - Subtree K-th Max

A - Horizon 【题目链接】A - Horizon (atcoder.jp)
思路：模拟
【代码实现】

#include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y secondusing namespace std; const int N = 2e5 + 10; typedef long long LL; int main() {double n; scanf("%lf", &n); printf("%.9lf\n",sqrt(n * (12800000.0 + n)) ); return 0; }

B - Integer Division 【题目链接】B - Integer Division (atcoder.jp)
思路：模拟
【代码实现】

#include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y secondusing namespace std; const int N = 2e5 + 10; typedef long long LL; int main() {LL n; cin >> n; if(n < 0) { if(abs(n) / 10 * 10 ==abs(n)) cout << "-" << abs(n)/10; else cout << "-" << abs(n)/10 + 1; } else cout << n/10; return 0; }

C - Knight Fork 【题目链接】C - Knight Fork (atcoder.jp)
思路：判断八个方向上的某一个点，到所给的两个点的距离是否相等
知识点：模拟 + 数学
【代码实现】

#include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y secondusing namespace std; const int N = 2e5 + 10; typedef long long LL; int dx[8] = {1,2,2,1,-1,-2,-2,-1}; int dy[8] = {2,1,-1,-2,-2,-1,1,2}; bool check(int x1, int y1, int x2, int y2) { for(int i = 0; i < 8; i ++) { LL a = x1 + dx[i], b = y1 + dy[i]; LL xx1 = a - x1, yy1 = b - y1, xx2 = a - x2, yy2 = b - y2; if(xx1 * xx1 + yy1 * yy1 == 5 && xx2 * xx2 + yy2 * yy2 == 5) return true; } return false; }int main() { LL x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(check(x1, y1, x2, y2)) puts("Yes"); else puts("No"); return 0; }

D - Prime Sum Game 【题目链接】 D - Prime Sum Game (atcoder.jp)
【AtCoder|AtCoder Beginner Contest 239（A~E）题解】思路：判断ab中是否存在一个数，若这个数与cd中的任何一个数的和都不是质数说明前者获胜，反之后者胜
知识点：模拟 + 素数的判断
【代码实现】

#include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y secondusing namespace std; const int N = 110; typedef long long LL; bool is_prime(int n) { if(n < 2) return false; for(int i = 2; i <= n / i; i ++) if(n % i == 0) return false; return true; }int main() { int a, b, c, d; cin >> a >> b >> c >> d; // 判断a~b中是否存在一个数，若这个数与c~d中的任何一个数的和都不是质数说明前者获胜 for(int i = a; i <= b; i ++) { bool flag = true; for(int j = c; j <= d; j ++) { if(is_prime(i + j)) flag = false; } if(flag) { puts("Takahashi"); return 0; } } puts("Aoki"); return 0; }

E - Subtree K-th Max 【题目链接】E - Subtree K-th Max (atcoder.jp)
题意：求以v为根节点的子树的第k大的数
思路：递归深搜每一个节点（从根节点开始往下），将以该节点为根节点的所有子元素存储下来（前20个），然后进行降序排序，这样就得到了所有节点的前20个数的降序序列，输出第k大即可。
知识点：树/图的深度遍历 + 排序

为了方便对每一个节点的前20个元素进行存储和排序，我们用vector的二维数组来实现！

【代码实现】

#include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y secondusing namespace std; const int N = 2e5 + 10; typedef long long LL; int h[N], e[N], ne[N], idx; int w[N]; vector subtree[N]; // 存储所有子树（包含当前节点），前20大的数int n, q; bool cmp(int a, int b) { return a > b; }void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }void dfs(int u, int fa) { subtree[u].push_back(w[u]); for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; // 拿到节点编号 if(j != fa)// 保证只会往下搜索 { dfs(j, u); for(auto x : subtree[j]) subtree[u].push_back(x); } } sort(subtree[u].begin(), subtree[u].end(), cmp); // 降序排序 if(subtree[u].size() > 20) subtree[u].resize(20); // 限制大小：只取前20个数 }int main() {memset(h, -1, sizeof h); cin >> n >> q; for(int i = 1; i <= n; i ++) cin >> w[i]; // 存放1~n节点的点权 for(int i = 1; i < n; i ++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } dfs(1, 0); // 从1节点开始，第二个参数为父节点，节点1不存父节点 while(q --) { int v, k; cin >> v >> k; cout << subtree[v][k - 1] << endl; // 数组下标从0开始 }return 0; }