官方题解｜排位赛#4题解Q1-Q4
2024-02-18 13:22:50
发布于：浙江
ACGO 排位赛#4题解Q1-Q4
题解地址：排位赛#4题解Q5、Q6
赛事地址：排位赛#4
直播预告：1月20日（周六）下午4点-6点 B站ACGO官方账号 排位赛#4复盘（欢迎观看大型翻车现场）
直播主讲：アイドル老师 ：小码王C++ 信奥算法讲师，3年C++算法竞赛教学经验，第47届国际大学生程序设计竞赛亚洲区域赛铜奖。
Q1 夺宝升级
题目解析
个谜题，每个谜题 挑战成功需要当前等级至少为 ，挑战成功即可将当前等级提升 ，谜题挑战的顺序不做限制。
那么显然我们可以按照谜题挑战需要的等级，从小到大挑战谜题。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main() {
// cin, cout解绑加速输入输出
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> _;
while (_--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n), id(n);
// 读入数组a和数组b
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
// id 数组初始化为 [0, 1, ... , n - 1]
iota(begin(id), end(id), 0);
// 使用 id 数组根据a[i]值从小到大进行排序
sort(begin(id), end(id), [&](const int &_a, const int &_b) {
return a[_a] < a[_b];
});
// 按照 a[i] 从小到大遍历谜题
for (auto &i : id) {
if (k < a[i]) break;
k += b[i];
}
cout << k << '\n';
}
return 0;
}
复杂度分析
将谜题按照 从小到大排序时间复杂度为 。
Q2 公约数序列
提示1
如果一个数组的最大公约数大于 ，那么说明数组中的每个元素都有一个共同的质因数。
提示2
若 为奇数， 为偶数，那么 的值为多少？
题目解析
要使整个数组的最大公约数大于 ，每个元素都必须有一个共同的质因数，因此我们需要找到数组中出现次数最多的质因数，然后将有这个质因数的数字与没有这个质因数的元素合并，答案就是 数组的大小 - 出现次数最多质因数的出现次数。
因为数字是连续的，所以出现次数最多的质因数一定是 。因此，我们需要做的最少操作次数就是给定范围 内奇数的数量。
令 表示小于等于 的奇数的数量，那么答案就是 。
当需要做的最少操作次数小于等于 时答案为 YES 否则为 NO。
需要注意一个特殊情况是当 时， 如果 那么显然答案为 NO，否则若 答案显然为 YES。
AC代码
#include <bits/stdc++.h>
using namespace std;
int odd(int x) {
return x + 1 >> 1;
}
bool check(int l, int r, int k) {
if (l == r) return l > 1;
return odd(r) - odd(l - 1) <= k;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> _;
while (_--) {
int l, r, k;
cin >> l >> r >> k;
cout << (check(l, r, k) ? "YES" : "NO") << '\n';
}
return 0;
}
复杂度分析
对于每个查询我们可以直接计算出 odd(l - 1) 和 odd(r)，所以对于每个用例时间复杂度为 。
Q3 树枝
提示
三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。
题目解析
求给定大小为 的数组中选择三个元素能够构成一个三角形的方案数。
那么我们需要考虑三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。
那么一个比较明显的思路是直接三重循环枚举三条边，然后检查即可。
但是这种方法的时间复杂度为 。本题 显然此种做法无法在时限内通过本题。
那么接下来我们考虑如何优化枚举。
首先考虑真的需要枚举三条边吗？如果我们已经确定了两条较小的边 ，就可以确定最长的边的大小最大为 。
为了方便我们可以将数组从小到大排序，然后可以使用二分来确定合法最长边在数组中的范围。此做法时间复杂度为 。
由于本题为单测试点多测试用例，，所以此做法仍然无法通过本题。
本题的数据范围要求时间复杂度在 及以内的做法，可以考虑把二分优化掉。
在上述枚举两条较短边，再使用二分确定第三条边的做法中，从小到大枚举前两条边，那么他们的长度之和显然是逐渐增大的，确定的两条较小边 ，令数组中 第一个大于等于 的元素下标为 ，那么对于边 令数组中 第一个大于等于 的元素下标为 ，那么显然 ，也就是说第三条边的最大长度是不断变大的。
那么我们便可以不用每次都重复地使用二分来判断最长第三边的位置。而是直接使用一个变量 来表示 第一个大于等于 的元素在数组中的位置。随着第二条边的长度 的增大，那么 也是不断增大的。这样我们枚举出两条较小边 后，向后移动 直到 ，可选的第三条边的数量就是 。
AC代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> _;
while (_--) {
int n; cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
sort(begin(a), end(a));
i64 res = 0;
for (int i = 0; i + 2 < n; ++i)
for (int j = i + 1, k = i + 2; j + 1 < n; ++j) {
// 向后移动 k 至当前允许的最长的第三边的位置
while (k < n and a[i] + a[j] > a[k]) ++k;
res += k - j - 1;
}
cout << res << '\n';
}
return 0;
}
复杂度分析
两重循环枚举较小的两条边时间复杂度为 ，第三条边的范围随着第二条边从小到大枚举，也是不断增大的，内层的 while 循环在整个枚举第二条边的过程中最多执行 次，所以总的时间复杂度为 。
Q4 画板
提示1
至少需要几条直线可以构成一个封闭图形？
提示2
如果存在一组平行线和另一组斜率不同的平行线会是什么情况？
题目解析
提示1：最少 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形。
提示2：如果存在一组平行线和另一组斜率不同的平行线，那么必然可以构成一个封闭图形。
根据 提示2 我们将题目分成两种情况。
A. 存在一组平行线和另一组斜率不同的平行线。
B. 不存在一组平行线和另一组斜率不同的平行线。
对于 情况A，我们可以将所有斜率相同的直线的截距 放到一个集合中，令斜率为 但截距不同的直线数量为 。
若存在 则必然存在封闭区域。
对于 情况B，此时所有的直线中至多有一个斜率 中截距不同的直线数量 ， 对于其他斜率 。
那么对于 情况B 我们只需要考虑 提示1 的情况： 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形即可。
对此我们可以枚举直线 ，然后枚举直线 ，若存在两条直线 和直线 相交与不同的两点，则说明可以构成封闭图形。
在实现上，情况B 留给我们的特殊性质，使得我们可以通过枚举斜率 的方式得到更低的复杂度（思考下为什么）。
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr double EPS = 1e-8;
int check() {
int n; cin >> n;
map<int, set<int>> lines;
for (int i = 0; i < n; ++i) {
int k, b;
cin >> k >> b;
lines[k].insert(b);
}
// 斜率不同的平行线对应斜率数量统计
int same_slope_cnt = 0;
for (auto &[k, seq] : lines)
if (seq.size() > 1)
++same_slope_cnt;
// 超过一个斜率有一组平行线，满足情况A返回true
if (same_slope_cnt > 1) return true;
// 情况B：枚举斜率
for (auto &[k1, seq2] : lines) {
for (auto &b1 : seq2) {
// 设置交点为无穷大
double x1 = 1e9, y1 = 1e9;
// 统计不同交点数量
int cnt = 0;
for (auto &[k2, seq2] : lines) {
if (k2 == k1) continue;
// 最多只有一个斜率有超过一条直线，只取第一个即可
auto b2 = *begin(seq2);
// 计算交点
double x2 = 1.0 * (b2 - b1) / (k1 - k2);
double y2 = k1 * x2 + b1;
if (abs(x1 - x2) + abs(y1 - y2) > EPS) {
x1 = x2;
y1 = y2;
// 存在两个不同交点，构成封闭图形
if (++cnt >= 2)
return true;
}
}
}
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> _;
while (_--)
cout << (check() ? "Yes" : "No") << '\n';
return 0;
}
复杂度分析
对斜率相同的直线集合去重时间复杂度为 。
若为 情况A，此时便可直接得到答案。
若为 情况B，枚举直线时间复杂度为 ，枚举斜率的时间复杂度为 （思考下为什么）。
有帮助，赞一个