链接：https://codeforces.com/contest/2093

A. Ideal Generator

算法：

    数学，打表。

思路：

    无。

关键代码：

void solve()
{
    int k;
    cin >> k;

    if (k & 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. Expensive Number

算法：

    贪心。

思路：

    无。

关键代码：

void solve()
{
    string s;
    cin >> s;
    int n = s.size();

    ll ans = MAX;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '0')
            continue;
        ll cnt = n - i - 1;
        for (int j = 0; j < i; ++j)
            if (s[j] != '0')
                ++cnt;
        ans = min(ans, cnt);
    }

    cout << ans << endl;
}

C. Simple Repetition

算法：

    数学，质数。

思路：

    无。

关键代码：

void solve()
{
    int x, k;
    cin >> x >> k;

    if (x == 1)
    {
        if (k == 2)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        return;
    }

    auto check = [](int n) -> bool
    {
        if (n <= 1)
            return 0;
        for (int i = 2; i <= n / i; ++i)
        {
            if (n % i == 0)
                return 0;
        }

        return 1;
    };

    if (check(x) && k == 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

D. Skibidi Table

算法：

    递归。

思路：

    递归寻找两个位置即可。

关键代码：

void solve()
{
    ll n, q;
    cin >> n >> q;

    function<ll(ll, ll, ll)> get1 = [&](ll x, ll y, ll len) -> ll
    {
        ll size = len >> 1ll;
        ll cnt = size * size;

        if (size == 1)
        {
            if (x <= size && y <= size)
                return 1;
            else if (x <= size && y > size)
                return 4;
            else if (x > size && y <= size)
                return 3;
            else
                return 2;
        }

        if (x <= size && y <= size)
            return get1(x, y, size);
        else if (x <= size && y > size)
            return 3 * cnt + get1(x, y - size, size);
        else if (x > size && y <= size)
            return 2 * cnt + get1(x - size, y, size);
        else
            return cnt + get1(x - size, y - size, size);
    };

    function<pair<ll, ll>(ll, ll)> get2 = [&](ll pos, ll len) -> pair<ll, ll>
    {
        ll size = len >> 1ll;
        ll cnt = size * size;
        pair<ll, ll> cur, ans = {0, 0};

        if (size == 1)
        {
            if (pos == 1)
                return make_pair(1, 1);
            else if (pos == 2)
                return make_pair(2, 2);
            else if (pos == 3)
                return make_pair(2, 1);
            else
                return make_pair(1, 2);
        }

        if (pos <= cnt)
        {
            cur = get2(pos, size);
            ans.first += cur.first;
            ans.second += cur.second;
        }
        else if (pos <= cnt * 2)
        {
            cur = get2(pos - cnt, size);
            ans.first += cur.first + size;
            ans.second += cur.second + size;
        }
        else if (pos <= cnt * 3)
        {
            cur = get2(pos - cnt * 2, size);
            ans.first += cur.first + size;
            ans.second += cur.second;
        }
        else
        {
            cur = get2(pos - cnt * 3, size);
            ans.first += cur.first;
            ans.second += cur.second + size;
        }

        return ans;
    };

    while (q--)
    {
        string op;
        ll x, y, d;
        cin >> op;

        if (op[0] == '-')
        {
            cin >> x >> y;

            cout << get1(x, y, (1ll << n)) << endl;
        }
        else
        {
            cin >> d;

            pair<ll, ll> ans = get2(d, (1ll << n));

            cout << ans.first << ' ' << ans.second << endl;
        }
    }
}

E. Min Max MEX

算法：

    二分。

思路：

    对 \(1 \text{~} n\) 间的数字进行二分答案即可。

关键代码：

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 10);
    cin >> a;

    vector<int> st(n + 10, 0);
    int color = 0;
    auto check = [&](int x) -> bool
    {
        ll has = x;
        ll cnt = 0;
        ++color;

        for (int i = 0; i < n; ++i)
        {
            if (a[i] < x && st[a[i]] != color)
            {
                st[a[i]] = color;
                if (!(--has))
                {
                    has = x;
                    ++color;

                    if (++cnt >= k)
                        return 1;
                }
            }
        }

        return cnt >= k;
    };

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l << endl;
}

F. Hackers and Neural Networks

算法：

    模拟。

思路：

    先选取一个匹配数最多的把 \(c\) 填满，再采取消 \(1\) 补 \(1\) 的方法，把 \(c\) 填成目标。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<string> s(n + 10);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    vector<vector<string>> b(m + 10, vector<string>(n + 10));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> b[i][j];

    vector<map<string, int>> hash(n + 10);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            ++hash[j][b[i][j]];

    for (int i = 0; i < n; ++i)
    {
        if (!hash[i].count(s[i]))
        {
            cout << -1 << endl;
            return;
        }
    }

    ll ans = 0;
    for (int i = 0; i < m; ++i)
    {
        ll cnt = 0;
        for (int j = 0; j < n; ++j)
        {
            if (s[j] == b[i][j])
                ++cnt;
        }

        ans = max(ans, cnt);
    }

    cout << n + 2 * (n - ans) << endl;
}

G. Shorten the Array

    还没补。