Educational Codeforces Round 173 A - D

2043A - Coin Transformation

按题意模拟。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        ll x;
        cin >> x;

        ll ans = 1;
        while (x > 3) {
            x /= 4;
            ans <<= 1;
        }
        cout << ans << endl;
    }

    return 0;
}

2043B - Digits

1 肯定有。

一个数是 5 的倍数等价于末位是 0 或 5，因此只能 $d=5$。

3 和 9 都是看数码和。对于 3，要求 $3\mid n! \cdot d$，如果 $d$ 是 3 或 9 已经成立，否则需要 $3\mid n!$，这等价于 $n \geqslant 3$；对于 9 也是类似分析，如果 $d$ 是 9 已经成立，如果 $d$ 是 3 或 6，需要 $3\mid n!$，这等价于 $n \geqslant 3$，否则需要 $9\mid n!$，这等价于 $n \geqslant 6$。

7 需要一点技巧，注意到 $1001=7\cdot 11\cdot 13$，而 $n \geqslant 3$ 时的数都是 1001 的倍数，所以 $n \geqslant 3$ 都可以，否则 $n=2$ 时只能 $d=7$。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, d;
        cin >> n >> d;

        vector<int> res{ 1 };
        if (n >= 3 || d % 3 == 0) {
            res.push_back(3);
        }
        if (d == 5) {
            res.push_back(5);
        }
        if (n >= 3 || d == 7) {
            res.push_back(7);
        }
        if (n >= 6 || (n >= 3 && d % 3 == 0) || d == 9) {
            res.push_back(9);
        }

        for (auto x : res) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

2043C - Sums on Segments

先考虑全为 1，-1。

1，-1 这些数表明，这些子串和是连续的，如果子串和最小值是 $l$，子串和最大值为 $r$，那么 $[l,r]$ 中所有数都是可以取到的。问题化为最大最小子串和问题。

如果有一个特殊数，这个数将整个数组分成两块，左右都是全为 1，-1，化为了上面的问题。再考虑包含这个特殊数的子串，子串和仍然是连续的，类似地分别找出左边和右边的最大最小子串就能确定范围 $[l,r]$。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

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

        int p = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] != 1 && a[i] != -1) {
                p = i;
            }
        }

        set<int> res;
        res.insert(0);
        int sum = 0;
        int maxr = 0, minr = 0;
        for (int i = p + 1; i < n; i++) {
            sum += a[i];
            maxr = max(maxr, sum);
            minr = min(minr, sum);
        }
        sum = 0;
        int maxl = 0, minl = 0;
        for (int i = p - 1; i >= 0; i--) {
            sum += a[i];
            maxl = max(maxl, sum);
            minl = min(minl, sum);
        }
        for (int i = minl + minr; i <= maxl + maxr; i++) {
            res.insert(a[p] + i);
        }

        auto solve = [&](int l, int r) {
            int maxsum = 0, maxx = -2e9;
            for (int i = l; i < r; i++) {
                maxsum += a[i];
                maxx = max(maxx, maxsum);
                if (maxsum < 0) {
                    maxsum = 0;
                }
            }
            int minsum = 0, minn = 2e9;
            for (int i = l; i < r; i++) {
                minsum += a[i];
                minn = min(minn, minsum);
                if (minsum > 0) {
                    minsum = 0;
                }
            }
            for (int i = minn; i <= maxx; i++) {
                res.insert(i);
            }
        };

        solve(0, p);
        solve(p + 1, n);

        cout << res.size() << endl;
        for (auto x : res) {
            cout << x << " ";
        }
        cout << endl;            
    }

    return 0;
}

2043D - Problem about GCD

暴力能过，暂时不懂为什么。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        ll l, r, d;
        cin >> l >> r >> d;

        r = r / d;
        l = (l + d - 1) / d;

        bool ok = false;
        for (ll len = r - l; len >= 0; len--) {
            for (ll j = l; j + len <= r; j++) {
                if (gcd(j, j + len) == 1) {
                    l = j, r = j + len;
                    ok = true;
                    break;
                }
            }
            if (ok) break;
        }     

        if (!ok) {
            cout << -1 << " " << -1 << endl;
        } else {
            cout << (l * d) << " " << (r * d) << endl;
        }
    }

    return 0;
}