Description

给定一个长度为 \(n\) 的序列 \(a\) ，请判断该序列是否有：

1. \(a_1 < a_2 < a_3 < \dots < a_n\)
2. 对于任意一个数 \(i\)（ \(1\leqslant i \leqslant n\) ） ，满足 \(a_1 \sim a_{i-1}\) 中任意若干个数相加之和 \(\neq a_i\)

如果满足上述条件，那么我们称该序列为 A-sequence 。

条件保证 \(1 \leqslant n \leqslant 30,\ 1 \leqslant a_i \leqslant 10^3\) 。

单个样例中可能会存在多组测试数据。

Solution

判断升序

判断序列是否为升序排列很简单。你可以手写一个循环或者使用 STL 中的 is_sorted 函数进行判断，我选择了后者 （能用 STL 干啥手写呢，STL 大法好！！1）

示例：

#include <iostream>
#include <algorithm>
using namespace std;

int a[] = {1, 2, 3, 4, 5, 6}, b[] = {6, 5, 4, 3, 2, 1};

int main() {
    cout << is_sorted(a, a + 6) << " " << is_sorted(b, b + 6) << endl;
    // 输出：1 0
    // a数组是升序的，b数组是降序的，is_sorted默认判断升序
    return 0;
}

判断两数之和是否等于当前数

这个其实也很简单，DFS 的板子。 （但是我还是调了一个小时

我们设定几个边界条件：选择的数量、递归深度、总和以及结束下标。

选择的数量和递归深度是用于防止无限递归的，总和初始值是要寻找求和方式的那个数（ \(a_i\) ），每次找到一个数就减去它，结束下标是搜索的时候数组的结尾下标。

这样，只要选择的数量和递归深度都不超过当前结束下标的时候，我们就可以进行 DFS 。每次 DFS ，若当前总和等于 \(0\) ，即选择完成且没有剩余，我们返回真；否则，我们有两种选择：选择当前数和不选择当前数。我们将对两种可能性分别递归，直到达到边界条件或找到总和排列方式。

Code

详见注释。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> seq;  // 每次输入的序列
int n, cnt = 0;  // n是序列长度，cnt用于记录测试点数量

bool dfs(int step, int selected, int sum, int end) {  // 搜索求和，参数分别是：递归深度、选择数量、总和、结束下标
    if (sum == 0) return 1;  // 如果一个排列方式的和恰好等于sum的初始值，返回真
    if (selected > end || sum < 0 || step > end) return 0;  // 判断边界条件
    if (dfs(step + 1, selected + 1, sum - seq[step], end)) return 1;  // 选择当前数
    if (dfs(step + 1, selected, sum, end)) return 1;  // 不选择当前数
    return 0;
}

int main() {
    while (cin >> n) {  // 没有给定测试点数量，输入以EOF结尾
        bool sorted = 0, sum = 1;  // 分别代表是否升序排列、对于任意一个数是否满足它之前的数的和不等于它
        vector <int> ().swap(seq);  // 清空vector
        cout << "Case #" << ++cnt << ": ";
        for (int i = 0; i < n; i++) {
            int t;
            cin >> t;
            cout << t;
            if (i != n - 1) cout << " ";
            if (dfs(0, 0, t, i - 1)) sum = 0;  // 判断当前数是否满足条件二
            seq.push_back(t);
        }
        cout << endl;
        if (is_sorted(seq.begin(), seq.end())) sorted = 1;  // 判断是否升序排列
        if (sum && sorted) cout << "This is an A-sequence." << endl;  // 两个条件都满足就是 A-sequence
        else cout << "This is not an A-sequence." << endl;
    }
    return 0;
}