【每日一题】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之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴