神秘的D题题解
  • 板块灌水区
  • 楼主4041nofoundGeoge
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/14 22:05
  • 上次更新2024/12/15 09:28:30
查看原帖
神秘的D题题解
1285950
4041nofoundGeoge楼主2024/12/14 22:05

今天的 ABC_D 题的题解什么意思?

#include <iostream>
#include <numeric>
#include <set>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    unsigned long S;
    cin >> N >> S;

    vector<unsigned long> A(N);
    for (auto& a : A)
        cin >> a;

    // Boil down to 0 <= S < X
    const auto sum{reduce(begin(A), end(A))};
    S %= sum;

    // Repeat A twice
    A.reserve(2 * N);
    for (unsigned i{}; i < N; ++i)
        A.emplace_back(A[i]);

    // Find the cumulative sum
    set<unsigned long> prefix_sum{};
    prefix_sum.emplace();
    for (unsigned long p{}; const auto a : A) {
        p += a;
        prefix_sum.insert(p);
    }

    // For each element p of the cumulative sums, check if (p + S) is contianed
    for (const auto p : prefix_sum)
        if (prefix_sum.contains(p + S)) {
            cout << "Yes" << endl;
            return 0;
        }

    cout << "No" << endl;
    return 0;
}

2024/12/14 22:05
加载中...