题解 | #子段和#

1. 问题分析

问题的核心是在给定序列的重排中，消除两类“零和”子区间：

• 长度为 1 的子区间：即序列中的单个元素 。若 ，则该区间和必为 0。
• 长度为 2 的子区间：即相邻的两个元素 。若 ，即两者互为相反数，则该区间和为 0。

由于 的规模达到 ，我们需要一个 或 的算法。

2. 构造性逻辑与鸽巢原理

我们并非真的去寻找一种排列，而是通过分析元素间的互斥关系来判断是否存在合法排列。

我们将问题抽象为：

1. 硬性排除条件：如果序列中包含 ，根据长度为 1 的约束，无论如何排列都无法满足条件，直接输出 NO。
2. 相邻冲突逻辑：如果不存在 ，唯一的威胁来自于相邻的相反数对 。
   • 若序列中只有一种绝对值的元素（如 ），且同时存在正数和负数，那么在任何排列中，正数和负数必然会在某个位置相邻，产生零和。
   • 若序列中存在多种绝对值的元素，我们可以通过交叉放置不同绝对值的元素来“隔离”相反数对。

3. 核心命题证明

命题：当序列中不含 时，无法满足条件的充要条件是：序列中所有元素的绝对值相同，且同时存在正数和负数。

• 必要性：如果序列中所有元素的绝对值都为 ，且既有 又有 ，因为没有其他类型的数值作为“缓冲区”，无论如何排列，序列中总会出现 或 的情况。
• 充分性：
  • 如果所有元素都相同（如全是 ），相邻和永远不为 。
  • 如果存在至少两种不同的绝对值（如 和 ），我们可以采取分块策略：
    • 将所有相同的数值聚集在一起形成块。例如，所有 放在一起形成块 ，所有 放在一起形成块 。
    • 只要不同数值的类别数足够，我们总能找到一个排列顺序，使得相邻的两个块不互为相反数。例如对于数值集 ，排列 产生的边界 和 均不为零。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unordered_map<ll, int> dict;
    int n;
    cin >> n;

    bool valid = true;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (a == 0)
            valid = false;
        dict[a]++;
    }

    if (!valid) {
        cout << "NO\n";
        return 0;
    }

    int m = dict.size();
    if (m == 2) {
        int sum = 0;
        for (const auto& [k, v] : dict) {
            sum += k;
        }
        if (sum == 0) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
}