CF1807G 题解

深圳信奥算法部-吴传民

2026-01-30 15:30:50

发布于：广东

9阅读

0回复

0点赞

CodeForces 1807G Subsequence Addition 题解

原题链接：https://codeforces.com/problemset/problem/1807/G2

题目大意

一开始数组只有一个元素 [1]。
每次操作：从当前数组里选一个非空子序列，把它们的和作为一个新数加入数组。
给你最终数组 c（顺序无关，本质是多重集合），问能不能通过若干次操作得到它。

思考方向

关键观察：
如果我们把最终数组 c 从小到大排序，并设 sum 表示“我们已经能凑出来的总和上限”（更准确：当前数组中一些元素之和的最大可达值），那么：

一开始只有 1，所以 sum = 1（表示至少能选到子序列和为 1）。
当我们要“生成”一个新元素 x 时，它必须是某个子序列的和。
而子序列和的最大值不可能超过当前所有元素和，也就是 sum。
因此：下一个要加入的数 x 必须满足 x <= sum，否则无论怎么选子序列都凑不出 x。

如果 x <= sum，我们就能用某个子序列凑出 x 并加入数组；加入后总和上限变为 sum += x。

另外：因为初始只有一个 1，所以最终数组里至少得有一个 1，否则第一步就无法开始。

解题思路

对每个测试用例：

读入 c，排序。
如果最小值不是 1，直接输出 NO。
令 sum = 1（表示目前能凑出的子序列和不超过 1）。
从第二个元素开始依次检查：
- 若当前 x > sum，说明凑不出 x，输出 NO。
- 否则 sum += x，继续。
全部通过则输出 YES。

为什么这样一定对？

必要性：任何新加入的数都必须是某个子序列和，肯定不超过当前总和 sum。
充分性：当 x <= sum 时，我们总能从已有元素中选出一些使和为 x（这是经典结论：在按规则构建、且始终保持“可表示区间连续”时，可表示范围从 [1..sum] 扩展到 [1..sum+x]）。

复杂度：排序 $O(n\log n)$ ，总 $n\le 2\cdot 10^5$ 。

最终代码

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> c(n);
        for (int i = 0; i < n; i++) cin >> c[i];
        sort(c.begin(), c.end());
        if (c[0] != 1) {
            cout << "NO\n";
            continue;
        }
        long long sum = 1; // 当前可凑出的最大子序列和上限（至少覆盖 [1..sum]）
        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (c[i] > sum) {
                ok = false;
                break;
            }
            sum += c[i];
        }
        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}