Educational codeforceRound 173 题解

A

B

C

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

using i64 = long long;
constexpr i64 inf = 1e9 + 7;
template<typename T>
tuple<T, T, T> MaxArray(const vector<T>& nums) {
    if (nums.size() == 1) return {0, -1, 0};

    T cur = nums[1], maxp = nums[1];      
    int start = 1;              
    int le = 1;        
    int ri = 1;            

    for (int i = 2; i < nums.size(); i++) {
        if (cur + nums[i] < nums[i]) {
            cur = nums[i];
            start = i;
        } else {
            cur += nums[i];
        }

        if (cur > maxp) {
            maxp = cur;
            le = start; 
            ri = i;       
        }
    }

    return {le, ri, maxp}; 
}
void solve() {
    int n;
    cin >> n;

    vector<i64> a(n + 1);
    int pos = -1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] != 1 && a[i] != -1) {
            pos = i;
        }
    }   

    if (pos == -1) {
        auto [x, y, z] = MaxArray<i64> (a);
        i64 tp = max(0LL, z);

        for (int i = 1; i <= n; i++) {
            a[i] = -a[i];
        }

        auto [h, j, p] = MaxArray<i64> (a);

        i64 kp = max(0LL, p);
        kp = -kp;

        cout << tp - kp + 1 << '\n';
        for (int i = kp; i <= tp; i++) {
            cout << i << ' ';
        }
        cout << '\n';
        return;
    }

    vector<i64> l(1), r(1);
    for (int i = 1; i < pos; i++) {
        l.push_back(a[i]);
    }

    for (int i = pos + 1; i <= n; i++) {
        r.push_back(a[i]);
    }


    auto [x, y, z] = MaxArray(l);
    z = max(0LL, z);
    i64 lmax = z;

    for (int i = 1; i <= l.size() - 1; i++) {
        l[i] = -l[i];
    }

    auto [p, u, b] = MaxArray(l);
    b = max(0LL, b);
    i64 lmin = -b;

    auto [gg, ee, f] = MaxArray(r);
    f = max(0LL, f);
    i64 rmax = f;
    for (int i = 1; i <= r.size() - 1; i++) {
        r[i] = -r[i];
    }

    auto [ioi, powp, w] = MaxArray(r);
    w = max(w, 0LL);
    i64 rmin = -w;

    set<i64> is;
    for (i64 i = min(rmin, lmin); i <= 0; i++) {
        is.insert(i);
    }

    for (int i = 0; i <= max(lmax, rmax); i++) {
        is.insert(i);
    }

    i64 sum = 0;
    i64 mp = 0;
    i64 mi = 0;
    for (int i = pos + 1; i <= n; i++) {
        sum += a[i];
        mp = max(0LL, max(mp, sum));
        mi = min(0LL, min(mi, sum));
    }

    i64 mmp = 0, mmi = 0;
    sum = 0;
    for (i64 i = pos - 1; i >= 1; i--) {
        sum += a[i];
        mmp = max(0LL, max(mmp, sum));
        mmi = min(0LL, min(mmi, sum));
    }

    i64 tminp = mmi + mi;
    i64 tmaxp = mmp + mp;
    //cerr << tminp << ' ' << tmaxp << '\n';

    for (i64 i = a[pos] + tminp; i <= a[pos] + tmaxp; i++) {
        is.insert(i);
    }

    cout << is.size() << '\n';
    for (auto x : is) {
        cout << x << ' ';
    }
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

D

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

using i64 = long long;
constexpr i64 inf = 1e18 + 9;
void solve() {
    i64 l, r, g;
    cin >> l >> r >> g;
    
    if (g > r) {
        cout << -1 << ' ' << -1 << '\n';
        return;
    }

    i64 de = (l / g) + ((l % g) ? 1 : 0);
    i64 kp = (r / g);
   // cerr << "!:" << de << ' ' << kp << '\n';
    if (g == 1) {
        if (l == 1) {
            cout << 1 << ' ' << 1LL * r << '\n';
            return;
        }
        if (l == r) {
            cout << -1 << ' ' << -1 << '\n';
            return;
        }

        i64 maxp = 0;
        i64 ll = l, rr = r;

        for (i64 i = l; i <= r; i++) {
            if (r - i <= maxp) break;
            for (i64 j = r; j >= l; j--) {
                if (j - i <= maxp) break;
                if (gcd(i, j) == 1) {
                    if (j - i > maxp) {
                        maxp = j - i, ll = i, rr = j;
                        break;
                    }
                }
            }
        }

        cout << 1LL * ll << ' ' << 1LL * rr << '\n';
        return;
    }

    if (de > kp) {
        cout << -1 << ' ' << -1 << '\n';
    } else if (de == kp) {
        if (de == 1) {
            cout << g << ' ' << g << '\n';
        } else {
            cout << -1 << ' ' << -1 << '\n';
        }
    } else {
        if (de == 1) {
            cout << g << ' ' << 1LL * g * kp << '\n';
            return;
        }

        i64 ll = de, rr = kp;
        i64 maxp = 0;
        for (i64 li = de; li <= kp; li++) {
            if (kp - li <= maxp) break;
            for (i64 j = kp; j >= li; j--) {
                if (j - li <= maxp) break;
                if (gcd(j, li) == 1) {
                    if (j - li > maxp) {
                        maxp = j - li;
                        rr = j, ll = li;
                        break;
                    }
                }
            }
        }
        cout << ll * 1LL * g << ' ' << rr * 1LL * g << '\n';
        
    }

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

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}