CF1847B 题解

· · 题解

题意

给定一个 n 位的数组 a_i，并将 a_i 分开成 ans1 个连续的部分，并使得 a_i \land a_2 \dots a_n = a_1 \land a_2 \dots a_i + a_{i + 1} \land a_{i + 2} \dots a_j + a_{j + 1} \land a_{j + 2} \dots a_n，并输出 ans1 的最大值。

思路

本题目主要考察与运算。

首先设 a_1 \land a_2 \dots a_i 为 A，a_{i + 1} \land a_{i + 2} \land a_n 为 B。根据题目，A + B=A \land B，且 A \land B \leq \min(A,B) \leq A + B(A,B \geq 0)，所以 A \land B = \min(A,B) = A + B。因为 \min(A,B) = A + B(A,B \geq 0)，所以 A = B = 0。所以如果数组 a 能满足题意的分成几个连续的部分，a_i \land a_2 \dots a_n = 0。所以如果数组的 a_i \land a_2 \dots a_n > 0，输出 1 即可。

然后，我们设 ans1 = 1，我们遍历数组，依次寻找能使 a_i \land + a_{i + 1} \dots a_j = a_{j + 1} \land a_{j + 2} \dots a_n 的最小的 j(j < n)。如果找得到，就意味着剩下的数组还能继续分割，所以 ans \gets ans + 1,i \gets j + 1。因为计算 a_{j + 1} \land a_{j + 2} \dots a_n 耗时很大，我们需要预处理。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005];
int ask[200005];
inline int find(int x) {
    int anss = a[x];
    if(anss == 0) return x;
    x++;
    for(;x <= n;x++) {
        anss &= a[x];
        if(anss == 0) return x;
    }
    return -114514;
}
signed main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
        memset(ask,0,sizeof(ask));
        ask[n] = a[n];//预处理
        for(int i = n - 1;i >= 1;i--) ask[i] = ask[i + 1] & a[i];
        int ans = ask[1],ans1 = 1;
        if(ans) {
            printf("1\n");
            continue;
        }
        for(int i = 1;i <= n;) {
            int x = find(i);
            if(x < i or x == n or ask[x + 1] != ans) {
                printf("%d\n",ans1);
                break;
            }
            ans1++;
            i = x + 1;
        }
    }
}