【每日一题】5月25日题目精讲

题号 NC14414
名称 小AA的数列
来源 Wannafly挑战赛4
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

异或有一个很快乐的一点就是,异或零什么都不会发生,异或偶数个1是0,异或奇数个1是1,于是我们就可以按位计算1的个数(奇偶性)了。
目标是求区间异或之和,所以我们考虑统计前缀,即前i个数中每一位为1的个数,然后算出所有符合条件的子区间当前位有多少个1就行了。(这是套路啊套路)
先不考虑区间长度为偶数这个限制:
显然枚举区间两个端点要超时,我们看能不能只枚举一个端点:
(具体分析问题的时候只需要考虑第x位,x相当于一个循环变量)
先枚举左端点l,每个和他1的个数的前缀和奇偶性不同的右端点,都会对答案有的贡献(在第x位贡献一个1)。
所以用一个数组cnt[j][0/1]来统计前缀和sum的第j个后缀(sum[j]到sum[n])里面1的个数为奇数/偶数的个数就行。
题面要求区间长度必须为偶数怎么办?
cnt[j]计算的时候不要从cnt[j+1]来,从cnt[j+2]来,即跳过会让区间长度变成奇数的点,这样就可以啦。

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目6月1日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/9114058d80954f418bb97be9b861459e
2 回复 分享
发布于 2020-05-22 21:55
https://blog.nowcoder.net/n/f0c66c74302943ed96a0188e75ed617e
1 回复 分享
发布于 2020-05-23 21:03
https://blog.nowcoder.net/n/392a75adddc04c9aadb9d98368bfe5f2
1 回复 分享
发布于 2020-05-23 15:19
https://blog.nowcoder.net/n/b7efe069ad58453d927e6800f3361bda
1 回复 分享
发布于 2020-05-23 14:25
https://blog.nowcoder.net/n/68554410a223484bad74416b7f0375cd
1 回复 分享
发布于 2020-05-22 20:16
https://blog.nowcoder.net/n/79a3072eb02c4dfb85e25d483c24a56e
1 回复 分享
发布于 2020-05-22 18:51
https://blog.nowcoder.net/n/665bad31179f4b82bb9f0702910ba15c
1 回复 分享
发布于 2020-05-22 17:41
https://blog.nowcoder.net/n/b1816a1594eb41389e78659f45467d06
1 回复 分享
发布于 2020-05-22 16:01
https://blog.nowcoder.net/n/e93b8f2c9078436ca59c743018f81900
1 回复 分享
发布于 2020-05-22 15:48
https://blog.nowcoder.net/n/4dacd8e372de4199a30442b4eee1849a
1 回复 分享
发布于 2020-05-22 14:03
2
1 回复 分享
发布于 2020-05-22 11:45
https://blog.nowcoder.net/n/f7c3452fa37645728f4bddd3a9b64a34
点赞 回复 分享
发布于 2020-05-31 14:30
https://blog.nowcoder.net/n/b35b67ab19e44742b8020fafd0bf602e
点赞 回复 分享
发布于 2020-05-31 07:51
https://blog.nowcoder.net/n/74beaaf9368c486f89c98c3fe39650c9
点赞 回复 分享
发布于 2020-05-30 08:54
https://blog.nowcoder.net/n/c8b047d05e284d22a21cb93c2a1f6fb5
点赞 回复 分享
发布于 2020-05-29 21:26
https://blog.nowcoder.net/n/8dc4f7fc2c2946ac9a3fbe7d75e5ce2c
点赞 回复 分享
发布于 2020-05-28 11:25
https://blog.nowcoder.net/n/7fcefdfa7a3f47009a5674c045e4d241
点赞 回复 分享
发布于 2020-05-27 16:03
https://blog.nowcoder.net/n/4db80492490c4b62883456e37e36f973
点赞 回复 分享
发布于 2020-05-27 12:50
https://blog.nowcoder.net/n/a887de9365964cc0b3175715b4b5b134
点赞 回复 分享
发布于 2020-05-26 19:08
这题目补的好累,痛苦 https://blog.nowcoder.net/n/a1bd0c347d3043eb80c20bcb2fb13c6a 总算写出来了
点赞 回复 分享
发布于 2020-05-26 12:21

相关推荐

03-15 14:55
已编辑
门头沟学院 golang
bg:双非学院本 ACM银 go选手timeline:3.1号开始暑期投递3.7号第二家公司离职顽岩科技 ai服务中台方向 笔试➕两轮面试,二面挂(钱真的好多😭)厦门纳克希科技 搞AI的,一面OC猎豹移动 搞AIGC方向 一面OC北京七牛云 搞AI接口方向 一面OC上海古德猫宁 搞AIGC方向 二面OC上海简文 面试撞了直接拒深圳图灵 搞AIGC方向一面后无消息懒得问了,面试官当场反馈不错其他小厂没记,通过率80%,小厂杀手😂北京字节 具体业务不方便透露也是AIGC后端方向2.28约面 (不知道怎么捞的我,我也没在别的地方投过字节简历哇)3.6一面 一小时 半小时拷打简历(主要是AIGC部分)剩余半小时两个看代码猜结果(经典go问题)➕合并二叉树(秒a,但是造case造了10分钟哈哈)一天后约二面3.12 二面,让我挑简历上两个亮点说,主要说的docker容器生命周期管理和raft协议使用二分法优化新任leader上任后与follower同步时间。跟面试官有共鸣,面试官还问我docker底层cpu隔离原理和是否知道虚拟显存。之后一道easy算法,(o1空间解决 给定字符串含有{和}是否合法)秒a,之后进阶版如何用10台机加快构建,想五分钟后a出来。面试官以为45分钟面试时间,留了18分钟让我跟他随便聊,后面考了linux top和free的部分数据说什么意思(专业对口了只能说,但是当时没答很好)。因为当时手里有7牛云offer,跟面试官说能否快点面试,马上另外一家时间到了。10分钟后约hr面3.13,上午hr面,下午走完流程offer到手3.14腾讯技术运营约面,想直接拒😂感受: 因为有AIGC经验所以特别受AI初创公司青睐,AIGC后端感觉竞争很小(指今年),全是简历拷打,基本没有人问我八股(八股吟唱被打断.jpeg),学的东西比较广的同时也能纵向深挖学习,也运气比较好了哈哈可能出于性格原因,没有走主流Java路线,也没有去主动跟着课写项目,项目都是自己研究和写的哈哈
烤点老白薯:你根本不是典型学院本的那种人,贵了你这能力
查看7道真题和解析
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务