题解：CF2131B Alternating Series

RealDream · 2025-08-17 16:50:33 · 题解

题意简化

给你一个正整数 N ，输出一个长度为 N 的“优质数组”，满足以下条件：

• 相邻的元素符号不同。
• 任意 x(x \geq 2) 个任意连续子序列的和为正数。
• 在所有满足条件的数组中，选择每个元素绝对值组成的序列字典序最小的那个（如在可以是 \{1, -2\} 的情况下不会是 \{1, -3\}，每个数组的数判定时取绝对值）。

思路

要使绝对值序列字典序最小，前几个元素应尽可能取小绝对值，并且数组中正数的和要大于负数和的绝对值。

观察样例，当 N 为 2 和 3 时，数组分别为 \{-1, 2\} 和 \{-1, 3, -1\}，由此可知每个“优质数组”都应该为 -1 开头。

所以，对于任意长度 N ，其“美好数组”都应该为 \{-1, ?, -1, ?, -1, ?, -1, \dots\}。

再来看第 2 个条件，在连续子序列和为正数和字典序最小这两个条件下，我们来依次尝试：

• 当数组中 ? 的值为 1 时：形成的数组为 \{-1, 1, -1, \dots\}，因为 -1 + 1 + (-1) = -1，显然不对。
• 当数组中 ? 的值为 2 时：形成的数组为 \{-1, 2, -1, \dots\}，因为 -1 + 2 + (-1) = 0，显然也不对。
• 当数组中 ? 的值为 3 时：形成的数组为 \{-1, 3, -1, \dots\}，因为 -1 + 1 + (-1) = 1，此时满足了第 2 个条件，所以 ? 的值可能为 3。

我们发现，当数组的结尾为正数时， \{-1, 3, -1, 3\} 并不优，因为 -1 + 3 = 2 ，而如果结尾是 2，-1 + 2 = 1，符合题意。

所以，我们重新整理一下思路：

• 输入一个数 N ，然后进入长度为 N 的循环（初始值 i = 0）。
• 当 i 为偶数时，输出 -1。
• 当 i 为奇数且不是最后一次循环时，输出 3。
• 当 i 为奇数且是最后一次循环是，输出 2。

Code

具体做法已经在前面说了，所以就不加注释了。

#include <bits/stdc++.h>

using namespace std;

namespace RealDream {
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    cout << -1;
                } else {
                    if (i == n - 1) cout << 2;
                    else cout << 3;
                }
                if (i < n - 1) {
                    cout << " ";
                }
            }
            cout << endl;
        }
        return 0;
    }
};

int main() {
    RealDream::main();
    return 0;
}