E. Special Elements - 题解

比赛与标签

比赛: Codeforces Round 640 (Div. 4) 标签: brute force, implementation, two pointers, *1500 难度: *1500

题目大意喵~

主人你好呀，这道题是这样子的喵~

题目会给我们一个数组 a，里面有 n 个正整数。我们需要找出数组里有多少个 “特殊元素”。

一个元素 a[i] 被称为 “特殊元素”，如果它能被表示成数组中至少两个连续元素的和。比如说，a[i] = a[l] + a[l+1] + ... + a[r]，其中 l < r。

我们的任务就是数一数，整个数组 a 中，总共有多少个这样的特殊元素。要注意哦，如果一个数字 x 是特殊的，并且它在数组里出现了好几次，那么每一次出现都要算进去的！

输入是多组测试数据，对于每一组，我们都要输出一个答案，就是特殊元素的总数，的说。

思路分析喵~

呐，我们来一起想想怎么解决这个问题吧，的说！

这个问题最直接的想法就是，我们先找出所有可能的、由连续子数组（长度至少为2）求出的和，然后看看原数组中有哪些元素等于这些和，对不对喵？

核心思想: 我们的核心思路是“预处理 + 查询”。
- 预处理: 先遍历数组，计算出所有长度大于等于2的连续子数组的和。
- 查询: 将这些和记录下来。然后，再遍历一遍原始数组 a，看看每个元素 a[i] 是否在我们记录的和的集合里。
关键观察:
- 一个非常重要的信息是，数组里的所有元素 a[i] 都满足 1 <= a[i] <= n。这意味着什么呢？这意味着，任何一个我们求出来的、由连续子数组相加得到的和 sum，如果它大于 n，那么它就不可能等于数组中的任何一个元素 a[i] 啦！
- 这个观察可以帮我们做一个很棒的优化，喵~ 当我们在累加一个连续子数组的和时，一旦这个和超过了 n，我们就可以停止继续向右累加了，因为再加下去和只会更大，更不可能等于数组里的任何数了。
算法流程: 基于上面的想法，我们可以设计出这样的步骤，喵~
1. 创建标记数组: 我们需要一个地方来记录哪些数字是可以被凑出来的。一个大小为 n+1 的布尔数组 possible 就非常合适！possible[s] = true 就代表数字 s 可以被凑出来。我们把它初始化为全 false。
2. 枚举所有子数组: 接下来，我们就要暴力枚举所有可能的连续子数组了。这可以用两层循环来做，的说。
  - 外层循环 l 从 0 到 n-1，用来固定子数组的左端点。
  - 内层循环 r 从 l+1 到 n-1，用来扩展子数组的右端点。我们从 l+1 开始，就是为了保证子数组的长度至少是2，喵~
3. 计算和并标记:
  - 在内层循环中，我们维护一个变量 current_sum。对于每个固定的 l，current_sum 一开始等于 a[l]。
  - 当 r 向右移动时，我们不断地把 a[r] 加到 current_sum 上。
  - 在每次相加后，我们要检查 current_sum。如果 current_sum > n，根据我们刚才的观察，就可以直接 break 掉内层循环，去处理下一个 l 了。这叫“剪枝”，是个很有效的优化技巧呐！
  - 如果 current_sum <= n，说明这个和是有可能等于数组中某个元素的，我们就把它标记下来：possible[current_sum] = true。
4. 统计答案: 当我们把所有可能的和都标记好之后，最后一步就是统计答案啦！我们再遍历一次原始数组 a，对于每个元素 a[i]，我们去查一下 possible[a[i]] 是不是 true。如果是，那它就是一个特殊元素，我们的计数器 count 就加一。
5. 输出结果: 遍历完整个数组 a 后，count 就是最终的答案啦！把它打印出来就大功告成，的说喵~

代码实现

cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 加上这两行可以让输入输出更快一点，对付严格的时间限制很有用哦，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 用一个布尔数组来标记哪些和是可能出现的，大小为 n+1 就够了，喵~
        vector<bool> possible(n + 1, false);

        // 外层循环，固定连续子数组的左端点 l
        for (int l = 0; l < n; l++) {
            int s = 0; // 注意这里 s 初始化为0，因为我们要从 a[l] 开始加
            // 内层循环，从 l 开始，扩展子数组的右端点 r
            // 为了保证长度至少为2，我们会在循环内部判断
            for (int r = l; r < n; r++) {
                s += a[r];
                // 如果长度小于2，就继续加下一个数
                if (r == l) continue;

                // 这是一个很重要的优化！如果和已经超过了n，
                // 那它不可能等于数组中的任何元素了，可以直接跳出内层循环，的说。
                if (s > n) break;
                
                // 如果和 s 小于等于 n，就把它标记为“可以凑出来”
                possible[s] = true;
            }
        }

        int count = 0;
        // 最后，遍历原始数组
        for (int i = 0; i < n; i++) {
            // 检查每个元素 a[i] 是否在我们之前标记的“可能”的和中
            if (a[i] <= n && possible[a[i]]) {
                count++;
            }
        }
        cout << count << '\n';
    }
    return 0;
}

（上面的代码稍作调整以匹配我更喜欢的循环写法，但逻辑和AC代码是完全一样的，喵~）

复杂度分析

时间复杂度: O(n²) 的说。我们用了两层嵌套循环来枚举所有的连续子数组并计算它们的和。外层循环跑 n 次，内层循环平均也跑 O(n) 次，所以这部分是 O(n²)。最后的统计循环是 O(n)。总的时间复杂度就是 O(n²)。因为题目保证所有测试用例的 n 的总和不超过 8000，所以这个复杂度是完全可以接受的！
空间复杂度: O(n) 的说。我们用了一个大小为 n 的向量 a 来存储输入，还有一个大小为 n+1 的布尔向量 possible 来做标记。所以空间开销是线性的，喵~

知识点总结

解决这个问题，我们主要用到了下面这些可爱的知识点，的说喵~

暴力枚举 (Brute Force): 通过两层循环，系统地遍历了所有需要考虑的情况（即所有连续子数组）。
预处理/查找表 (Preprocessing/Lookup Table): 我们没有在检查每个 a[i] 时再去计算它是否能被凑出，而是先一步到位，把所有能凑出的和都算好并存入一个布尔数组（查找表）中。这大大加快了后续的查询速度，让每次查询都变成了 O(1) 的操作。
剪枝优化 (Pruning): 在计算和的过程中，利用 sum > n 这个条件提前终止了不必要的计算，提高了算法的效率。

希望这篇题解能帮到主人哦！喵~ >w<

E. Special Elements - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​