CodeForces 817E Choosing The Commander题解

题目

题意

有一个军队,每个人都有一个个性值,主角时不时会增加、或者移除一个指定个性值的战士,也可能试图添加一个指挥官。指挥官有两个属性,分别为个性值和领导力,如果一个现役战士的个性值与指挥官的个性值的异或小于领导力,那么这个战士会敬重该指挥官。

有n次操作,如果是试图添加指挥官的操作,要求输出现役战士中有多少人会敬重这位指挥官。

题解

个性值和领导力的取值范围都比较大,又有异或,比较明显地是在二进制上下功夫。像Trie树一样,对每位战士的个性值建树,每个节点是对应二进制位上的取值,最终到叶子节点的路径即可表示一个特定的个性值,在上面可以记录当前有几个战士具有这样的个性值。

如果没有异或这一回事,添加指挥官的时候只要逐位比较一遍即可,如果在第i位上指挥官的领导力为0,那么个性值为1的战士就不会敬重他,接着再比较个性值为0的战士里剩余的位;如果领导力为1,那么个性值为0的战士一定会敬重他,接着再比较个性值为1的战士里剩余的位。

有了异或之后,如果在第i位上指挥官的个性值为1,那么上述的判断条件就要倒过来,否则不用,就可以求出结果了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 《四柱特训班讲义》一书,是笔者根据2003年春举办的四柱特训班讲课记录的基础上整理出来的。它是以《四柱详真》...
    小狐狸娃娃阅读 14,396评论 1 29
  • 午后,在茶水处,仔细削一颗苹果。阳光暖洋洋的照在我背上,洒在我发上,苹果在手中随着刀子转动,红红的果皮长长的垂下,...
    你好_王姑娘阅读 2,622评论 0 1
  • 讲到PHP开发,就一定会提到fastcgi和php-fpm,这两个东西对PHP的性能有着至关重要的作用。在百度实习...
    Chuck_Hu阅读 7,675评论 2 19
  • $课文80水晶宫 867. Perhapsthe most extraordinary building of t...
    Berry521阅读 1,414评论 0 1
  • 当气球被气体膨胀到一定的程度,人就在紧张中有一种预感,“砰”的一声,气球即将爆裂了! 此情此景,孩子们的反...
    马多_阅读 2,929评论 2 3

友情链接更多精彩内容