第一次 ak cf 的正式比赛，不正式的是寒假里 div4 的 Testing Round，好啦好啦不要问我为什么没有 ak div4 了，差一题差一题 =。=

不知不觉已经咕了一个月了2333。

比赛链接：https://codeforces.com/contest/1462

A. Favorite Sequence

题解

模拟即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        deque<int> d;

        for (int i = 0; i < n; i++) {

            int x;

            cin >> x;

            d.push_back(x);

        }

        while (not d.empty()) {

            cout << d.front() << ' ';

            d.pop_front();

            if (not d.empty()) {

                cout << d.back() << ' ';

                d.pop_back();

            }

        }

        cout << "\n";

    }

    return 0;

}

B. Last Year's Substring

题解

枚举余下首尾子串的长度即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        string s;

        cin >> s;

        bool ok = false;

        for (int i = 0; i <= 4; i++) {

            string t = s.substr(0, i) + s.substr(n - 4 + i);

            ok or_eq t == "2020";

        }

        cout << (ok ? "YES" : "NO") << "\n";

    }

    return 0;

}

C. Unique Number

题解

最小的数一定最短，所以从 9~1 依次减即可，也因此不会存在 \(x\) 减不完的情况。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int x;

        cin >> x;

        if (x > 45) {

            cout << -1 << "\n";

            continue;

        }

        string digit;

        for (int i = 9; i >= 1; i--) {

            if (x >= i) {

                x -= i;

                digit += '0' + i;

            }

        }

        cout << string(digit.rbegin(), digit.rend()) << "\n";

    }

    return 0;

}

拓展

最大的数一定最长，所以从 1~9 依次减即可，也因此需要判断 \(x\) 减不完的情况。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int x;

        cin >> x;

        if (x > 45) {

            cout << -1 << "\n";

            continue;

        }

        string s;

        for (int i = 1; i <= 9; i++) {

            if (x < i and x != 0) {

                x += i - 1;

                s.pop_back();

            }

            if (x >= i) {

                x -= i;

                s += '0' + i;

            }

        }

        cout << string(s.rbegin(), s.rend()) << "\n";

    }

    return 0;

}

D. Add to Neighbour and Remove

题解

枚举最后剩下几个数即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        vector<int> a(n);

        int sum = 0;

        for (int i = 0; i < n; i++) {

            cin >> a[i];

            sum += a[i];

        }

        int ans = INT_MAX;

        for (int i = 1; i <= n; i++) {

            if (sum % i == 0) {

                bool ok = true;

                int cur = 0;

                for (int j = 0; j < n; j++) {

                    cur += a[j];

                    if (cur > sum / i) {

                        ok = false;

                    } else if (cur == sum / i) {

                        cur = 0;

                    }

                }

                if (ok) {

                    ans = min(ans, n - i);

                }

            }

        }

        cout << ans << "\n";

    }

    return 0;

}

E2. Close Tuples (hard version)

题解

将值排序，然后枚举所有值，找到以当前值为最小值且符合题意的元组的最大长度，答案即 \(\sum \limits _{i = 1}^{n} C_{len - 1}^{m - 1}\) 。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e6 + 100;

constexpr int MOD = 1e9 + 7;

int fac[N], inv[N];

int binpow(int a, int b) {

    int res = 1;

    while (b) {

        if (b & 1) res = 1LL * res * a % MOD;

        a = 1LL * a * a % MOD;

        b >>= 1;

    }

    return res;

}

int C(int n, int m){

    if(m < 0 or m > n) return 0;

    return 1LL * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

void Init(){

    fac[0] = 1;

    for (int i = 1; i < N; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;

    inv[N - 1] = binpow(fac[N - 1], MOD - 2);

    for (int i = N - 2; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % MOD;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    Init();

    int t;

    cin >> t;

    while (t--) {

        int n, m, k;

        cin >> n >> m >> k;

        vector<int> a(n);

        for (int i = 0; i < n; i++) {

            cin >> a[i];

        }

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

        int64_t ans = 0;

        int l = 0, r = 0;

        while (l < n) {

            while (r < n and a[r] - a[l] <= k) {

                ++r;

            }

            if (a[r - 1] - a[l] <= k) {

                ans = (ans + C(r - l - 1, m - 1)) % MOD;

            }

            ++l;

        }

        cout << ans << "\n";

    }

    return 0;

}

F. The Treasure of The Segments

题解

枚举所有区间即可，满足以下两种情况之一的区间需要删掉：

右端点小于所枚举区间的左端点
左端点大于所枚举区间的右端点

将区间左右端点分别排序，每次二分查找需要删掉区间的个数即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        vector<int> L(n), R(n);

        vector<pair<int, int>> seg(n);

        for (int i = 0; i < n; i++) {

            cin >> L[i] >> R[i];

            seg[i] = {L[i], R[i]};

        }

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

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

        int ans = INT_MAX;

        for (auto [x, y] : seg) {

            int res = 0;

            int l = upper_bound(L.begin(), L.end(), y) - L.begin();

            res += n - l;

            int r = lower_bound(R.begin(), R.end(), x) - R.begin();

            res += r;

            ans = min(ans, res);

        }

        cout << ans << "\n";

    }

    return 0;

}

巴特西

Codeforces Round #690 (Div. 3)