题解：CF1973B Cat, Fox and the Lonely Array

2huk · 2024-05-21 22:13:48 · 题解

• 给定一个长度为 n 的数组 a，求最小的 k 使得对于任意两个正整数 i, j \in [1, n - k + 1] 都满足 \operatorname{or}_{t=i}^{i+k-1} a_t = \operatorname{or}_{t=j}^{j+k-1} a_t。

一种 \Theta(n \log a_i) 的做法。

我们考虑 0 \sim 19 这 20 个二进制位中，如果某一位 j 满足所有 a_i 的这一位都为 0，那么就不需要靠考虑这一位对答案 k 的影响了。因为无论 k 如何取值，或和的第 j 位一定为 0。

所以我们需要考虑的就是那些二进制位 j 使得存在至少一个 a_i 的第 j 位为 1。注意到无论 k 如何取值，或和的第 j 位一定为 1。

所以我们需要的就是对于所有 i 而言，将 i \sim i + k - 1 的数或起来后，使得第 j 位不为 0 的最小的 k。那么对于每个 i 求出的 k 的最小值即为答案。再对于每个二进制位 j 计算出最小的 k 再取最小就是真正的答案。

例如所有 a_i 的第 j 位为：

显然如果 k \le 3 的话 i = 4 就是一个不合法的位置。因为 a_4 \mid a_5 \mid a_6 的这一位为 0，但是 i = 5 计算出的答案的这一位为 1。

所以 k 就是最大的连续 0 的数量加一。

int n, a[N];
vector<int> s[30];
 
void Luogu_UID_748509() {
    for (int i = 0; i < 20; ++ i ) s[i].clear();

    fin >> n;
    for (int j = 0; j < 20; ++ j ) s[j].push_back(0);
    for (int i = 1; i <= n; ++ i ) {
        fin >> a[i];
        for (int j = 0; j < 20; ++ j )
            if (a[i] >> j & 1) s[j].push_back(i);
    }
    for (int j = 0; j < 20; ++ j ) s[j].push_back(n + 1);
    int res = 0;
    for (int i = 0; i < 20; ++ i )
        if (s[i].size() > 2) for (int a = 0, b = 1; b < s[i].size(); ++ a, ++ b )
            res = max(res, s[i][b] - s[i][a]);
    if (res == 0) res = 1;
    fout << res << '\n';
}