题目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 = 1e4+10; 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 = 1e9+10; 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 = 1e5+10; int n; double a1, b1, a2, b2; vector<pair<double, 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_queue<int> 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; vector<int> 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; }
