首页 > 其他分享 >2021 ICPC Asia East Continent Final L

2021 ICPC Asia East Continent Final L

时间:2022-11-30 23:12:05浏览次数:78  
标签:int tr 显然 ICPC Asia East Final 2021

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

相关文章

  • 2021SWPUCTF-WEB(二)
    ez_unserialize​不知道在哪,御剑扫叭​有一个robots.txt​​一道反序列化好像是分析代码应该是admin=admin、passwd=ctf即可输出flag<?phpclasswllm{publi......
  • 提升访问github的速度,亲测可用2021.4.9
    操作可见:https://www.jianshu.com/p/0493dcc15d6f亲测有效。本人谷歌浏览器。简单来说就是利用https://www.ipaddress.com/来获得以下两个GitHub域名的IP地址github.com,......
  • 2021 昆明 F
    FindtheMaximum题链整理题意发现就是找一个连通块然后让他的平均绝对值最大平时的背包都是n2的显然不能做了我们考虑猜一些结论当时我想的就是可能最多不会很多点......
  • 2021SWPUCTF-WEB(一)
    gift_F12给了一个网站,题目提示是F12,就F12找一下​WLLMCTF{We1c0me_t0_WLLMCTF_Th1s_1s_th3_G1ft}jicao一个代码,逻辑很简单​大概就是通过POST的方式传一个参数id=w......
  • try-cathch- finally 捕获错误 throw抛出异常
    语法结构强壮代码try{可能会错的代码}catch(err){捕获错误}finally{不管语法正确错误都会执行不会影响后面代码的执行} <body><p>123</p><script>......
  • 2022icpc西安(The 2022 ICPC Asia Xian Regional Contest)
    C#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;voidsolve(){i64a,b,c;cin>>a>>b>>c;i64tmp=1;i64ans=c*b;......
  • Flutter vs React Native:哪个是2021年的最佳选择?
    转载https://baijiahao.baidu.com/s?id=1710194842067466597&wfr=spider&for=pc计划在2021年进行响应式开发?但不确定应该选择哪种技术来快速且低成本的开发应用程序?如果......
  • DTCC | 2021中国图数据库技术大会链接分享
    DTCC|2021中国图数据库技术大会链接分享​​DTCC|2021中国图数据库技术大会链接分享​​​​一、新一代分布式架构​​​​二、数据流通与数据交易​​​​三、业务模型......
  • 整合SpringBoot + Dubbo + Nacos 出现 Unable to make protected final java.lang.Cla
    版本SpringBoot:2.7.3Dubbo:3.0.4Nacos:2.0.3异常信息如下Unabletomakeprotectedfinaljava.lang.Classjava.lang.ClassLoader.defineClass(java.lang.String,......
  • 关于final关键字的一些总结
    final关键字主要用在三个地方:变量、方法、类。1.对于一个final变量,如果是基本数据类型的变量,则其数值一旦在初始化之后便不能更改;如果是引用类型的变量,则在对其初始化之后便......