abc227

FiraCode · 2024-09-18 14:08:28 · 个人记录

A

直接模拟即可

B

直接暴力预处理出所有在 1 ... 1000 中可以被 4ab + 3a + 3b 表示出的数即可。

C

直接暴力时间复杂度是正确的。

D

套路题，之前做过类似的。

二分之后将所有点与 mid 取 \min，此时只要 \sum a_i 是 \ge mid \cdot k 的就合法否则不合法，因为对 mid 取 \min 就相当于限制了每个数选的次数。

E

考虑记搜，枚举所有排列其实可以每次把一个字符扔到前面来实现，而由于我们只关心最后状态是什么不关心中途是怎么换的，那么把某个字符扔到前面实际上只用选最前面的字符即可。

然后把字符串 S 和剩余步数记录一下即可。

#include <bits/stdc++.h>

using namespace std;

namespace A{
    int n, k, a;
    void main() {
        scanf("%d%d%d", &n, &k, &a);
        for (int i = 1; i < k; ++i) {
            a = a % n + 1;
        }

        printf("%d\n", a);
    }
}

namespace B {
    int n, s;
    bool st[10100];

    void init() {
        for (int i = 1; i <= 1000; ++i) {
            for (int j = 1; j <= 1000; ++j) {
                if (4 * i * j + 3 * i + 3 * j > 1000) break;
                st[4 * i * j + 3 * i + 3 * j] = true;
            }
        }
    }

    void main() {
        init();
        int ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            int a;
            scanf("%d", &a);
            ans += !st[a];
        }

        printf("%d\n", ans);
    }
}

namespace C {
    typedef long long ll;

    ll n;

    void main() {
        scanf("%lld", &n);
        ll ans = 0;
        for (ll A = 1; A * A * A <= n; ++A) {
            for (ll B = A; A * B * B <= n; ++B) {
                ll C = n / (A * B) - B + 1;
                ans += C;
            }
        }

        printf("%lld\n", ans);
    }
}

namespace D {
    typedef long long ll;
    int n, k;
    ll a[200010];

    bool check(ll mid) {
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += min(a[i], mid);
        }

        return sum / k >= mid;
    }

    void main() {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

        ll l = 1, r = 200000000000000000;
        while (l < r) {
            ll mid = (l + r + 1) >> 1ll;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        printf("%lld\n", l);
    }
}

namespace E {
    typedef long long ll;
    int k;
    string s;
    map<pair<string, int>, ll> ma;

    ll dfs(string s, int k) {
        if (k < 0) return 0;
        if (s.size() <= 1) return 1;
        if (ma.count({s, k})) return ma[{s, k}];

        ll res = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            if (s[i] == 'K') {
                string t;
                for (int j = 0; j < i; ++j) t += s[j];
                for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];

                res += dfs(t, k - i);

                break;
            }
        }
        for (int i = 0; i < (int)s.size(); ++i) {
            if (s[i] == 'E') {
                string t;
                for (int j = 0; j < i; ++j) t += s[j];
                for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];

                res += dfs(t, k - i);

                break;
            }
        }
        for (int i = 0; i < (int)s.size(); ++i) {
            if (s[i] == 'Y') {
                string t;
                for (int j = 0; j < i; ++j) t += s[j];
                for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];

                res += dfs(t, k - i);

                break;
            }
        }

        return ma[{s, k}] = res;
    }

    void main() {
        cin >> s >> k;
        cout << dfs(s, k);
    }
}