在本文中，我们将简要说明如何在 C++ 中求解按位 OR>=K 的子数组的数量。所以我们有一个数组 arr[] 和一个整数 K，我们必须找到 OR（按位或）大于或等于 K 的子数组的数量。所以这是给定问题的示例 -
Input: arr[] = {1, 2, 3} K = 3
Output: 4
Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2寻找解决方案的方法
现在我们将使用两种不同的方法来使用 C++ 来解决问题 -
暴力破解
在这种方法中，我们只是要遍历所有可以形成的子数组并检查 OR 是否大于或等于 K。如果是，那么我们将增加我们的答案。
示例
#includeusing namespace std; int main(){ int arr[] = {1, 2, 3}; // given array. int k = 3; int size = sizeof(arr) / sizeof(int); // the size of our array. int answer = 0; // the counter variable. for(int i = 0; i < size; i++){ int bitwise = 0; // the variable that we compare to k. for(int j = i; j < size; j++){ // all the subarrays starting from i. bitwise = bitwise | arr[j]; if(bitwise >= k) // if bitwise >= k increment answer. answer++; } } cout << answer << "\n"; return 0; }
输出
4
这种方法非常简单，但它有其缺陷，因为这种方法对于较高的约束不太好，对于较高的约束，它会花费太多时间，因为这种方法的时间复杂度是O(N *N)，其中 N 是给定数组的大小，因此现在我们将采用一种有效的方法。
立即学习“C++免费学习笔记（深入）”；
Avactis是一个强大的PHP在线购物系统拥有多个版本包括开源版本。它具备一个在线购物系统所需要的所有功能从产品到会员管理，订单和营销。可以无限分类和为产品指定任务数量的图片（支持自动生成缩略图）。使用自定义字段功能，让你可以更好地定义一个产品。该系统提供以非常灵活的方式来创建任意类型的促销活动如设置折扣代码，基于价格的折扣或基于数量的折扣等。
高效方法
在这种方法中，我们将使用 OR 运算符的一些属性，即即使我们添加更多数字，它也不会减少，因此如果我们从 i 到 j 得到一个子数组，其 OR 大于或等于 K，那么每个包含范围 {i,j 的子数组} 将具有大于 K 的 OR，我们正在利用此属性并改进我们的代码。
示例
#include#define N 1000 using namespace std; int t[4*N]; void build(int* a, int v, int start, int end){ // segment tree building if(start == end){ t[v] = a[start]; return; } int mid = (start + end)/2; build(a, 2 * v, start, mid); build(a, 2 * v + 1, mid + 1, end); t[v] = t[2 * v] | t[2 * v + 1]; } int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays. if (l > r) return 0; if(tl == l && tr == r) return t[v]; int tm = (tl + tr)/2; int q1 = query(2*v, tl, tm, l, min(tm, r)); int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r); return q1 | q2; } int main(){ int arr[] = {1, 2, 3}; // given array. int k = 3; int size = sizeof(arr) / sizeof(arr[0]); // the size of our array. int answer = 0; // the counter variable. build(arr, 1, 0, size - 1); // building segment tree. for(int i = 0; i < size; i++){ int start = i, end = size-1; int ind = INT_MAX; while(start <= end){ // binary search int mid = (start + end) / 2; if(query(1, 0, size-1, i, mid) >= k){ // checking subarray. ind = min(mid, ind); end = mid - 1; } else start = mid + 1; } if(ind != INT_MAX) // if ind is changed then increment the answer. answer += size - ind; } cout << answer << "\n"; return 0; }
输出
4
在这种方法中，我们使用二分搜索和线段树，这有助于将时间复杂度从 O(N*N) 降低到 O(Nlog(N))，这非常好好的。现在，与前一个程序不同，该程序还可以适用于更大的约束。
结论
在本文中，我们解决了一个问题，以查找具有 OR >= K 的子数组的数量使用二分搜索和线段树，时间复杂度为 O(nlog(n))。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。
