我要招人

去企业版

首页 > 试题广场 >

小苯的美丽区间

[编程题]小苯的美丽区间

热度指数：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]$ 这一段区间的所有元素之和。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个正整数 ，表示数组  的长度。
第二行  个正整数 ，表示数组 。
（保证同一个测试文件中的测试数据里， 的总和不超过 。）

输出描述:

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

示例1

输入

输出

15
13

说明

对于第二组测试数据：；
所有长度为  的子区间和都是美丽的，因为  的二进制中只有一个 ，其美丽值为 ，因此总美丽值为 ；
所有长度为  的子区间和都是美丽的，因为他们的和都是 ， 的美丽值为 ，其总美丽值为 。
所有长度为  的子区间和都不是美丽的，因此美丽值总和为 。
唯一一个长度为  的子区间和是美丽的，其总和为 ，美丽值为 ；
综上，所有区间的总美丽值之和为：。

算法知识视频讲解

CCSU_xcq

题意要求和为2次幂，那么转化为两数之和问题，因为只有2次幂才有贡献，那么求出前缀和之后，枚举以i为结尾的前缀和，然后找差值为2次幂的前缀和，也就是

pre_sum[i] - pre_sum[j] = (1 << p)

而等式右边只有log级别的，所以O(nlogn)就可以解决

#include <iostream>
#include <vector>
#include <set>
#include <map>

std::vector<long long> tar;

void solve() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    long long pre_sum = 0;
    std::map<long long, int> mp;
    mp[0] ++;
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
        pre_sum = pre_sum + a[i];
        mp[pre_sum] ++;
    }

    pre_sum = 0;
    long long ans = 0;
    for (int i = 0; i < n; i ++) {
        pre_sum += a[i];
        for (int j = 0; tar[j] <= pre_sum; j ++) {
            auto target = pre_sum - tar[j];
            ans += mp[target] * j;
        }
    }
    std::cout << ans << std::endl;
}


int main() {
    int t = 1;
    std::cin >> t;
    tar.reserve(64);
    for (int i = 0; i < 60; i ++) {
        tar.push_back(1ll << i);
        // std::cout << tar.back() << ' ';
    }
    // std::cout << std::endl;
    while (t --) solve();
}

发表于 2025-09-20 16:14:18 回复(0)

提交观点

问题信息

位运算前缀和哈希阿里云

难度：

1条回答 19收藏 674浏览

小苯的美丽区间

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题