首页 > 试题广场 >

小苯的美丽区间

[编程题]小苯的美丽区间
  • 热度指数：326 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯认为一个数 x 是美丽数，当且仅当：如果将 x 不停除以 2，直到 x 不整除 2 时停止，此时 x 恰好等于 1。
\bullet 如果一个数美丽，则其美丽值为：以上操作中除以 2 的次数。
\bullet 否则一个数不美丽，则其美丽值为 0。

现在小苯有一个长度为 n 的数组 a，他想知道 a 中所有连续子数组的和的美丽值之和是多少，请你帮他算一算吧。
形式化的：记数字 x 的美丽值为 f(x)，则请你求出 \sum_{l=1}^n\sum_{r=l}^n f(a_l+a_{l+1}+\dots+a_r)。
（其中 a_l+ a_{l+1}+\dots+a_r 表示 a 数组在 [l,r] 这一段区间的所有元素之和。）

输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^4 \right) 代表数据组数，每组测试数据描述如下：
第一行输入一个正整数 n\ (1 \leq n \leq 3 \times 10^5)，表示数组 a 的长度。
第二行 n 个正整数 a_1\ a_2\dots a_n\ (0 \leq a_i < 2^{30})，表示数组 a。
（保证同一个测试文件中的测试数据里，n 的总和不超过 3 \times 10^5。）


输出描述:
对于每个测试数据，在单独的一行输出一个整数表示答案。
示例1

输入

2
5
2 4 4 3 5
4
2 2 2 2

输出

15
13

说明

对于第二组测试数据：\{2,2,2,2\}；
所有长度为 1 的子区间和都是美丽的，因为 2 的二进制中只有一个 1，其美丽值为 1，因此总美丽值为 1 \times 4=4；
所有长度为 2 的子区间和都是美丽的，因为他们的和都是 4，4 的美丽值为 2，其总美丽值为 2 \times 3=6。
所有长度为 3 的子区间和都不是美丽的，因此美丽值总和为 0。
唯一一个长度为 4 的子区间和是美丽的，其总和为 8，美丽值为 3；
综上，所有区间的总美丽值之和为：4+6+0+3=13。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 16:11:44
题目链接 REAL738 小苯的美丽区间 题目描述 小苯定义一个数 是美丽数，当且仅当：将 不停除以 2，直到结果 不整除 2 时停止，此时 恰好等于 1。 如果一个数是美丽数，其美丽值为：以上操作中除以 2 的次数。 否则，其美丽值为 0。 现在给定一个长度为 的数组 ，请你 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 想回学校的奶酪希望奇迹发生
发表于 2025-07-02 12:30:17
分享一下这道题的题解～这道题目的是找到有多少个子数组的区间和是一个美丽值，再求它们的累加和所以我们可以使用前缀和找到子数组的区间和：PreSum[i] - PreSum[j]美丽值是指2的指数次方，我们可以提前记录一下所以，PreSum[i] - PreSum[j] = 2xPreSum[i] - 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

位运算 前缀和 哈希 阿里云
难度：
1条回答 675浏览

热门推荐

相关试题

小苯的美丽区间

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号