欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces Round #674 D.Non-zero Segments【前缀和 | set】

程序员文章站 2022-04-15 18:23:37
题目链接题目描述:题解:好题啊~不知道为啥,我感觉用英文比中文写题解更简洁。Firstly, let’s understand that the sum of the segment [l;r][l;r][l;r] is zero if pr−pl−1p_r-p_{l-1}pr​−pl−1​ is zero (in other words, pl−1=prp_{l-1}=p_rpl−1​=pr​), where pip_ipi​ is the sum of the first iii ele...

题目链接

题目描述:

Codeforces Round #674 D.Non-zero Segments【前缀和 | set】


题解:

好题啊~
不知道为啥,我感觉用英文比中文写题解更简洁。
Firstly, let’s understand that the sum of the segment [ l ; r ] [l;r] [l;r] is zero if p r − p l − 1 p_r-p_{l-1} prpl1 is zero (in other words, p l − 1 = p r p_{l-1}=p_r pl1=pr), where p i p_i pi is the sum of the first i i i elements ( p 0 = 0 p_0=0 p0=0).
Let’s iterate over elements form left to right and add all prefix sums in the set. if we get the sum that is already in set, we get some segment with sum 0, and we need to fix it somehow. Let’s insert some huge number before the current element in such way that all prefix sums starting from the current elements to the end will be significantly bigger than all prefix sums to the left. in words of implementation, we just get rid of all prefix sums to left (clear the set) and continue doing the same process starting from the current element (so we just cut off the prefix of the array)

In AC code, when we clear the set and restarts the process(mentioned above) from the current element, the (sum-x), the previous element of the current element, should be inserted into the set. The same role as the element 0 in the original set is used to check whether the sum of all the elements(from current element to right) is zero.


AC Codes:

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7;



int main() {
    //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    set<long long> s{0};
    long long sum = 0, x;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> x;
        sum += x;
        if (s.count(sum)) {
            ans++;
            s = {sum - x};
        }
        s.insert(sum);
    }
    cout << ans << '\n';
    return 0;
}

本文地址:https://blog.csdn.net/weixin_44258590/article/details/108858952