洛谷每日一题（P2141 [NOIP2014 普及组] 珠心算测验）

原题目链接：

P2141 [NOIP2014 普及组] 珠心算测验 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原题目截图：

思路分析：

代码的主要逻辑是：

1. 读取数组的大小n。
2. 创建一个unordered_set来存储不同的子数组和。
3. 创建一个向量nums来存储数组元素。
4. 对数组进行排序。（这一步是关键，如果不排序，那么可能导致一些小的结果无法被计算到）
5. 遍历数组，对于每个元素：
   • 检查当前元素是否已经在集合中，如果是，则增加计数器cnt。
   • 将当前元素与处理过程中的所有元素相加，并将结果插入到集合中，以确保不重复计算相同的子数组和。
   • 将当前元素添加到处理过程中的向量中。
6. 输出不同的子数组和的数量。

解决代码：

#include<iostream>  // 包含输入输出流的头文件
#include<vector>    // 包含向量的头文件
#include<unordered_set>  // 包含哈希集合的头文件
using namespace std;  // 使用标准命名空间
#include<algorithm>  // 包含算法的头文件

int main() {
    int n;  // 存储数组的大小
    cin >> n;  // 从标准输入读取数组的大小
    unordered_set<int> uset;  // 使用哈希集合来存储出现过的子数组和
    vector<int> nums(n);  // 创建一个大小为n的向量来存储数组元素
    int cnt = 0;  // 用于计数不同的子数组和的数量

    // 读取数组元素
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 对数组进行排序，这样相同的元素会相邻，便于计算子数组和
    sort(nums.begin(), nums.end());

    vector<int> process;  // 创建一个向量来存储处理过程中的元素

    // 遍历数组
    for (int i = 0; i < n; i++) {
        int x = nums[i];  // 当前元素
        if (uset.count(x)) cnt++;  // 如果当前元素已经在集合中，则增加计数
        // 更新集合
        for (int num : process) {
            uset.insert(num + x);  // 将当前元素与之前处理过的元素相加，如果结果不在集合中，则插入
        }
        process.push_back(x);  // 将当前元素加入到处理过程中
    }

    cout << cnt;  // 输出不同的子数组和的数量
    return 0;
}