场上可能忘记带🧠了

1330A Dreamoon and Ranking Collection

一列$[1,100]$的数，可以向其补$x$个数，问从$[1,k]$都出现过打的最大的$k$是多少。

前缀和找一下最大的$k - cnt[k] = x$，$O(n)$。

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(205);
        for (int i = 0, t; i < n; ++i) {
            cin >> t;
            a[t] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= 200; ++i) {
            a[i] += a[i - 1];
            if (i - a[i] == x) ans = i;
        }
        cout << ans << endl;
    }
    return 0;
}

1330B Dreamoon Likes Permutations

现在有个序列$a$，问把$a$分为两段，且两段都是排列的方案数。

分别记一下每个位置从头从尾的方向是否是排列，然后枚举分界点。
$O(n\log n)$（我这里用了线段树判断是否是排列，应该有别的做法）

B.cpp
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
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

namespace data_struct {
    class segment_tree {
#define nd node[now]
#define ndl node[now << 1]
#define ndr node[now << 1 | 1]
#define mid ((nd.l + nd.r) >> 1)
    public:
        struct segment_node {
            int l, r, val;
        };

        int nn;
        vector<segment_node> node;

        void pushup(int now) {
            nd.val = ndl.val + ndr.val;
        };

        void build(int s, int t, int now = 1) {
            nd.l = s, nd.r = t;
            if (s == t) {
                nd.val = 0;
                return;
            }
            build(s, (s + t) >> 1, now << 1);
            build(((s + t) >> 1) + 1, t, now << 1 | 1);
            pushup(now);
        }

        void update(int s, int t, int x, int now = 1) {
            if (s <= nd.l && t >= nd.r) {
                nd.val |= 1;
                return;
            }
            if (s <= mid)
                update(s, t, x, now << 1);
            if (t > mid)
                update(s, t, x, now << 1 | 1);
            pushup(now);
        }

        int query(int s, int t, int now = 1) {
            if (s <= nd.l && t >= nd.r) {
                return nd.val;
            }
            int ret = 0;
            if (s <= mid) {
                ret += query(s, t, now << 1);
            }
            if (t > mid) {
                ret += query(s, t, now << 1 | 1);
            }
            return ret;
        }

        void init(int nnn) {
            nn = nnn;
            node.resize(nn << 2 | 3);
            build(1, nn);
        }
    } tree;
}
using namespace data_struct;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;

        tree.init(n);
        vector<int> a(n + 5), pre(n + 5), suf(n + 5);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; ++i) {
            tree.update(a[i], a[i], 1);
            if (tree.query(1, i) == i)
                pre[i] = 1;
        }
        tree.init(n);
        for (int i = n; i > 0; --i) {
            tree.update(a[i], a[i], 1);
            if (tree.query(1, n - i + 1) == n - i + 1)
                suf[i] = 1;
        }
        vector<pii> ans;
        for (int i = 1; i < n; ++i) {
            if (pre[i] && suf[i + 1])
                ans.emplace_back(i, n - i);
        }
        cout << ans.size() << endl;
        for (pii i : ans)
            cout << i.first << ' ' << i.second << endl;
    }
    return 0;
}

1329A Dreamoon Likes Coloring

有$n$个位置，$m$个颜色，每个颜色涂长$l_i$的段，问能否让每个格子都被涂色，且最终每个颜色至少留下一格。

因为每个颜色只涂一次，那么从右涂，下一次涂色覆盖它的一部分，仅留下右端点，如果剩余的长度$\geq$当前段长度，就能保证每个颜色出现一次。如果有格子没涂，只需要将后涂的颜色从左涂就行，$O(m)$。

C.cpp
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
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int l[N];

int main() {
    int n, m, nn;
    ll sum = 0;
    cin >> n >> m;
    nn = n;
    vector<int> ans;
    for (int i = 0; i < m; ++i) {
        cin >> l[i];
        sum += l[i];
        if (l[i] > n) {
            cout << -1 << endl;
            return 0;
        }
        ans.emplace_back(n - l[i] + 1);
        --n;
    }
    if (sum < nn) {
        cout << -1 << endl;
        return 0;
    }
    if (ans.back() != 1) {
        ans.back() = 1;
        for (int i = m - 1; i > 0; --i) {
            if (ans[i] + l[i] < ans[i - 1])
                ans[i - 1] = ans[i] + l[i];
        }
    }
    for (int i : ans) cout << i << ' ';
    cout << endl;
    return 0;
}

1329B Dreamoon Likes Sequences

有一个上界$d$，一个任意长度的序列如果$a_i\leq d$，且$\oplus_{j=1}^{i-1} a_i< \oplus_{j=1}^i a_i, i\in [1,n]$即合法，求能构造的合法序列数量。

关键在于异或是不进位的加法，那么新加入的数必定要比前一个数的二进制第一个有效位靠前，所有按每个数二进制最高位分组统计个数$(cnt[i])$，然后设&dp[i]&表示序列最长长度为$i$时的答案，转移方程为：

因为前一组的答案都可以再添加一个当前组的数字，也可以只选当前组的数字，所以是$dp[i - 1] + 1$，$O(32)$。

D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q, m, n;
    cin >> q;
    while (q--) {
        cin >> n >> m;
        vector<int> dp(35), cnt(35);
        for (int i = 0, j = 1; i < 31; ++i) {
            cnt[i] = (min(n, (j << 1) - 1) + 1 - j) % m;
            if (cnt[i] < 0) {
                cnt[i] = 0;
                break;
            }
            j <<= 1;
        }
        for (int i = 1; i < 32; ++i)
            dp[i] = (ll(dp[i - 1] + 1) * cnt[i - 1] + dp[i - 1]) % m;
        cout << dp[31] << endl;
    }
    return 0;
}

1329C Drazil Likes Heap

有一个满二叉树形式的高$h$的堆，现在可以选择一个位置，将这个位置值变成大儿子的值，然后再递归操作自己的大儿子，问如何操作让堆变成满二叉树且树高为$g$的形式，且权值最小的方案。
（上面说的操作相当于选一个点删除，递归的把大儿子移上来）

因为大顶堆，所以每次从上层操作收益一定是最大的。而当我们选定一个点后，如果操作，那么它的路径是唯一的。因此我们从树顶开始枚举，能删就删。判断是否可以删除，只需要看最终影响的叶子节点的高度，详细可以看代码。$O(2^gh)$

E.cpp
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
#include <bits/stdc++.h>
using namespace std;

const int sz = (1 << 20);

int h, g;
int a[sz << 1], hit[sz << 1];
vector<int> ans;
#define l (u << 1)
#define r l + 1

bool check(int u) {
    int uu = u;
    hit[u] = hit[u >> 1] + 1;
    while (a[u]) {
        if (a[l] > a[r]) u = l;
        else u = r;
        hit[u] = hit[u >> 1] + 1;
    }
    u >>= 1;
    if (hit[u] > g) {
        u = uu;
        while (a[u]) {
            if (a[l] > a[r]) a[u] = a[l], u = l;
            else a[u] = a[r], u = r;
        }
        return true;
    }
    return false;
}

int main() {
    cin >> q;
    while (q--) {
        cin >> h >> g;
        for (int i = 1; i < (1 << h); ++i)
            cin >> a[i];
        for (int i = 1 << h; i < (2 << h); ++i)
            a[i] = 0;
        
        ll sum = 0;
        hit[1] = 1;
        ans.clear();
        for (int i = 1; i < (1 << g); ++i) {
            while (check(i))
                ans.emplace_back(i);
            sum += a[i];
        }
        cout << sum << endl;
        for (int i : ans) cout << i << ' ';
        cout << endl;
    }
    return 0;
}

（下一题太难了，所以结束了）