题目描述

难度分:$1381$

输入$n(2 \leq n \leq 1000)$，$k(1 \leq k \leq \frac{n(n+1)}{2}$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

$a$一共有$\frac{n(n+1}{2}$个非空连续子数组，也有对应的$\frac{n(n+1)}{2}$个子数组元素和。

从这$\frac{n(n+1)}{2}$个元素和中，选择$k$个，计算这$k$个数的按位与（AND）。

求这些按位与的最大值？

输入样例$1$

4 2
2 5 2 5

输出样例$1$

12

输入样例$2$

8 4
9 1 8 2 7 5 6 4

输出样例$2$

32

算法

按位贪心

这种位运算的题目一般都要按位来做，我们先预处理出$a$的前缀和数组$s$，然后双重循环遍历所有子数组$[l,r]$计算出所有子数组的和存入到$vals$数组中。

首先可以明确，由于要求的是$k$个数按位与的最大值，因此越高的位我们越希望它是$1$。

从高位往低位考虑，把$vals$中第$j$位是$1$的数存入$cands$数组中，如果$cands$中数字的个数不少于$k$，说明答案在这一位可以为$1$。接下来考虑第$j+1$位，从$cands$中选出第$j+1$位是$1$的数字做同样的考虑……，周而复始直到考虑完最低位。

复杂度分析

时间复杂度

按照题目所给的数据范围，子数组的累加和最大是$10^{12}$，大概用$40$位二进制就可以表示完，所以每位都考虑$n^2$个累加和时间复杂度为$O(40n^2)$，仍然是$O(n^2)$级别。

空间复杂度

空间消耗主要就是$vals$和$cands$两个数组，在最差情况下里面会存$n^2$个子数组和，因此额外空间复杂度为$O(n^2)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 1001;
int n, k, a[N];
LL s[N];

int main() {
    scanf("%d%d", &n, &k);
    s[0] = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    vector<LL> vals;
    for(int len = 1; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            LL sum = s[r] - s[l - 1];
            vals.push_back(sum);
        }
    }
    vector<LL> cands;
    LL ans = 0;
    for(int j = 40; j >= 0; j--) {
        cands.clear();
        for(int i = 0; i < vals.size(); i++) {
            if(vals[i]>>j&1) {
                cands.push_back(vals[i]);
            }
        }
        int cnt = cands.size();
        if(cnt >= k) {
            // 只要第j位为1的数不少于k个，这一位就可以是1
            ans |= 1ll<<j;      // 注意爆int，WA了好几发
            vals.clear();
            for(LL val: cands) vals.push_back(val);
        }
    }
    printf("%lld\n", ans);
    return 0;
}