字节青训-连续子串和的整除问题、统计班级中的说谎者
目录
一、连续子串和的整除问题
问题描述
小明是一个五年级的小学生，今天他刚刚学习了整除，想练习一下自己的掌握情况。他在纸上写了一个长度为 n 的正整数序列，a_0, a_1,..., a_{n - 1}，然后想了一个正整数 b，他想知道这个序列有多少个连续子串的和满足能够被 b 整除。你可以帮帮他吗？
输入格式
共两行，第一行包含两个正整数 n(1 <= n <= 10^5) 和 b(1 <= b <= 10^8)，第二行包含 n 个正整数，表示 a_0, a_1,..., a_{n - 1}(1 <= a_i <= 10^4)。
输出格式
共 1 行，一个整数，表示这个序列有多少个连续子串的和满足能够被 b 整除。
输入样例 1
3 3 1 2 3
输出样例 1
3
数据范围
50%的数据：n(1 <= n <= 10^3)。
100%的数据：n(1 <= n <= 10^5)。
解题思路：
问题理解
我们需要找到一个长度为 n 的正整数序列中，有多少个连续子串的和能够被给定的正整数 b 整除。
数据结构选择
由于 n 的范围最大可以达到 10^5，直接暴力枚举所有子串的和显然是不可行的，因为这会导致时间复杂度为 O(n^2)，这在 n 较大时会超时。
算法思路
我们可以利用前缀和的思想来优化这个问题。具体步骤如下：
-
前缀和数组：首先计算序列的前缀和数组
prefixSum，其中prefixSum[i]表示从序列的开始到第i个元素的和。 -
余数计数：使用一个哈希表（或数组）来记录每个前缀和模
b的余数出现的次数。 -
计算结果：对于每个前缀和
prefixSum[i]，我们只需要知道在它之前有多少个前缀和的余数与prefixSum[i]的余数相同。因为如果两个前缀和的余数相同，那么它们之间的子数组的和一定是b的倍数。
具体步骤
- 初始化一个前缀和数组
prefixSum，并计算每个前缀和。 - 初始化一个哈希表
remainderCount，用于记录每个余数出现的次数。 - 遍历前缀和数组，对于每个前缀和
prefixSum[i]，计算其模b的余数remainder。 - 如果
remainderCount中已经存在remainder，则说明之前有相同余数的前缀和，这些前缀和与当前前缀和之间的子数组的和是b的倍数。 - 将当前余数
remainder的计数加到结果中，并将remainder的计数加 1。
最终代码：
#include <iostream>
#include <vector>
#include <unordered_map>
int solution(int n, int b, std::vector<int> sequence) {
std::vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + sequence[i];
}
std::unordered_map<int, int> remainderCount;
int result = 0;
for (int i = 0; i <= n; ++i) {
int remainder = prefixSum[i] % b;
if (remainder < 0) remainder += b; // 处理负余数
// 查找之前有多少个前缀和的余数与当前余数相同
if (remainderCount.find(remainder) != remainderCount.end()) {
result += remainderCount[remainder];
}
// 更新余数计数
remainderCount[remainder]++;
}
return result;
}
int main() {
std::vector<int> sequence = {1, 2, 3};
std::cout << (solution(3, 3, sequence) == 3) << std::endl;
return 0;
}运行结果：
二、统计班级中的说谎者
问题描述
班里有 N 个学生，第 i 个学生的分数是 A_i。当且仅当分数 <= A_i 的学生数量多于分数比他高的数量时，第 i 个学生会说谎。求出有多少学生会说谎。
输入格式
- 输入
N学生的成绩，包含A_1, A_2, ..., A_N
输出格式
对于每组数据，输出有多少学生会说谎。
数据范围
- $1 \leq N \leq 100$
- $0 \leq A_i \leq 100$
示例输入
100 100 100
示例输出
3
示例输入
2 1 3
示例输出
2
示例输入
30 1 30 30
示例输出
3
示例输入
19 27 73 55 88
示例输出
3
示例输入
19 27 73 55 88 88 2 17 22
示例输出
5
解题思路：
问题理解
我们需要判断每个学生是否会说谎。具体来说，当且仅当分数 <= A_i 的学生数量多于分数比他高的数量时，第 i 个学生会说谎。
数据结构选择
我们可以使用一个数组来存储学生的分数，然后通过遍历数组来统计每个分数的出现次数。
算法步骤
- 统计每个分数的出现次数：使用一个数组
count，其中count[i]表示分数i出现的次数。 - 计算前缀和：使用一个数组
prefix_sum，其中prefix_sum[i]表示分数小于等于i的学生总数。 - 判断每个学生是否说谎：对于每个学生
A[i]，计算分数小于等于A[i]的学生数量和分数大于A[i]的学生数量，判断是否满足说谎条件。
最终代码：
#include <iostream>
#include <vector>
#include <algorithm>
int solution(std::vector<int> A) {
int N = A.size();
std::vector<int> count(101, 0); // 统计每个分数的出现次数
std::vector<int> prefix_sum(101, 0); // 前缀和数组
// 统计每个分数的出现次数
for (int score : A) {
count[score]++;
}
// 计算前缀和
for (int i = 1; i <= 100; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + count[i];
}
int liar_count = 0;
// 判断每个学生是否说谎
for (int score : A) {
int less_or_equal = prefix_sum[score];
int greater = N - less_or_equal;
if (less_or_equal > greater) {
liar_count++;
}
}
return liar_count;
}
int main() {
// Add your test cases here
std::cout << (solution({100, 100, 100}) == 3) << std::endl;
std::cout << (solution({2, 1, 3}) == 2) << std::endl;
std::cout << (solution({30, 1, 30, 30}) == 3) << std::endl;
std::cout << (solution({19, 27, 73, 55, 88}) == 3) << std::endl;
std::cout << (solution({19, 27, 73, 55, 88, 88, 2, 17, 22}) == 5) << std::endl;
return 0;
}运行结果：
原文地址：https://blog.csdn.net/m0_73302939/article/details/143779967
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！