Lesson 6 - 阶段复习测试
2024年11月30日大约 15 分钟
3204 寻找最大和
问题分析
题目给定了 n 个正整数，要求从中选择 3 个数字，使得这 3 个数字的和最大且不超过给定的整数 m。我们需要通过穷举所有可能的 3 个数的组合，找出其中符合条件的最大和。如果没有符合条件的组合，则输出 0。
解题思路
- 遍历所有可能的 3 个数的组合：对于给定的 n 个数，我们可以选择任意 3 个数来构成组合。总共有 C(n, 3) 种组合方法，遍历每一种组合，计算其和，并且判断是否小于等于 m。
- 更新最大和：对于每一个符合条件的组合，检查其和是否比之前记录的最大和大。如果是，则更新最大和。
- 返回结果：如果找到了符合条件的组合，输出最大和，否则输出 0。
解题注意事项
- 需要保证遍历所有 3 个数的组合，可以通过三重循环来实现。
- 要确保每个组合的和小于等于 m，更新最大和。
- 如果没有找到符合条件的组合，记得输出 0。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int max_sum = 0; // 初始化最大和为0，表示没有找到符合条件的组合
// 穷举所有可能的3个数的组合
for(int i = 0; i < n - 2; i++) {
for(int j = i + 1; j < n - 1; j++) {
for(int k = j + 1; k < n; k++) {
int sum = a[i] + a[j] + a[k];
if(sum <= m) { // 如果和不超过m
max_sum = max(max_sum, sum); // 更新最大和
}
}
}
}
cout << max_sum << endl; // 输出结果
return 0;
}3203 图书管理员
问题分析
在图书馆的书架上，图书的编号从 1 到 1000，编号是连续的。我们需要编写一个程序，计算通过二分查找来找到指定图书时，系统需要进行多少次比较。
二分查找的基本思想是：
- 每次选取当前查找区间的中间元素进行比较。
- 根据比较结果决定继续在左半部分或右半部分进行查找。
- 查找会一直进行，直到找到目标元素或查找区间为空。
我们要计算的是在这个过程中，进行的比较次数。
解题思路
- 初始化查找区间：初始时查找区间是
[1, 1000]，其中 1 是最小编号，1000 是最大编号。 - 每次比较：在每次的查找过程中，计算当前区间的中间位置
mid = (L + R) / 2，并进行一次比较。 - 更新查找范围：根据比较结果，更新查找区间：
- 如果
mid == target，则找到了目标，查找结束。 - 如果
mid < target，则说明目标在右半部分，更新查找范围为[mid + 1, R]。 - 如果
mid > target，则说明目标在左半部分，更新查找范围为[L, mid - 1]。
- 如果
- 终止条件：当查找区间为空时，查找结束。
解题注意事项
- 二分查找的关键在于正确更新查找区间的左右边界。
- 每次计算中间位置时要注意
(L + R) / 2，以避免溢出（尽管这里范围不大，溢出不太可能，但保持良好的习惯是很重要的）。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main() {
int target; // 目标图书编号
cin >> target;
int L = 1, R = 1000; // 初始查找范围为1到1000
int cnt = 0; // 比较次数
// 使用二分查找
while (L <= R) {
cnt++; // 每进行一次查找就增加比较次数
int mid = (L + R) / 2; // 计算中间值
if (mid == target) {
break; // 找到目标图书，结束查找
}
else if (mid < target) {
L = mid + 1; // 如果目标在右半部分，更新查找范围
}
else {
R = mid - 1; // 如果目标在左半部分，更新查找范围
}
}
cout << cnt << endl; // 输出比较次数
return 0;
}5821 连环询问
问题分析
给定一个由 n 个正整数组成的序列，我们需要快速回答 m 次询问。每次询问给定一个区间 [L, R]，要求输出该区间内所有整数的和。
为了高效地解决这个问题，直接遍历区间进行求和可能会导致时间复杂度过高，尤其是在 n 较大时。我们可以利用前缀和数组来优化计算。
解题思路
前缀和：使用前缀和数组
pre，其中pre[i]表示从第 1 个元素到第i个元素的和。利用前缀和数组，我们可以在常数时间内计算任意区间的和。- 例如，对于区间
[L, R]，我们可以通过公式pre[R] - pre[L-1]得到该区间的和。
- 例如，对于区间
步骤：
- 首先构建前缀和数组
pre，使得pre[i]存储从第一个元素到第i个元素的和。 - 对于每次询问，直接通过
pre[R] - pre[L-1]计算区间[L, R]的和。
- 首先构建前缀和数组
解题注意事项
- 前缀和数组的大小应该是
n + 1，这样可以方便地处理从第一个元素开始的区间。 - 在处理区间查询时，注意数组下标的偏移，特别是
L和R的值需要正确映射到pre数组。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10; // 设置数组的最大大小
int arr[MAXN]; // 存储输入的数组
int pre[MAXN]; // 前缀和数组
int main() {
int n, m;
cin >> n >> m;
// 读入数组并计算前缀和
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
pre[i] = pre[i - 1] + arr[i]; // 更新前缀和
}
// 处理 m 次查询
for (int i = 0; i < m; ++i) {
int L, R;
cin >> L >> R;
cout << pre[R] - pre[L - 1] << endl; // 输出区间 [L, R] 的和
}
return 0;
}5820 丰富的周日生活
问题分析
小童希望参加尽可能多的活动，但每次只能参加一个活动，且每个活动只能从开始到结束一次完成。为了让他的周日生活更丰富，我们需要找出他最多能参加的活动数量。
这是一个典型的活动选择问题，可以通过贪心算法来解决：
- 贪心策略：每次选择结束时间最早的活动，因为这样可以留下更多的时间来参加其他活动。
解题思路
- 排序：首先将活动按结束时间升序排序。这样可以确保我们总是选择结束时间最早的活动，从而最大化剩余时间，参加更多的活动。
- 选择活动：在活动按结束时间排序后，首先选择第一个活动，然后遍历剩余活动，选择每个活动的开始时间不早于前一个已选活动的结束时间的活动。
步骤
- 读取所有活动的开始时间和结束时间。
- 按照结束时间排序活动。
- 使用贪心算法，遍历活动并选择符合条件的活动，最终得到最多的活动数。
提示
- 先对活动按结束时间排序，可以保证我们总是选择最合适的活动。
- 在选择活动时，要确保当前活动的开始时间不早于已选择活动的结束时间。
详情
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10; // 设置数组的最大大小
struct Activity {
int start, end;
};
// 定义比较函数，实现按结束时间升序排序
bool cmp(Activity a, Activity b) {
return a.end < b.end;
}
Activity arr[MAXN]; // 存储活动的数组
int main() {
int n;
cin >> n;
// 读取活动时间
for (int i = 0; i < n; ++i) {
cin >> arr[i].start >> arr[i].end;
}
// 按结束时间升序排序活动
sort(arr, arr + n, cmp);
// 贪心算法选择活动
int count = 0, last_end_time = -1;
for (int i = 0; i < n; ++i) {
if (arr[i].start >= last_end_time) {
count++; // 选择该活动
last_end_time = arr[i].end; // 更新最后一个活动的结束时间
}
}
cout << count << endl; // 输出最多能够参加的活动数
return 0;
}11613 门牌号码
问题分析
- 累加门牌号的和：从
k = 1开始，逐步计算从1到k的所有门牌号的和S(k)。 - 计算童童的门牌号：每次累加
S(k)后，计算x = S(k) - n，即童童家门牌号。 - 判断是否符合条件：检查
x是否满足1 <= x <= k，如果满足则输出x和k。 - 停止条件：找到符合条件的
x和k后，输出结果并结束程序。
解题注意事项
- 通过
for循环模拟计算门牌号的和，而不是直接使用等差数列公式。 - 每次计算的和
S(k)需要检查x = S(k) - n是否在有效的门牌号范围内，即1 <= x <= k。 - 最大门牌号不超过 40000，因此
k最大可以取到 40000。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int s = 0;
for (int i = 1; i <= 40000; i++) {
s += i; // 累加当前的门牌号 i
if (s > n && (s - n) % 2 == 0) { // 判断是否满足条件
cout << (s - n) / 2 << " " << i; // 输出童童家的门牌号和家庭数
break; // 找到解后退出循环
}
}
return 0;
}3309 查找数字是否出现
问题分析
在一个升序排列的整数序列中，我们需要判断给定的多个数字是否存在于该序列中。如果数字存在，输出 "YES"；如果数字不存在，输出 "NO"。
具体步骤如下：
- 给定一个升序排列的整数序列
a，长度为n。 - 我们需要查询
m个数字，判断它们是否出现在该序列中。 - 对于每个查询数字，我们需要判断其是否存在于升序序列
a中，若存在则输出 "YES"，否则输出 "NO"。
解题思路
由于序列是升序排列的，因此可以利用 二分查找 来提高查询效率。二分查找的时间复杂度是 O(log n)，相比线性查找的 O(n) 性能更优，适用于处理较大数据量的情况。
- 输入处理：首先读取序列的长度
n，然后读取升序序列a。 - 查询处理：对于每个查询数字，使用二分查找来检查其是否在序列
a中。 - 输出结果：对于每个查询数字，若查找成功，输出 "YES"；否则输出 "NO"。
解题注意事项
- 由于查询次数
m和序列长度n都很大，因此需要使用 二分查找 来优化查询时间。 - 可以利用标准库中的
binary_search来简化二分查找的实现，避免自己手动编写二分查找算法。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<long long> a(n); // 存储升序序列
for(int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> m;
while (m--) {
long long x;
cin >> x;
// 使用 binary_search 函数判断 x 是否在升序序列 a 中
if(binary_search(a.begin(), a.end(), x)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}3309 查找数字是否出现
问题分析
给定一个升序排列的整数序列，我们需要查询若干个数字是否存在于该序列中。如果数字存在，输出 "YES"；如果数字不存在，输出 "NO"。
具体步骤如下：
- 给定一个升序排列的整数序列
a，长度为n。 - 查询
m个数字，判断它们是否出现在该序列中。 - 对于每个查询数字，使用 二分查找 来判断它是否存在于升序序列
a中。 - 对于每个查询数字，如果存在，输出 "YES"；否则输出 "NO"。
解题思路
由于序列是升序排列的，我们可以利用 二分查找 来优化查询效率。二分查找的时间复杂度是 O(log n)，相比线性查找的 O(n) 性能更优，适用于处理较大数据量的情况。
- 输入处理：首先读取序列的长度
n，然后读取升序序列a。 - 查询处理：对于每个查询数字，使用 手动实现的二分查找 来检查其是否在序列
a中。 - 输出结果：对于每个查询数字，若查找成功，输出 "YES"；否则输出 "NO"。
解题注意事项
- 由于查询次数
m和序列长度n都很大，因此使用 二分查找 来优化查询时间。 - 由于问题要求使用 数组，所以我们需要使用原生数组而不是
vector来存储序列。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 10000000; // 设置数组的最大容量
int a[MAX_N]; // 存储升序序列
int n, m;
bool binary_search(int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] == x) {
return true; // 找到目标数字
}
if (a[mid] < x) {
left = mid + 1; // 搜索右半部分
} else {
right = mid - 1; // 搜索左半部分
}
}
return false; // 未找到目标数字
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> m;
while (m--) {
int x;
cin >> x;
if (binary_search(x)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}17273 平方之和
问题分析
给定 n 个正整数 a_1, a_2, ..., a_n，我们需要判断对于每个 a_i，是否存在两个正整数 x 和 y，使得 x^2 + y^2 = a_i。
我们可以通过穷举法来找到是否存在这样的 x 和 y，但是由于 a_i 的值可能非常大（最大可达到 10^6），我们需要考虑效率，避免直接穷举所有可能。
解题思路
- 对于每个整数
a_i，我们需要检查是否存在两个正整数x和y，使得x^2 + y^2 = a_i。 - 由于
x和y必须是正整数，所以我们可以通过遍历可能的x值来检查对应的y值。 - 我们可以遍历所有
x从1到sqrt(a_i)，然后检查y^2 = a_i - x^2是否是一个完全平方数，即y是否是一个正整数。 - 如果找到了满足条件的
x和y，则输出 "Yes"，否则输出 "No"。
解题注意事项
- 由于我们只需要判断是否存在两个正整数满足
x^2 + y^2 = a_i，所以遍历x的值时可以限制到sqrt(a_i)，以减少不必要的计算。 - 对于每个
x，只需要检查a_i - x^2是否为完全平方数，因此可以直接计算其平方根来验证。
代码实现
#include<bits/stdc++.h>
using namespace std;
bool check(int a) {
for (int x = 1; x * x <= a; ++x) {
int y2 = a - x * x;
int y = (int)sqrt(y2);
if (y * y == y2) {
return true; // 找到符合条件的 x 和 y
}
}
return false; // 没有找到符合条件的 x 和 y
}
int main() {
int n;
cin >> n;
while (n--) {
int a;
cin >> a;
if (check(a)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}9048 科技创新大赛
问题分析
童童参加了科技创新大赛并获得了科技创新奖，但他发现自己的小伙伴中有许多人也获得了奖项，尤其是其中的一部分人还获得了另一个奖项——特殊贡献奖。现在，童童希望统计出哪些人同时获得了两个奖项。
我们需要做的是：在两个奖项的获奖者中，找出哪些人的编号是重合的，并按在科技创新奖名单中的顺序输出这些人。
解题思路
- 我们有两个奖项的获奖者列表，一个是科技创新奖获奖者的编号，另一个是特殊贡献奖获奖者的编号。
- 任务是找出两个奖项的获奖者的交集，并按照科技创新奖获奖者的原始顺序输出。
- 我们可以通过使用数组来实现查找：对于特殊贡献奖的获奖者，我们将其编号标记为出现过，接着遍历科技创新奖的获奖者列表，检查每个获奖者是否同时出现在特殊贡献奖的获奖者列表中。
- 具体做法是，使用一个大小为100001（最大编号为100000）的布尔数组，记录每个编号是否获得了特殊贡献奖。
解题注意事项
- 由于编号最大为100000，因此可以使用一个长度为100001的数组来标记是否为特殊贡献奖的获奖者。
- 根据科技创新奖获奖者的顺序输出交集中的人。
代码实现
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int innovation_winners[n]; // 科技创新奖获奖者编号
bool contribution_winners[100001] = {0}; // 特殊贡献奖获奖者编号标记数组
// 读取科技创新奖获奖者
for (int i = 0; i < n; ++i) {
cin >> innovation_winners[i];
}
// 读取特殊贡献奖获奖者，并更新标记数组
for (int i = 0; i < m; ++i) {
int id;
cin >> id;
contribution_winners[id] = true;
}
// 输出同时获得两个奖项的获奖者
bool first = true;
for (int i = 0; i < n; ++i) {
if (contribution_winners[innovation_winners[i]]) {
if (!first) {
cout << " ";
}
cout << innovation_winners[i];
first = false;
}
}
cout << endl;
return 0;
}