链接：https://atcoder.jp/contests/abc444

A – Repdigit

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    int x;
    cin >> x;

    if (x % 10 == x / 10 % 10 && x % 10 == x / 100)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B – Digit Sum

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll cnt = 0;
        ll x = i;
        while (x)
        {
            cnt += x % 10;
            x /= 10;
        }

        if (cnt == k)
            ++ans;
    }

    cout << ans << endl;
}

C – AtCoder Riko

算法：

贪心，分类讨论。

思路：

容易想到 \(L\) 只有 \(max\) 和 \(max + min\) 两种可能（\(max\) 为数组最大元素，\(min\) 为数组最小元素）。

\(max\) 证明：想要证明 \(max\) 为 \(L\) 可能的值，只需证明比 \(max\) 小的元素都不可能成为 \(L\)，如果选择一个 \(x\)（小于 \(max\)），其作为 \(L\)，由于 \(max > x\)，其不能构成零食，因此 \(x\) 不能当作 \(L\)。

\(max + min\) 证明：想要证明 \(max + min\) 为 \(L\) 可能的值，只需证明比 \(min\) 大的元素都不可能与 \(max\) 的和构成 \(L\)，如果选择一个 \(x\)（大于 \(min\)），其和 \(max\) 的和作为 \(L\)，由于 \(min < x\) 且 \(min + max < x + max\)，还不存在比 \(max\) 大的元素与 \(min\) 配对，因此 \(x + max\) 不能构成零食，因此 \(x + max\) 不能当作 \(L\)。

分类讨论：

• 当 \(n\) 为奇数时，天然的多出一个元素，需要这个元素单独一对，这个单独的一对很容易想到是 \(max\)，而 \(max + min\) 必然不能成为 \(L\)（证明略）；
• 当 \(n\) 为偶数时，\(maxv 和 [latex]max + min\) 都有可能。

关键代码：

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

    ranges::sort(a);

    ll maxx = a[n - 1];
    ll minn = a[0];

    if (maxx == minn)
    {
        if (n & 1)
            cout << maxx << endl;
        else
            cout << maxx << ' ' << maxx * 2 << endl;

        return;
    }

    if (n & 1)
        cout << maxx << endl;
    else
    {
        vector<int> ans;
        bool ok = 1;
        int i = 0, j = n - 1;
        for (; i <= j;)
        {
            if (i == j && a[i] + a[j] == maxx)
            {
                ok = 0;
                break;
            }

            if (a[j] == maxx)
            {
                --j;
                continue;
            }

            if (a[i] + a[j] == maxx)
                ++i, --j;
            else
            {
                ok = 0;
                break;
            }
        }

        if (ok)
            ans.push_back(maxx);

        ok = 1;
        for (int i = 0, j = n - 1; i < j;)
        {
            if (a[i] + a[j] == maxx + minn)
                ++i, --j;
            else
            {
                ok = 0;
                break;
            }
        }

        if (ok)
            ans.push_back(maxx + minn);

        for (auto x : ans)
            cout << x << ' ';
        cout << endl;
    }
}

D – Many Repunit Sum 

算法：

前缀和，差分，高精度。

思路：

板子题，不过多赘述。

关键代码：

void miyan()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    vector<ll> b(N, 0);
    for (int i = 0; i < n; ++i)
    {
        b[1] += 1;
        b[a[i] + 1] -= 1;
    }

    for (int i = 1; i < N - 3; ++i)
        b[i] += b[i - 1];

    string ans;
    for (int i = 1; i < N - 3; ++i)
    {
        ll t = b[i] % 10;
        ll w = (b[i] - t) / 10;

        b[i] = t;
        b[i + 1] += w;

        ans += b[i] + '0';
    }

    while (ans.back() == '0')
        ans.pop_back();

    ranges::reverse(ans);

    cout << ans << endl;
}

E – Sparse Range

算法：

贪心，双指针，\(STL\)。

思路：

想要计算满足条件的整数对 \((L, R)\) 的数量，只需计算对于每个 \(L\) 满足条件的 \(R\) 的数量即可。

发现，当 \((L, R)\) 满足条件时，\((L, R – 1)\) 和 \((L + 1, R)\) 也满足条件，所以对于 \(L + 1\)，其可以直接继承 \(L\) 的 \(R\)，因此可以直接双指针。

怎样判断 \(R + 1\) 是不是可以作为 \((L, R)\) 的新结尾呢？

需要判断 \(a_R\) 是不是与 \((L, R)\) 中的每个 \(i\) 都满足 \(|a_i – a_R| \ge D\)，判断这个不等式是否对于每个 \(i\) 都成立，可以直接判断与 \(a_R\) 的值最相近的 \(a_i\)，既小于 \(a_R\) 的第一个 \(a_i\) 和大于 \(a_R\) 的第一个 \(a_i\) 是否满足不等式，判断时可以使用 \(set\) 维护当前区间集合，在 \(O(logn)\) 是时间内找到这两个元素。

关键代码：

void miyan()
{
    ll n, d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    set<int> S;
    auto check = [&](ll x) -> bool
    {
        auto it = S.lower_bound(x);
        if (it != S.end() && *it - x < d)
            return 0;

        it = S.upper_bound(x);
        if (it != S.begin() && x - *prev(it) < d)
            return 0;

        return 1;
    };

    ll ans = 0;
    for (int i = 0, j = 0; i < n; ++i)
    {
        while (j < n && (S.empty() || check(a[j])))
            S.insert(a[j++]);

        ans += j - i;

        S.erase(a[i]);
    }

    cout << ans << endl;
}

F – Half and Median

还没补。