Codeforces Round 1016 (Div. 3) (opens new window)

A - Ideal Generator

Code

点击查看

#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

点击查看

#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\ne 1$ 时
  • 如果 $n=1$ 那么需要构造出这个数字，然后判断是否为素数
  • 如果 $n\ne 1$ 那么肯定必然不是素数，如果 $k=2$，$n$ 的位数为 $2$，那么肯定能被 $101$ 整除，如果 $n$ 的位数为 $3$ 那么肯定能被 $1001$ 整除，以此类推

Code

点击查看

#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 \le 2^{n-1},y\le 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}\times2^{n-1}$

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

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

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

• 当 $d\le 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\le 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

点击查看

#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 mid-1$ 这些数字都出现过一次，那就段数 $+1$

Code

点击查看

#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$ 的不一样的字符串数为 $miss$

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

这样的总次数为 $n+2\times miss$

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

Code

点击查看

#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\ge k$ 且 $j-i+1,i\le j$ 最小

Solution

一个很典的题目

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

然后我们定义查询函数，枚举右边的那个数 $j$，对于一个 $x=a_j$，我们需要查询在字典树中满足 $a_i \oplus x\ge 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\le j$ 了

Code

点击查看

#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;
}