P9883题解

naroto2022 · 2024-02-05 17:19:51 · 题解

P9883题解

算法

• 就是问 a[] 最少有多少非零位置，才能使其生成的树状数组 c[] 符合条件。
• 如果 j+(j \ \operatorname{and} \ (-j))=i 的 c[j] 全是 0，但 c[i] 非 0，那么 a[i] 就必须非 0；
• 如果 j+(j \ \operatorname{and} \ (-j))=i 的 c[j] 只有一个非 0，但 c[i] 为 0，那么 a[i] 就必须非 0；
• 可以证明，其他情况下都可以让 a[i] 为 0。

代码

#include<bits/stdc++.h>
const int N=1e5+5;
int n,a[N],b[N],ans;
char sc[N];
int main(){
    int T;
    scanf("%d",&T);
    for(;T--;){
        scanf("%d %s",&n,sc+1);
        ans=0;
        for(int i=1; i<=n; i++) a[i]=sc[i]-'0',b[i]=0;
        for(int i=1; i<=n; i++){
            if(!b[i]&&a[i]||b[i]==1&&!a[i]) ++ans;
            if(a[i]&&(i&-i)+i<=n) ++b[(i&-i)+i];
        }
        printf("%d\n",ans);
    }
    return 0;
}