题解归档 - cf104118G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118G
• 本地来源：problems/cf104118G/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/G
• 原始标题：Gym 104118G - Gallivanting Merchant

思路

Gym 104118G - Gallivanting Merchant

Choosing the first appearance day only chooses a residue class modulo k.

An item [L,R] is buyable iff the chosen residue appears in that interval.

• If R-L+1 >= k, every residue works: add it to a constant base.
• Otherwise the interval covers one cyclic segment on residues (day-1) mod k.
• Split wrapped cyclic segments into at most two normal segments and sweep events.

The answer is base + max residue coverage.

Complexity: O(n log n).

Checks:

• official sample 1
• statement samples 2-3 reconstructed from PDF
• randomized brute force for small k

代码

来源：problems/cf104118G/solution.cpp

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

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

    int n;
    ll k;
    cin >> n >> k;

    int all = 0;
    vector<pair<ll, int>> ev;

    auto add_seg = [&](ll l, ll r) {
        ev.push_back({l, +1});
        if (r + 1 < k) ev.push_back({r + 1, -1});
    };

    for (int i = 0; i < n; ++i) {
        ll L, R;
        cin >> L >> R;
        if (R - L + 1 >= k) {
            ++all;
            continue;
        }
        ll l = (L - 1) % k;
        ll r = (R - 1) % k;
        if (l <= r) {
            add_seg(l, r);
        } else {
            add_seg(l, k - 1);
            add_seg(0, r);
        }
    }

    sort(ev.begin(), ev.end());
    int cur = 0, best = 0;
    for (int i = 0; i < (int)ev.size();) {
        ll x = ev[i].first;
        while (i < (int)ev.size() && ev[i].first == x) {
            cur += ev[i].second;
            ++i;
        }
        best = max(best, cur);
    }

    cout << all + best << '\n';
    return 0;
}