时间复杂度 (A[i]^x)>(A[i]&x)



是否可以进一步优化这段计算的时间复杂度"(y^x) "(y &x)"在c++中?(您可以将布尔运算更改为其他形式,例如,这也可以写成log2(y)!=log2(x),这给出了相同的布尔输出,但这在c++编译器中具有更高的时间复杂度)'enter code here

#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;cin>>t;
while(t--){
int n;cin>>n;int A[n];
for(int i=0;i<n;i++){cin>>A[i];}
int q;cin>>q;
while(q--){
int l,r,x;
cin>>l>>r>>x;int count=0;
for(int i=l-1;i<r;i++){
if((A[i]^x)>(A[i]&x)){count++;}
}
cout<<count<<endl;
} 
}
return 0;
}

'这是我试图优化....的代码请以任何可能的方式提供帮助(输入的数量不能更改)

(y^x)>(y&x)相当于nlz(y) != nlz(x),其中nlz是返回其输入的前导零的个数的函数。

因此,为了计算数组A(A[i]^x)>(A[i]&x)为真的频率,我们可以创建一个小数组N,其中N[j]是数组Anlz(A[i]) == j为真的元素数。那么(A[i]^x)>(A[i]&x)为真的次数等于n - N[nlz(x)]

这样就不会在真正重要的A上循环了。创建数组N仍然需要对A进行循环,但是外部循环的每次迭代只需要一次,而不是对每个单独的x

c++ 20内置了nlz函数,命名为std::countl_zero

相关内容

  • 没有找到相关文章

最新更新