Codeforces Round 1016 (Div. 3) A-G 题解

A - Ideal Generator

Code

::: details

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        int x; cin >> x;
        if (x % 2 == 1)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}

:::

B - Expensive Number

Solution

显然，变成 $1$ 肯定是最小的答案，思考怎么变成 $1$ ，就是所有不为 $0$ 的个数加上最后一个非 $0$ 数字后 $0$ 的个数

Code

::: details

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

void solve() {
    string s;
    int ans = 0, flg = 1;
    cin >> s;
    reverse(s.begin(), s.end());
    for (auto c : s) {
        if (c == '0') {
            ans += flg;
        }
        else {
            ans += 1;
            flg = 0;
        }
    }
    cout << ans - 1 << '\n';
}

int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

C - Simple Repetition

Solution

当 $k = 1$ 时，直接判断即可
当 $k \neq 1$ 时
- 如果 $n = 1$ 那么需要构造出这个数字，然后判断是否为素数
- 如果 $n \neq 1$ 那么肯定必然不是素数，如果 $k = 2$ ， $n$ 的位数为 $2$ ，那么肯定能被 $101$ 整除，如果 $n$ 的位数为 $3$ 那么肯定能被 $1001$ 整除，以此类推

Code

::: details

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

bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

void solve() {
    int n, k; cin >> n >> k;
    if (k == 1) {
        cout << (is_prime(n) ? "YES" : "NO") << '\n';
        return ;
    }
    if (n == 1) {
        int x = 0;
        for (int i = 1; i <= k; i++)
            x = x * 10 + n;
        cout << (is_prime(x) ? "YES" : "NO") << '\n';
        return ;
    }
    cout << "NO" << '\n';
    return ;
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

D - Skibidi Table

Solution

递归好题

对于第一问，定义函数 $f (x, y, n)$ 表示当边长为 $2^{n}$ 时， $(x, y)$ 位置的值，采用递归思维

当 $x \leq 2^{n - 1}, y \leq 2^{n - 1}$ 时，说明在左上角， $f (x, y, n) = f (x, y, n - 1)$
当 $x > 2^{n - 1}, y > 2^{n - 1}$ 时，说明在右下角， $f (x, y, n) = f (x - 2^{n - 1}, y - 2^{n - 1}, n - 1) + 2^{n - 1} \times 2^{n - 1}$
当 $x > 2^{n - 1}, y \leq 2^{n - 1}$ 时，说明在左下角， $f (x, y, n) = f (x - 2^{n - 1}, y, n - 1) + 2 \times 2^{n - 1} \times 2^{n - 1}$
当 $x \leq 2^{n - 1}, y > 2^{n - 1}$ 时，说明在右上角， $f (x, y, n) = f (x, y - 2^{n - 1}, n - 1) + 3 \times 2^{n - 1} \times 2^{n - 1}$

对于第二问也是同理，定义 $g (d, n)$ 表示，变长为 $2^{n}$ 时， $d$ 数字所在的位置

当 $d \leq 2^{n - 1} \times 2^{n - 1}$ 说明在左上角， $(x, y) = g (d, n - 1)$ ， $g (d, n) = (x, y)$
当 $2^{n - 1} \times 2^{n - 1} < d \leq 2 \times 2^{n - 1} \times 2^{n - 1}$ ，说明在左下角， $(x, y) = g (d - 2^{n - 1} \times 2^{n - 1}, n - 1)$ ， $g (d, n) = (x + 2^{n - 1}, y + 2^{n - 1})$

后面就不写了，同理

Code

::: details

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

ll F[61];

ll query_1 (ll x, ll y, ll n) {
    if (n == 0) return 1;
    ll L = 1ll << n, cnt = L * L / 4;
    if (x <= L / 2 && y <= L / 2)
        return query_1(x, y, n - 1);
    if (x > L / 2 && y > L / 2)
        return query_1(x - L / 2, y - L / 2, n - 1) + cnt;
    if (x > L / 2 && y <= L / 2)
        return query_1(x - L / 2, y, n - 1) + cnt * 2;
    if (x <= L / 2 && y > L / 2)
        return query_1(x, y - L / 2, n - 1) + cnt * 3;
    assert(0);
}

pair<ll, ll> query_2 (ll d, ll n) {
    if (n == 0) return {1, 1};
    ll L = 1ll << n, cnt = L * L / 4;
    if (d <= cnt) {
        auto [x, y] = query_2(d, n - 1);
        return {x, y};
    }
    if (d <= cnt * 2) {
        auto [x, y] = query_2(d - cnt, n - 1);
        return {x + L / 2, y + L / 2};
    }
    if (d <= cnt * 3) {
        auto [x, y] = query_2(d - cnt * 2, n - 1);
        return {x + L / 2, y};
    }
    if (d <= cnt * 4) {
        auto [x, y] = query_2(d - cnt * 3, n - 1);
        return {x, y + L / 2};
    }
    assert(0);
}

void solve() {
    ll n; int q; cin >> n >> q;
    while (q--) {
        string op; cin >> op;
        if (op == "->") {
            ll x, y; cin >> x >> y;
            cout << query_1(x, y, n) << '\n';
        }
        else {
            ll d; cin >> d;
            auto [x, y] = query_2(d, n);
            cout << x << ' ' << y << '\n';
        }
    }
}

int main() {
    freopen ("D.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    for (int i = 0; i < 61; i++) {
        F[i] = (1LL << i);
    }

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

E - Min Max MEX

Question

给定一个长度为 $n$ 当数组 $a$ ，和一个整数 $k$

现在你需要把数组 $a$ 分成 $k$ 段，使得所有段的 mex 的最小值最大

Solution

二分答案 mid，然后去 check 是否能分出 mid 段

对于 check，记录如果从 $0 \sim m i d - 1$ 这些数字都出现过一次，那就段数 $+ 1$

Code

::: details

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

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

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> b(n + 1, 0);

    auto check = [&] (int m) {
        if (m == 0) return true;
        int cnt = 0, now = 0;
        for (int i = 0; i < m; i++)
            b[i] = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] < m && b[a[i]] == 0) {
                b[a[i]] = 1;
                now += 1;
            }
            if (now == m) {
                cnt += 1;
                now = 0;
                for (int j = 0; j < m; j++)
                    b[j] = 0;
            }
        }
        return cnt >= k;
    };

    int L = 0, R = n + 1;
    while (L + 1 < R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            L = mid;
        }
        else {
            R = mid;
        }
    }
    cout << L << '\n';
    return ;
}

int main() {
    freopen ("E.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

F - Hackers and Neural Networks

Question

这个题的题意不是很清楚，读了好久

给定一个长度为 $n$ 的字符串数组 $a$ ， $a_{i}$ 是一个字符串

和一个 $m$ 个长度为 $n$ 的字符串数组 $b$ ， $b_{j, i}$ 是一个字符串

现在 $c$ 是一个为空的，长度为 $n$ 的字符串数组，你需要经过一些操作把 $c$ 变成 $a$ ，操作二选一：

选择一个 $j$ ，计算机会随机选出现在 $c$ 中的一个空位 $i$ ，然后把 $b_{j, i}$ 复制给 $a_{i}$
选择一个位置 $i$ ，令 $c_{i}$ 为空串

需要求最小操作次数，无解则输出 $- 1$

Solution

先考虑无解，对于每一个 $a_{i}$ ，必然存在一个 $j$ 使得 $a_{i} = b_{j, i}$ ，若没有则无解

我们可以构造出一种构造方式，设一个字符串数组 $b_{j}$ 和 $a$ 的不一样的字符串数为 $m i s s$

那么一种可行的方式是：先执行 $n$ 次 $1$ 操作，然后对于哪些和 $b_{j}$ 不一样的位置，执行一次 $2$ 操作，然后针对那个位置一样的 $b_{j}$ 做一次 $1$ 操作

这样的总次数为 $n + 2 \times m i s s$

所以只需要找到 miss 最小的 $j$ 即可

Code

::: details

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

const int INF = 0x3f3f3f3f;

void solve() {
    int n, m; cin >> n >> m;
    vector<string> a(n + 1);
    vector<vector<string>> b(m + 1, vector<string>(n + 1));

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 1; i <= n; i ++) {
        int flg = 0;
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j][i]) {
                flg = 1;
                break;
            }
        }
        if (flg == 0) { // 无解
            cout << "-1\n";
            return;
        }
    }

    int min_miss = INF;
    for (int j = 1; j <= m; j++) {
        int miss = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[j][i]) {
                miss++;
            }
        }
        min_miss = min(min_miss, miss);
    }
    cout << n + 2 * min_miss << '\n';
    return ;
}

int main() {
    freopen ("F.in", "r", stdin);
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

G - Shorten the Array

Question

给定一个长度为 $n$ 的数组 $b$ 和一个整数 $k$

现在需要你选出两个整数 $b_{i}, b_{j}$ ，满足 $b_{i} \oplus b_{j} \geq k$ 且 $j - i + 1, i \leq j$ 最小

Solution

一个很典的题目

建立一颗字典树，字典树的 $a_{i}$ 的最后一个节点记录下 $i$ 的下标，然后维护一个数组 max_son[i] 表示字典树上以 $i$ 为根节点的子树中的最大下标

然后我们定义查询函数，枚举右边的那个数 $j$ ，对于一个 $x = a_{j}$ ，我们需要查询在字典树中满足 $a_{i} \oplus x \geq k$ 的最大下标，

这是一个很经典的做法

枚举 $k$ 的每一位，假设当前枚举到第 $c$ 位，设 $k$ 第 $c$ 位为 $k_{c}$ ， $x$ 的第 $c$ 位为 $x_{c}$

若 $k_{c} = 1$ ，那么需要 $x \oplus a_{i}$ 的这一位为 $1$ ，所以要在字典树上往 $c_{x}$ 的异侧走
若 $k_{c} = 0$ ，如果 $x \oplus a_{i}$ 的这一位为 $1$ ，那么就不需要看后面的位了，需要把当前记录的最大下标和与 $x_{c}$ 异侧的儿子的 max_son 做比较，然后往 $x_{c}$ 的同侧走

每次先把 $j$ 加入字典树中，然后查询，就可以保证字典树中的 $i \leq j$ 了

Code

::: details

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

const int INF = 0x3f3f3f3f;

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    struct Node {
        int x, max_son;
        int ch[2];
        Node() : x(0), max_son(0) {
            ch[0] = ch[1] = -1;
        }
    };
    
    int cnt = 0;
    vector<Node> tree(n * 61);
    
    auto insert = [&] (int x, int id) {
        int cur = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (tree[cur].ch[bit] == -1) {
                tree[cur].ch[bit] = ++cnt;
                tree[cnt] = Node();
            }
            cur = tree[cur].ch[bit];
            tree[cur].max_son = max(tree[cur].max_son, id);
        }
        tree[cur].x = id;
    };

    auto query = [&] (int x) {
        int cur = 0, ret = 0;
        for (int i = 30; i >= 0; i--) {
            int bit_k = (k >> i) & 1, bit_x = (x >> i) & 1;
            if (bit_k == 1) {
                cur = tree[cur].ch[bit_x ^ 1];
            }
            else {
                if (tree[cur].ch[bit_x ^ 1] != -1)
                    ret = max(ret, tree[tree[cur].ch[bit_x ^ 1]].max_son);
                cur = tree[cur].ch[bit_x];
            }
            if (cur == -1) break;
        }
        if (cur != -1)
            ret = max(ret, tree[cur].max_son);
        // ret = max(ret, tree[cur].max_son);
        return ret;
    };

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        insert(a[i], i);
        int ret = query(a[i]);
        if (ret > 0) {
            ans = min(ans, i - ret + 1);
        }
    }
    cout << (ans == INF ? -1 : ans) << '\n';
}

int main() {
    freopen ("G.in", "r", stdin);
    freopen ("G.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::