C++ 查询给定范围内偶数或奇数的概率
在给定的范围内找到数字奇偶校验的概率，即它是偶数还是奇数。例如，对于每个查询，我们需要打印表示概率的 p 和 q。
Input : N = 5, arr[] = { 6, 5, 2, 1, 7 }query 1: 0 2 2
query 2: 1 2 5
query 3: 0 1 4
Output : 0
3 4
1 2
在这个问题中，我们将维护两个数组，其中包含在该索引之前出现的奇数和偶数的数量。这简化了我们的问题，现在我们需要打印它们的计数和该范围内存在的元素数量。
寻找解决方案的方法
在这种方法中，我们维护两个数组。它们包含在第 i 个索引之前找到的偶数和奇数的数量，并像前缀和问题一样解决这个问题。
示例
#include <bits/stdc++.h>输出结果using namespace std;
void solve(int arr[], int n, int Q,int query[][3]){
int even[n + 1]; // 我们的数组用于计算偶数找到直到第 i 个索引
int odd[n + 1]; // 我们的数组用于计算找到第 i 个索引的几率
even[0] = 0; odd[0] = 0; // 因为我们正在做基于 1 的索引，所以我们只是将两个数组的第 0 个索引设置为 0
for (int i = 0; i < n; i++) {
if (arr[i] & 1) { // 如果我们找到奇数，我们增加奇数
odd[i + 1] = odd[i] + 1;
even[i + 1] = even[i];
}
else { // 否则我们甚至增加
even[i + 1] = even[i] + 1;
odd[i + 1] = odd[i];
}
}
for (int i = 0; i < Q; i++) { // 遍历查询
int r = query[i][2]; // 正确的范围
int l = query[i][1]; // 左范围
int k = query[i][0]; // 查询类型
int q = r - l + 1; // 给定范围内的元素数
int p;
if (k) // k 是查询的类型，我们正在寻找
//给定范围内具有相同奇偶校验的元素数
p = odd[r] - odd[l - 1];
else
p = even[r] - even[l - 1];
if (!p) // 如果 p 为零，我们只需打印 0
cout << "0\n";
else if (p == q) // 如果 p == q 我们打印 1
cout << "1\n";
else {
int g = __gcd(p, q);
cout << p / g << " " << q / g << "\n"; // 作为 p 并且不应该有一个共同的 gcd 所以我们划分 gcd
}
}
}
int main(){
int arr[] = { 6, 5, 2, 1, 7 }; // 给定数组
int n = sizeof(arr) / sizeof(int); // 我们数组的大小
int Q = 2; // 我们的查询数量
int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; // 给定查询
solve(arr, n, Q, query);
return 0;
}
03 4
以上代码说明
在上面的方法中，我们通过维护两个数组来计算第 i 个索引找到的偶数和奇数的数量。现在我们需要找到给定范围内存在的偶数或奇数的数量并打印该数字并打印存在的元素总数。
结论
在本教程中，我们解决给定范围内偶数或奇数概率的查询。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。我们希望本教程对您有所帮助。
以上是 C++ 查询给定范围内偶数或奇数的概率 的全部内容， 来源链接： utcz.com/z/351604.html
