题解 | #元素方碑#

1. 问题分析

该问题的核心在于理解操作的局限性。虽然题目描述了方碑之间的能量流动，但这种流动并非在任意两个方碑之间自由进行，而是受到严格的几何结构限制。

核心约束：

• 操作中心性：对下标为 的方碑进行操作，受到影响的是 和 。
• 不变性：方碑 在该操作下，自身的能量 保持不变。
• 耦合关系：下标 的奇偶性决定了它能操作的对象。
  • 当 是偶数时， 和 必然是奇数。这意味着对偶数方碑的操作只能在奇数下标序列中转移能量。
  • 当 是奇数时， 和 必然是偶数。这意味着对奇数方碑的操作只能在偶数下标序列中转移能量。

结论：整排方碑被划分为两个互不干扰的独立系统：奇数下标集合和偶数下标集合。能量只能在各自的集合内部流动，无法跨越奇偶性进行交换。

2. 奇偶不变性原理

基于上述分析，该问题本质上是一个状态可达性问题。我们可以采用“守恒量”策略进行判断。

2.1 奇偶系统分解

定义两个子集：

• （下标为奇数的能量集合）
• （下标为偶数的能量集合）

无论进行多少次操作，集合 的能量总和 以及集合 的能量总和 是始终不变的（因为每次操作只是在集合内部移动 1 单位能量）。

2.2 目标状态的可行性

由于最终目标是令所有 个方碑的能量全部相等，记最终相等的能量值为 。则必须满足：

1. 全局总和条件：总能量 必须能够被 整除。
2. 局部期望条件：
   • 奇数下标集合的能量总和必须等于 。
   • 偶数下标集合的能量总和必须等于 。

其中 和 分别是奇数和偶数下标方碑的数量。

2.3 连通性与非负约束

• 连通性：在 的范围内，任何两个同余项（如同为奇数下标）总能通过若干步中间方碑进行能量传递。例如，能量可以从 传到 ，再从 传到 。
• 非负约束：由于目标值 始终 且起始能量非负，且同余集合内是全连通的，我们总能找到一条路径将富余的能量转移到亏损的方碑上，而不会导致任何方碑在最终状态下变为负数。

3. 代码实现

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

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        ll odd = 0;
        int oddCnt = 0;
        ll even = 0;
        int evenCnt = 0;

        for (int i = 0; i < n; i++) {
            ll a;
            cin >> a;
            if (i % 2 == 0) {
                even += a;
                evenCnt++;
            } else {
                odd += a;
                oddCnt++;
            }
        }
        ll S = odd + even;
        if (S % n != 0) {
            cout << "NO\n";
            continue;
        }
        ll X = S / n;
        if (even != evenCnt * X) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
}

4. 复杂度分析

时间复杂度：

空间复杂度： 或