AtCoder Beginner Contest 217

发表于2021-09-08更新于2023-09-15字数统计1.7k阅读时长17分

比赛链接

D Cutting Woods

Description

题目链接

Solution

设 x1≤x≤x2x_1 \le x \le x_2，x1,x2x_1,x_2 分别为 xx 左边第一个被切过的位置和右边第一个被切过的位置，那么 xx 所属木头段的长度为 x2−x1x_2-x_1。为了快速求得 x1,x2x_1,x_2，我们将切过的位置插入 set 中，查询时使用 upper_bound 函数即可。

Code

Cutting Woods
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    set<int> s;
    s.insert(n);
    s.insert(0);
    for (int i = 1; i <= m; i++) {
        int c, x;
        cin >> c >> x;
        if (c == 1) {
            s.insert(x);
        } else {
            auto it = s.lower_bound(x);
            int r = *it;
            int l = *(--it);
            cout << r - l << endl;
        }
    }
    return 0;
}

E Sorting Queries

Description

题目链接

Solution

观察任意时刻序列的结构，容易发现它是由一段升序的序列和一段乱序的序列构成的。对于操作 11，我们将新的元素插在乱序序列的尾部；对于操作 22，取升序序列中首元素，若升序序列为空则取乱序序列的首元素；对于操作 33，我们将乱序序列的元素转移到升序序列中，将元素升序排列。比较自然的想到用队列维护乱序序列，用 set 维护升序序列以快速完成操作 33 中元素顺序的调整。

Code

Sorting Queries
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;

multiset<int> s;
queue<int> q;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int type, x;
        cin >> type;
        if (type == 1)
            cin >> x, q.push(x);
        else if (type == 2) {
            if (s.size())
                cout << *s.begin() << endl, s.erase(s.begin());
            else
                cout << q.front() << endl, q.pop();
        } else {
            while (!q.empty()) {
                s.insert(q.front());
                q.pop();
            }
        }
    }
    return 0;
}

F Make Pair

Description

题目链接

Solution

设 dp[l][r]dp[l][r] 表示将区间 [l,r][l,r] 的学生配对的方案数，采用区间 DPDP，考虑如下转移（规定所有区间长为偶数）：

  • 学生 ll 和 rr 可配对，则有 dp[l][r]←dp[l+1][r−1]dp[l][r] \leftarrow dp[l+1][r-1]。
  • 学生 ll 和 rr 不可配对，我们枚举中间位置 kk。此时我们已知 dp[l][k]dp[l][k] 和 dp[k+1][r]dp[k+1][r]，记 [l,k][l,k] 对应 x=k−l+12x = \frac{k-l+1}{2} 对学生，[k+1,r][k+1,r] 对应 y=r−k2y = \frac{r-k}{2} 对学生。由乘法原理，将这 x+yx+y 对学生配对的方案数等于 dp[l][k]dp[l][k] 乘 dp[k+1][r]dp[k+1][r] 再乘上将这 x+yx+y 对学生进行组合，并保证各自原有的相对顺序不变的方案数。这个方案数可用隔板法求解，结果为 (x+yx)\binom{x+y}{x}。于是我们得到 dp[l][r]←dp[l][k]∗dp[k+1][r]∗(x+yx)dp[l][r] \leftarrow dp[l][k]*dp[k+1][r]*\binom{x+y}{x}。为了保证不重复计算答案，这里要求学生 ll 和 kk 能配对（假设学生 ll 和 kk 不可配对，那么一定存在一个位置 k′k' 和 ll 配对，那么我们得到了三段区间，分别为 [l,k′][l,k']，[k′+1,k][k'+1,k]，[k+1,r][k+1,r]。显然将 [k′+1,k][k'+1,k] 归到 [l,k′][l,k'] 和归到 [k+1,r][k+1,r] 是等价的，这两种情况下学生的配对方式是完全一样的）。

Code

Make Pair
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 4E2 + 5;
const int MOD = 998244353;
int n, m, T;
LL dp[MAXN][MAXN], fac[MAXN * 2], inv[MAXN * 2];
bool good[MAXN][MAXN];

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void add(LL& a, LL b) { a = (a + b) % MOD; }

void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n * 2; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = qpow(fac[i], MOD - 2, MOD);
    }
}

LL C(int n, int m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    n *= 2;
    init();
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        good[a][b] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (good[i][i + 1]) dp[i][i + 1] = 1;
        dp[i][i - 1] = 1;
    }

    for (int len = 4; len <= n; len += 2)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (good[l][r]) add(dp[l][r], dp[l + 1][r - 1]);
            for (int k = l + 1; k <= r - 2; k += 2) {
                int x = (k - l + 1) / 2, y = (r - k) / 2;
                if (good[l][k])
                    add(dp[l][r], dp[l + 1][k - 1] * dp[k + 1][r] % MOD *
                                      C(y + x, x) % MOD);
            }
        }
    cout << dp[1][n];
    return 0;
}

G Groups

Description

题目链接

Solution

设 dp[i][j]dp[i][j] 表示考虑前 ii 个元素，分了 jj 组，各组内元素对 MM 取模的结果互不相同的方案数。显然，我们此时最多分 ii 组，最少分 ⌊(i+M−1)M⌋\lfloor \frac{(i+M-1)}{M} \rfloor 组，因为 [1...i][1...i] 与 ii 模 MM 同余的数有 ⌊(i+M−1)M⌋\lfloor \frac{(i+M-1)}{M} \rfloor 个。对于第 ii 个元素，我们要么将其单独分一组，此时有 dp[i][j]←dp[i−1][j−1]dp[i][j]\leftarrow dp[i-1][j-1]；要么将其分到已有的 jj 组中，但这些组中不能有与之同余的元素，这样的组有 j−⌊i−1M⌋j - \lfloor \frac{i - 1}{M} \rfloor 个，因此有 dp[i][j]←dp[i−1][j]∗(j−⌊i−1M⌋)dp[i][j] \leftarrow dp[i-1][j]*(j - \lfloor \frac{i - 1}{M} \rfloor)。初始条件为 dp[0][0]=1dp[0][0] = 1。

Code

Groups
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 5E3 + 5;
const int MOD = 998244353;
int n, m, T;
LL dp[MAXN][MAXN];

void add(LL& a, LL b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int mi = (i + m - 1) / m;
        for (int k = mi; k <= i; k++) {
            if (k <= i - 1)
                add(dp[i][k], dp[i - 1][k] * (k - (i - 1) / m) % MOD);
            add(dp[i][k], dp[i - 1][k - 1]);
        }
    }
    for (int i = 1; i <= n; i++) cout << dp[n][i] << "\n";
    return 0;
}