江南程序设计竞赛联盟暑期多校训练·第二场（个人补题B,H,L）

题目B. k -- GCD 可分数列知识点二分贪心gcd关键根据每加入一个数字的gcd值不会大于元素为单调性质想到可以用二分做如果想到这点的话下面就是对段数进行贪心思路在[1,min(a)]上二分答案思路就是贪心的将数字加入如果把当前位置的数字加入后不满足条件则在当前位置的左边划分段数大于k则取左区间否则取右区间注意分段时最后的边界还需要特别处理由于题目所给的a都是大于等于一的二分左端点可以从零开始代码#include bits/stdc.h using namespace std; #define int long long #define endl \n int n, k; const int N 1e410; int arr[N]; int check(int x) { if (x 0) return 0; int sum 0; int p 1; int gd arr[p]; while (p n) { if (gcd(gd, arr[p]) x) { gd gcd(gd, arr[p]); p; } else { sum; gd arr[p]; p; } } if (gd x) sum; return sum; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n k; int mi 1e910; for (int i 1; i n; i) { cin arr[i]; mi min(mi, arr[i]); } int l 0, r mi ; while (l 1 ! r) { int mid (l r) / 2; if (check(mid) k) l mid; else r mid; //cout l r mid check(mid) endl; } if (check(r) k) cout r; else cout l; //cout check(10) check(11) check(12); return 0; } /* 7 5 66 77 44 11 85 18 56 */题目H. 接力赛知识点区间合并关键左右可以任意走只需要关注y值即可思路将所有的y值都记录下来y值就可以看成区间进行合并只需将每个区间的左端点从小到大排序然后遍历如果下一个区间和当前区间重叠则合并更新右端点否则记录不连续的区间长并更新新的左右端点注意由于是坐标系AB的y值需要判定一下若A的y值小于等于B的y值则直接输出零否则再进行操作并且最好剔除掉AB两点之外的区间代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int N 1e510; int n; double a1, b1, a2, b2; vectorpairdouble, double v; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n a1 b1 a2 b2; for (int i 1; i n; i) { int X1, X2, Y1, Y2; cin X1 Y1 X2 Y2; if (Y1 b1 Y2 b2) v.push_back({Y1, Y2}); } if (b1 b2) { cout 0; return 0; } v.push_back({b1, b1 10}); v.push_back({b2 - 10, b2}); sort(v.begin(), v.end()); if (v.size() 0) { cout b1 - b2; return 0; } double l v[0].first, r v[0].second; double ans 0; for (int i 1; i v.size() - 1; i) { if (v[i].first r) { ans (v[i].first - r); l v[i].first; r v[i].second; } else { r max(r, v[i].second); } } cout ans; return 0; }题目L. 小组合作知识点贪心或 dp关键这题用贪心来写考虑的情况很多容易卡思路我是用的贪心的思路也是一知半解建议还是去看别人的我是用一个大顶堆存社牛值然后依次往下贪心当人数满足条件的时候分段但是存在多种情况导致这个贪心错误所以贪的时候还需要对当前段进行判断如果后面的值对于当前段的贡献不如对其他段的贡献则需要再进行处理这里直接附上原本的题解吧我说的可能还是有很多错误的地方代码#include bits/stdc.h using namespace std; #define int long long #define endl \n priority_queueint q; int ans 0; int now 0; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin n; for (int i 1; i n; i) { int x; cin x; q.push(x); } if (q.top() n) { cout -1; return 0; } while (!q.empty()) { now q.top(); if (now q.size()) break; vectorint v; while (now--) { v.push_back(q.top()); q.pop(); } if (!ans) { ans; continue; } if (v.size() ! 1) { if (v[1] v.size() - 1) { for (int i 1; i v.size() - 1; i) { q.push(v[i]); } } else ans; } else ans; } if (ans) cout ans; else cout -1; return 0; }