Codeforces Round #1016(Div.3)

D

题目大意：Vadim 喜欢用整数填充正方形表格。但今天他想出了一个有趣的方法！以 $2 \times 2$ 的表格为例，行从上到下编号，列从左到右编号。我们在左上角单元格放置 $1$，右下角放置 $2$，左下角放置 $3$，右上角放置 $4$。这就是他需要的全部乐趣！幸运的是，Vadim 有一个大小为 $2^n \times 2^n$ 的表格。他计划用 $1$ 到 $2^{2n}$ 的整数按升序填充它。为了填充这么大的表格，Vadim 会将其分成 $4$ 个相等的正方形子表格，先填充左上角的子表格，然后是右下角的子表格，接着是左下角的子表格，最后是右上角的子表格。

数据范围：$1 \leq t \leq 10$，$1 \le n \le 30$，$1 \le q \le 20\,000$，$1 \le x, y \le 2^n$，$1 \le d \le 2^{2n}$，$\sum q \le 20\,000$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void solve() {
    ll n, q, x, y;
    string op;
    cin >> n >> q;
    auto dfs = [&](this auto&& dfs, ll qx, ll qy, ll x, ll y, ll len) -> ll {
        if (len == 2) {
            if (qx == x && qy == y) return 1;
            if (qx == x + 1 && qy == y + 1) return 2;
            if (qx == x + 1 && qy == y) return 3;
            if (qx == x && qy == y + 1) return 4;
        }
        ll tem = (len / 2) * (len / 2);
        if (qx < x + len / 2 && qy < y + len / 2) return dfs(qx, qy, x, y, len / 2);
        if (qx >= x + len / 2 && qy >= y + len / 2) return tem + dfs(qx, qy, x + len / 2, y + len / 2, len / 2);
        if (qx >= x + len / 2 && qy < y + len / 2) return 2 * tem + dfs(qx, qy, x + len / 2, y, len / 2);
        if (qx < x + len / 2 && qy >= y + len / 2) return 3 * tem + dfs(qx, qy, x, y + len / 2, len / 2);
    };
    auto dfs2 = [&](this auto&& dfs2, ll d, ll x, ll y, ll len) -> pll {
        if (len == 2) {
            if (d == 1) return {x, y};
            if (d == 2) return {x + 1, y + 1};
            if (d == 3) return {x + 1, y};
            if (d == 4) return {x, y + 1};
        }
        ll tem = (len / 2) * (len / 2);
        if (d <= tem) return dfs2(d, x, y, len / 2);
        if (d <= 2 * tem) return dfs2(d - tem, x + len / 2, y + len / 2, len / 2);
        if (d <= 3 * tem) return dfs2(d - 2 * tem, x + len / 2, y, len / 2);
        if (d <= 4 * tem) return dfs2(d - 3 * tem, x, y + len / 2, len / 2);
    };
    rep(i, 0, q - 1) {
        cin >> op;
        if (op == "->") {
            cin >> x >> y;
            cout << dfs(x, y, 1, 1, (1LL << n)) << endl;
        } else {
            cin >> x;
            auto [a, b] = dfs2(x, 1, 1, (1LL << n));
            cout << a << ' ' << b << endl;
        }
    }
    return;
}

E

题目大意：给定一个长度为 $n$ 的数组 $a$ 和一个数字 $k$。子数组被定义为数组中一个或多个连续元素组成的序列。需要将数组 $a$ 分割成 $k$ 个互不重叠的子数组 $b_1, b_2, \dots, b_k$，使得这些子数组的并集等于整个数组。此外，需要最大化 $x$ 的值，其中 $x$ 等于所有子数组 $b_i$（$i \in [1..k]$）的 MEX 的最小值。MEX $(v)$ 表示数组 $v$ 中未出现的最小非负整数。

数据范围：$1\leq t\leq 10^4$，$1\leq k \leq n \leq 2 \cdot 10^5$，$0\leq a_i\leq 10^9$，$\sum n \le 2 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll l = 0, r = n, mid, ans = 0;
    auto check = [&](ll mid) -> bool {
        ll tot = 0;
        vl cnt(mid + 1);
        int tot2 = 0;
        rep(i, 0, n - 1) {
            if (a[i] <= mid) cnt[a[i]]++;
            while (tot2 <= mid && cnt[tot2]) tot2++;
            if (tot2 >= mid) {
                ranges::fill(cnt, 0);
                tot2 = 0;
                tot++;
            }
        }
        return tot >= k;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << ans << endl;
    return;
}

F

题目大意：黑客们再次尝试利用神经网络的输出来创造有趣的短语。这次，他们希望获得一个长度为 $n$ 的字符串数组 $a$。最初，他们有一个长度为 $n$ 的数组 $c$，其中所有位置都是空白，用符号 $*$ 表示。黑客们可以访问 $m$ 个神经网络，每个神经网络都有自己对请求的答案版本——一个长度为 $n$ 的字符串数组 $b_i$。

数据范围：$1 \le t \le 1000$，$1 \le n, m \le 500$，$1 \le |a_i| \le 10$，$1 \le |b_{i,j}| \le 10$，$\sum |a_i| \le 2 \cdot 10^5$，$\sum |b_{i, j}| \le 2 \cdot 10^5$，$\sum n \cdot m \le 2 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve() {
    ll n, m;
    cin >> n >> m;
    vector<string> ma(n);
    vector<vector<string>> ma2(m, vector<string>(n));
    rep(i, 0, n - 1) cin >> ma[i];
    rep(i, 0, m - 1) { rep(j, 0, n - 1) cin >> ma2[i][j]; }
    rep(i, 0, n - 1) {
        bool flag = false;
        rep(j, 0, m - 1) {
            if (ma2[j][i] == ma[i]) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            cout << -1 << endl;
            return;
        }
    }
    ll ans = 3 * n;
    rep(i, 0, m - 1) {
        ll ans2 = 0;
        rep(j, 0, n - 1) ans2 += (ma2[i][j] == ma[j]);
        ans = min(ans, 3 * n - 2 * ans2);
    }
    cout << ans << endl;
    return;
}

G

题目大意：一个长度为 $m$ 的数组 $b$ 的美观度定义为所有可能数对 $1 \le i \le j \le m$ 中 $b_i \oplus b_j$ 的最大值，其中 $x \oplus y$ 表示数字 $x$ 和 $y$ 的按位异或。我们将数组 $b$ 的美观度记为 $f(b)$。如果一个数组 $b$ 满足 $f(b) \ge k$，则称该数组是美观的。最近，Kostya 从商店购买了一个长度为 $n$ 的数组 $a$。他认为这个数组太长了，因此计划从中截取一个美观的子数组。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$0 \le k \le 10^9$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 01-Trie 短版：只留最常用的插入和最大异或
// 需要删除就给每个点 cnt--；需要 min_xor 就优先走同位。
template <int LOG = 30>
struct BinaryTrieLite {
    struct Node {
        int ch[2];
        int cnt;
        int idx;

        Node(int x = -1) : cnt(0), idx(x) { ch[0] = ch[1] = -1; }
    };

    vector<Node> tr;

    BinaryTrieLite() { tr.push_back(Node()); }

    int newnode() {
        tr.push_back(Node());
        return (int)tr.size() - 1;
    }

    void insert(long long x, int idx) {
        int u = 0;
        tr[u].cnt++;
        tr[u].idx = max(tr[u].idx, idx);
        for (int i = LOG; i >= 0; i--) {
            if (u == -1) break;
            int b = (x >> i) & 1;
            if (tr[u].ch[b] == -1) {
                tr[u].ch[b] = newnode();
            }
            u = tr[u].ch[b];
            tr[u].cnt++;
            tr[u].idx = max(tr[u].idx, idx);
        }
    }

    int query(ll x, ll k) {
        int u = 0;
        int ans = -1;
        frep(i, LOG, 0) {
            if (u == -1) break;
            int tem = (x >> i) & 1;
            int tem2 = (k >> i) & 1;
            if (tem2 == 0) {
                int v = tr[u].ch[tem ^ 1];
                if (v != -1) ans = max(ans, tr[v].idx);
                u = tr[u].ch[tem];
            } else {
                u = tr[u].ch[tem ^ 1];
            }
        }
        if (u != -1) ans = max(ans, tr[u].idx);
        return ans;
    }

    long long max_xor(long long x) {
        if (tr[0].cnt == 0) return 0;
        int u = 0;
        long long ans = 0;
        for (int i = LOG; i >= 0; i--) {
            int b = (x >> i) & 1;
            int v = tr[u].ch[b ^ 1];
            if (v != -1 && tr[v].cnt > 0) {
                ans |= 1LL << i;
                u = v;
            } else {
                u = tr[u].ch[b];
            }
        }
        return ans;
    }
};
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    if (k == 0) {
        cout << 1 << endl;
        return;
    }
    BinaryTrieLite<30> trie;
    int ans = INT_MAX;
    rep(r, 0, n - 1) {
        int tem = trie.query(a[r], k);
        if (tem != -1) ans = min(ans, r - tem + 1);
        trie.insert(a[r], r);
    }
    cout << (ans == INT_MAX ? -1 : ans) << endl;
    return;
}