C++ を使用して、K 以上のビットまたは値を持つサブ配列の数を見つけるコードを作成します。

この記事では、C でビットごとの OR>=K を使用して部分配列の数を求める方法を簡単に説明します。したがって、配列 arr[] と整数 K があり、OR (ビットごとの 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 を使用して問題を解決するために 2 つの異なる方法を使用します -

ブルート フォースCrack

このアプローチでは、形成できるすべてのサブ配列を反復処理し、OR が K 以上で​​あるかどうかを確認するだけです。 「はい」の場合は、回答を追加します。

例

#include <bits/stdc++.h>
using 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 は指定された配列のサイズ) であるため、多くの時間がかかるため、ここでは効率的な方法を使用します。

効率的な方法

この方法では、OR 演算子のいくつかのプロパティを使用します。つまり、数値をさらに追加しても減少しないため、i から j に移動すると、OR が次のような部分配列が得られます。 K 以上の場合、範囲 {i,j} を含む各部分配列は K より大きい OR を持ちます。私たちはこの特性を利用してコードを改善しています。

例

#include <bits/stdc++.h>
#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 などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して、K 以上のビットまたは値を持つサブ配列の数を見つけるコードを作成します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。