CF_r981_div3----D. Kousuke's Assignment

Posted on Edited on

写在前面：该题转载至codeforces Codeforces Round 981 (Div. 3)😃

题目描述：

Codeforces Round 981 (Div. 3)----D. Kousuke’s Assignment

time limit per test2 seconds
memory limit per test256 megabytes

After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array a of n integers and asked him to calculate the number of non-overlapping segments of the array a, such that each segment is considered beautiful.

A segment [l,r] is considered beautiful if al+al+1+⋯+ar−1+ar=0.

For a fixed array a, your task is to compute the maximum number of non-overlapping beautiful segments.

在和 Sakurako 一起旅行后，Kousuke 非常害怕，因为他忘记了他的编程作业。在这次作业中，老师给了他一个包含 n 个整数的数组 a，并要求他计算数组 a 中不重叠线段的数量，使得每个线段都被认为是美丽的。

如果线段 [l,r] 满足 al+al+1+⋯+ar−1+ar=0 则该线段被认为是美丽的。

对于固定数组 a，您的任务是计算不重叠的美丽线段的最大数量。

输入：

The first line of input contains the number t (1≤t≤104) — the number of test cases. Each test case consists of 2 lines.

  • The first line contains one integer n (1≤n≤105) — the length of the array.

  • The second line contains n integers ai (−105≤ai≤105) — the elements of the array a.

It is guaranteed that the sum of n across all test cases does not exceed 3⋅105.

输入的第一行包含数字 t (1≤t≤104) — 测试用例的数量。每个测试用例由 2 行组成。

第一行包含一个整数 n (1≤n≤105) — 数组的长度。第二行包含 n个整数 a_i (−105≤a_i≤105) — 数组 a的元素。保证所有测试用例的 n 的总和不超过 3⋅105。

输出：

For each test case, output a single integer: the maximum number of non-overlapping beautiful segments.

对于每个测试用例，输出一个整数：不重叠的美丽线段的最大数量。

样例：

输入：

3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1

输出：

1
2
3

题目解析：

那必须是狠狠贪心，这是个前缀和的经典模板题，题目等价于求给定数组的不重叠的和为零的子数组数量，那可以从头遍历过去，如果遍历到的元素a与其之前的连续m个元素的和为0，那这m+1个数对应的就是一个和为零的子数组。

此时记录当前符合条件的子数组数量的变量sum自增，然后把a及其之前的元素无视掉，即不再参与后面的前缀和判断。

例如样例中的第一个给定数组arr[5]={2 1 -3 2 1},遍历未开始的时候sum=0,遍历到a_0 = 2,那么第一个数及其之前的元素的和为2。

这里说明一下，这里如果用map记录的话时间复杂度是优于用数组存储直接遍历的，或者每次遍历新元素都将其逐个往前累加,直到和为0或者遍历到了数组边界。(感觉不用map的话会被hacker用TL打掉)

继续往后遍历，第二个数及其之前的元素之和为3，到第三个元素及其之前元素之和为0，而sum=0的情况在遍历还未开始时出现过，所以sum(arr[0],arr[2])==0,满足条件，所以把前三个元素抛开，sum++后值为1。

再继续往后遍历，第四，五个元素分别与其之前的元素 (到上次满足条件的最后1个元素为止，此处为arr[2]后面的元素才参与计算) 求和的结果都未出现重复数字，所以返回最后结果sum=1。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int _;
    cin >> _;
    while (_--) {
        long long sum[200000]={0};
        int n;
        cin >> n;
        vector<long long> a(n+1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum[i]=sum[i-1]+a[i];
        }
        map<long long, long long> mp;
        int cnt = 0;
        int last = -1;
        mp[0] = 0; 
        for (int i = 1; i <= n; i++) {
            if (mp.count(sum[i]) && mp[sum[i]] > last) {
                cnt++;
                last = i - 1; 
            }
            mp[sum[i]] = i;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

Connect With Me

TTTTTThank You!