Codeforces Round 674 (Div. 3) 解题报告

CF1426D Non-zero Segments

Codeforces Round 674 (Div. 3) 第四题。

题意翻译

给定一个序列,求最少插入多少数,才能使此序列任意子段和均不为 \(0\)。

插入的数字可以是你能想到的所有整数。

题解

我们处理每一段区间的前缀和,那么对于任意两个 \( i , j ( 1 \leq j \leq i \leq n ) \),让 \( f _ i – f _ j \) 就为 \( a _ j \) 至 \( a _ i \) 的区间和。

那么如果存在 \( f _ i – f _ j = 0 ( 1 \leq j \leq i \leq n ) \),即存在 \( f _ i = f _ j \) 的情况,就代表区间和为 \( 0 \),如果这样那我们可以在这段区间中间插入一个 \( + \infty \),使得这段区间不为 \(0\) 的同时不会出现一段新的区间和为 \(0\),再把这个位置记录下来,之后的查询都必须在这个之后。

unordered_set 查找前缀和即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{ //有符号型快读
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        f |= (ch == '-'), ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return f ? -res : res;
}

int n;
unordered_set<ll> S;

int main(void)
{
    n = read();
    S.insert(0); //从头开始的前缀和为 0
    reg int cnt = 0;
    ll sum = 0;
    for (reg int i = 1; i <= n; ++i)
    {
        static int a; //元素
        a = read();   //读入
        if (S.find(sum + a) != S.end())
        {                  //如果恰好出现相同
            ++cnt;         //插入一个正无穷
            S.clear();     //清空之前的数据
            S.insert(sum); //插入当前的和
        }
        sum += a;      //维护前缀和
        S.insert(sum); //插入
    }
    printf("%d\n", cnt); //输出答案
    return 0;
}
Pages: 1 2 3 4 5 6 7 8