AtCoder Beginner Contest 217 【A - F】

2023-10-21 18:49:58

比赛链接：https://atcoder.jp/contests/abc217/tasks

A - Lexicographic Order

题意

给出两个字符串 \(s,t\) ，若 \(s\) 字典序小于 \(t\) 输出 Yes ，否则输出 No 。

题解

模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    cout << (s < t ? "Yes" : "No") << "\n";
    return 0;
}

B - AtCoder Quiz

题意

给出 ABC 、ARC 、AGC 、AHC 四个字符串中的三个，输出剩下的那一个。

题解

模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x = ‘B‘ ^ ‘R‘ ^ ‘G‘ ^ ‘H‘;
    for (int i = 0; i < 3; i++) {
        string s;
        cin >> s;
        x ^= s[1];
    }
    cout << ‘A‘ << char(x) << ‘C‘ << "\n";
    return 0;
}

C - Inverse of Permutation

题意

给出一个排列，一次输出 \(1,2,\dots,n\) 的下标。

题解

模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    for (auto i : p) {
        cout << i + 1 << ‘ ‘;
    }
    return 0;
}

D - Cutting Woods

题意

有一根长为 \(l\) 米的木棒，从左端起每隔 \(1\) 米有一个标记，给出 \(q\) 次格式为 \((c_i, x_i)\) 询问：

  • 若 \(c_i = 1\) ，将木棒从标记 \(x_i\) 处锯开
  • 若 \(c_i = 2\) ，输出标记 \(x_i\) 所在木棒的长度，保证不曾从 \(x_i\) 处锯开过

题解

记录所有被锯开的标记，某个标记所在木棒的长度即左右最近被锯开的两个标记间的距离。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int l, q;
    cin >> l >> q;
    set<int> st{0, l};
    while (q--) {
        int c, x;
        cin >> c >> x;
        if (c == 1) {
            st.insert(x);            
        } else {
            auto it = st.upper_bound(x);
            cout << *it - *prev(it) << "\n";
        }
    }
    return 0;
}

E - Sorting Queries

题意

开始时有一个空序列 \(a\) ，给出 \(q\) 次询问：

  • 1 x ，将 \(x\) 添加至 \(a\) 末尾
  • 2 ，输出序列 \(a\) 首部的元素
  • 3 ，将序列 \(a\) 排为升序

题解

利用 queue 和 priority_queue 模拟。

1 x ，将 \(x\) 添加至 queue 末尾

2 ，输出 priority_queue 的首部，若其为空，输出 queue 的首部

3 ，把 queue 中的所有元素弹入 priority_queue 中

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    priority_queue<int, vector<int>, greater<int>> pque;
    queue<int> que;
    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            que.push(x);
        } else if (op == 2) {
            if (not pque.empty()) {
                cout << pque.top() << "\n";
                pque.pop();
            } else {
                cout << que.front() << "\n";
                que.pop();
            }
        } else {
            while (not que.empty()) {
                pque.push(que.front());
                que.pop();
            }
        }
    }
    return 0;
}

F - Make Pair

题意

有 \(2n\) 个学生站为一排，编号为 \(1,2,\dots,2n\) ，给出这 \(2n\) 个学生中的 \(m\) 对好关系。

老师想要进行 \(n\) 次操作：

  • 选择两个相邻且为好关系的学生，将他们移去，若留下间隙，两边的学生保持原次序合并

计算老师有多少种方案来进行这 \(n\) 次操作。

题解

区间 \(dp\) 。

设 \(dp[l][r]\) 为移去区间 \([l, r]\) 所需进行的 \(\frac{(r - l + 1)}{2}\) 次操作的方案数，显然区间长度 \((r - l + 1)\) 须为 \(2\) 的倍数。

对于较大区间 \([l, r]\) 的更新，可以通过枚举与 \(l\) 配对的点 \(x\) 来进行，若 \((l, x)\) 为好关系，则有状态转移方程：

\[dp[l][r] = dp[l + 1][x - 1] \cdot dp[x + 1][r] \cdot C_{p + q}^{p} \]

其中， \(p = \frac{(x - 1) - (l + 1) + 1}{2} + 1\) ， \(q = \frac{r - (x + 1) + 1}{2}\) ，即区间 \([l, x]\) 和 \([x + 1, r]\) 各自需要操作的次数。

因为移去 \((l, x)\) 一定会先移去它们间的 \([l + 1, x- 1]\) ，所以 \(p\) 次操作的方案数为 \(dp[l + 1][x - 1]\) ， \(q\) 次操作的方案数为 \(dp[x + 1][r]\) ，剩下所需决定的即 \(p + q\) 次操作的顺序关系。

因为方案数已包含在 \(dp\) 中，所以 \(p\) 次操作两两无差别， \(q\) 次操作两两无差别，答案即 \(C_{p + q}^{p}(C_{p + q}^{q})\) ，含义为从总共 \(p + q\) 个位置中选择 \(p(q)\) 个放置 \(p(q)\) 次操作。

代码

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

constexpr int N = 405;
constexpr int MOD = 998244353;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

struct Combination {
    vector<Z> fac, inv;

    Combination(int n) : fac(n), inv(n) {
        fac[0] = 1;
        for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
        inv[n - 1] = fac[n - 1].inv();
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1);
    }

    Z C(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[m] * inv[n - m];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    n *= 2;
    vector<vector<int>> edge(N, vector<int> (N));
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edge[a][b] = true;
    }
    vector<vector<Z>> dp(N, vector<Z> (N));
    Combination C(N);
    for (int l = n; l >= 1; l--) {
        for (int r = l + 1; r <= n; r += 2) {
            for (int x = l + 1; x <= r; x += 2) {
                if (edge[l][x]) {
                    Z cur = 1;
                    if (l + 1 <= x - 1) {
                        cur *= dp[l + 1][x - 1];
                    }
                    if (x + 1 <= r) {
                        cur *= dp[x + 1][r];
                    }
                    int p = (l + 1 <= x - 1 ? ((x - 1) - (l + 1) + 1) / 2 : 0) + 1;
                    int q = (x + 1 <= r ? (r - (x + 1) + 1) / 2 : 0);
                    cur *= C.C(p + q, p);
                    dp[l][r] += cur;
                }
            }
        }
    }
    cout << dp[1][n].val() << "\n";
    return 0;
}

参考

https://atcoder.jp/contests/abc217/submissions/25575778

https://codeforces.com/blog/entry/94543?#comment-835878

https://codeforces.com/blog/entry/94543?#comment-835926

AtCoder Beginner Contest 217 【A - F】

上一篇：第三章


下一篇：OpenZeppelin 7个最常使用的合约