题目解析

把原序列按顺序种在一条线上。 设当前前缀和为 pre，若存在两下标 l<r 使

则等价于

也就是当前前缀和减 M 与之前出现过的某个前缀和相同。 为了让整条路上 不存在 这样的配对，我们可以把整条路切成若干段，使得每段内部都不出现上述现象——在两段间插入一棵新树即可。显然切段次数越少，新增树就越少。

贪心切段

• 维护当前段内所有前缀和的哈希集合 S（初始含 0）。

• 顺序扫描原数组

  1. pre += Ai

  2. 若 pre - M 已在 S，说明本段出现了和为 M 的区间——必须立刻切段：

     • ans++（新增一棵树）
     • 清空 S，只留下 0
     • 本元素必须属于下一段，令 pre = Ai，把 pre 放入 S

  3. 否则把 pre 放入 S，继续扫描

• 扫描结束，ans 即最小新树棵数。

为什么只需插 1 棵？ 新插的树可以取超级大的值或超级小的值，如$10^{18}$,$-10^{18}$。 它把前后两段划开，任何跨越插入位置的区间都包含这棵树，其和一定 ≠ M。

正确性

每段内部不出现 “前缀差 = M”，跨段区间必含插入的树，也不满足和 = M，因此整体合法。若某次检测到冲突却不切段，必然存在非法区间，因此算法得到的插入数最小。

复杂度分析

• 时间：每个元素至多被处理一次，集合操作均摊 O(1)→O(N)
• 空间：哈希集合最大只含当前段前缀和→O(N)（最坏全在一段）

参考代码

Python

import sys

n, M = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

seen = {0}        # 当前段前缀和集合
pre = 0           # 当前段前缀和
ans = 0           # 需插入的树数

for v in a:
    pre += v
    if pre - M in seen:        # 产生非法区间，切段
        ans += 1
        seen.clear()
        seen.add(0)
        pre = v                # 重新计算前缀和
    seen.add(pre)

print(ans)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        long pre = 0;                   // 当前段前缀和
        int ans = 0;                    // 新树棵数
        HashSet<Long> set = new HashSet<>();
        set.add(0L);

        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            pre += x;
            if (set.contains(pre - M)) { // 冲突，切段
                ans++;
                set.clear();
                set.add(0L);
                pre = x;
            }
            set.add(pre);
        }
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; int M;
    if (!(cin >> n >> M)) return 0;

    unordered_set<int64> S;  // 当前段前缀和集合
    S.insert(0);
    int64 pre = 0;
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        int64 x; cin >> x;
        pre += x;
        if (S.count(pre - M)) {        // 出现非法区间
            ++ans;
            S.clear();
            S.insert(0);
            pre = x;                   // 新段前缀和
        }
        S.insert(pre);
    }
    cout << ans << '\n';
    return 0;
}

题目内容

新的一个季度又要到了，多多君准备在多多路上再种一些树木。

多多路上已经有了$N$棵树木(编号$1$~$N$)，对于每一棵树，多多君都给打了一个美观值评分，其中第i棵树的美观值记为$Ai$。

而对于多多路上的每个区间，其整体的美观值可以认为是该区间中每棵树的美观值之和.

多多君不太喜欢数字$M$，所以当某个区间的美观值为$M$时，就需要在该区间中再种若干树木，使得没有任何一个区间的美观值为$M$。

多多君想知道，假设新种的树木的美观值可以任意挑选的情况下，最少需要再种多少棵树，可以满足上述要求。

输入描述

共两行，第一行，两个整数N和M，分别表示当前已有树木的数量和多多君不喜欢的数字$M$。 $(1<=N<=100,000)$

$(-1,000,000<=M<=1,000,000)$

第二行，$N$个整数 $Ai$，第$i$个整数表示第$i$棵树木的美观值。

($-1,000,000 <=Ai <=1,000,000$ 且保证$Ai$不等于$M$)

输出描述

共一行，一个整数，表示最少需要再种多少树，可以满足没有任意一个区间的美观值为M的要求。

补充说明

其中$30$%的数据，有:$N<=1,000$

样例1

输入

4 -1
3 -3 2 3

输出

1

说明

只有一个区间$[2,3]$的美观值为:$-3+2=-1$不符合要求。

可以选择在$[2,3]$之间再种一颗美观值为$1$的树，使得整体为:$3\ -3\ 1\ 2\ 3$，如

此没有任何一个区间的美观值为$-1$。

样例2

输入

5 100
1 2 3 4 5

输出

0

说明

没有一个区间的和谐之和为$100$。