L. Fenwick Tree
题链
题目都说了 我们可以将这个序列看作二叉搜索树
我们显然序列越往后层数越高
我们一层一层的考虑
我们要是当前s[i]=1 显然是要往下一层传递一个贡献的
要是当前遍历到s[i]=1 但是 tr[i]=0 显然不行 tr[i]=1 满足
那么tr[i]>=2呢 我们显然可以找到一种组合方式让tr[i]=1
s[i]=0时同理 tr[i]=1显然不合法要让当前层加1变成2 因为大于2之后我们总有一种组合方式=0
void solve(){
int n;string s;cin>>n>>s;s=")"+s;
vector<int>d(n+10);
int ans=0;
for(int i=1;i<=n;i++){
if(s[i]=='0'){
if(d[i]==1) ans++;
}else{
if(d[i]==0) ans++;
d[i+(i&(-i))]++;
}
}
cout<<ans<<'\n';
}
标签:int,tr,显然,ICPC,Asia,East,Final,2021
From: https://www.cnblogs.com/ycllz/p/16940126.html