B - Cat, Fox and the Lonely Array 二分 + 二拆前缀和
作者:
多米尼克領主的致意
,
2024-05-19 13:20:23
,
所有人可见
,
阅读 5
容易得出数组中具有单调性:随着k范围增大,多数相与运算的结果单调非减 因此具有单调性
可以二分
复杂度O(20nlogn)
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, bits = 20;
int t;
int pre[N][bits];
int a[N];
int n;
void init(){
for(int i = 1;i <= n;i++){
for(int j = 0;j < bits;j++){
if(a[i] & (1 << j)){
pre[i][j] = pre[i - 1][j] + 1;
}
else{
pre[i][j] = pre[i - 1][j];
}
}
}
}
bool check(int x){
int last;
for(int i = x;i <= n;i++){
ll ans = 0;
for(int j = 0;j < bits;j++){
if(pre[i][j] - pre[i - x][j])ans += 1 << j;
}
// cout << ans << endl;
if(i == x){
last = ans;
}
else{
if(ans != last)return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--){
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i];
init();
int l = 1, r = n;
while(l < r){
int mid = (l + r) >> 1;
// cout << mid << endl;
if(check(mid))r = mid;
else l = mid + 1;
}
cout << l << endl;
}
return 0;
}