数组缺失元素补充与目标和构造

问题描述：给定一个包含 $m$ 个互不相同正整数的集合，以及一个目标值 $s$。你需要向该集合中添加若干个不存在于原集合中的正整数，使得所有新添加元素的总和恰好等于 $s$。请判断是否存在满足条件的添加方案。

算法思路：首先对原数组进行升序排序。为了使添加的元素之和最小，我们应优先填补 $1$ 到数组最大值之间缺失的正整数。计算出这部分缺失元素的总和，如果该总和已经大于 $s$，则显然无解。如果小于或等于 $s$，我们将 $s$ 减去该缺失和，然后从数组最大值加 $1$ 开始，依次贪心地累加后续连续整数，直到剩余目标值降至 $0$ 或以下。若最终剩余值恰好为 $0$，则输出肯定结果，否则无解。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void processTestCase() {
    int n;
    long long target_sum;
    if (!(cin >> n >> target_sum)) return;

    vector<long long> elements(n);
    for (int i = 0; i < n; ++i) {
        cin >> elements[i];
    }

    sort(elements.begin(), elements.end());

    long long missing_sum = 0;
    long long expected_val = 1;
    
    // 计算区间内缺失元素的和
    for (int i = 0; i < n; ++i) {
        while (expected_val < elements[i]) {
            missing_sum += expected_val;
            expected_val++;
        }
        expected_val = elements[i] + 1;
    }

    if (missing_sum > target_sum) {
        cout << "NO\n";
        return;
    }

    target_sum -= missing_sum;
    long long next_val = elements.back() + 1;
    
    // 贪心补充后续连续整数
    while (target_sum > 0) {
        target_sum -= next_val;
        next_val++;
    }

    cout << (target_sum == 0 ? "YES\n" : "NO\n");
}

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

    int t;
    if (cin >> t) {
        while (t--) {
            processTestCase();
        }
    }
    return 0;
}

区间数位和的高效查询

问题描述：给定多次查询，每次查询提供一个正整数 $n$，要求计算从 $1$ 到 $n$ 所有整数的数位之和的总和。

算法思路：由于查询次数较多且数据范围固定，直接对每次查询进行遍历计算会导致超时。因此采用预处理结合前缀和的策略。利用动态规划的思想，一个数 $i$ 的数位和等于 $i / 10$ 的数位和加上 $i \pmod{10}$。通过线性递推预处理出所有可能数值的数位和，并同步构建前缀和数组。在应对具体查询时，即可实现 $\mathcal{O}(1)$ 时间复杂度的常数级响应。

#include <iostream>
#include <vector>

using namespace std;

const int MAX_LIMIT = 200005;
vector<long long> prefix_digit_sums(MAX_LIMIT, 0);

void precompute() {
    vector<int> single_digit_sum(MAX_LIMIT, 0);
    for (int i = 1; i < MAX_LIMIT; ++i) {
        single_digit_sum[i] = single_digit_sum[i / 10] + (i % 10);
        prefix_digit_sums[i] = prefix_digit_sums[i - 1] + single_digit_sum[i];
    }
}

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

    precompute();

    int test_cases;
    if (cin >> test_cases) {
        while (test_cases--) {
            int query_n;
            cin >> query_n;
            cout << prefix_digit_sums[query_n] << "\n";
        }
    }
    return 0;
}