CSP2021-S 题解

    CSP2021-S 题解

    T1. 廊桥分配

    LOJ 3542

    Solution

    考虑分别求出分配给 “ 国内区 “ 与 “ 国际区 “ ii 个廊桥时能停靠的飞机数 fif_i 与 gig_i。

    则答案为 max⁡0≤i≤n{fi+gn−i}\max\limits_{0 \leq i \leq n} \{ f_i + g_{n - i} \}。

    注意到求 f,gf, g 两个数组的过程是一样的,这里以求 ff 数组为例。

    一开始国内区没有廊桥。考虑将每个飞机的「抵达时间」和「起飞时间」放入一个序列后排序,使用类似扫描线的方法求解:

    • 若遇到的是一个飞机的「抵达时间」。

      • 若当前没有可供停靠的廊桥,则新建一个廊桥停靠;
        否则找一个当前没有停靠飞机、且编号最小的廊桥停靠(使用小根堆维护当前可供停靠的廊桥编号)。
      • 然后该将贡献计入该廊桥中。
    • 若遇到的是一个飞机的「起飞时间」。则将该飞机停靠的廊桥的编号放入小根堆。

    最后对这个贡献数组求一遍前缀和即可求出 ff 数组。

    时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue> 
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 100100;
    
    int n, m1, m2;
    
    int bel[N];
    
    int len;
    struct Node {
        int x, state, id;
    
        Node() {}
        Node(int A, int B, int C) : x(A), state(B), id(C) {} 
    } seq[N * 2];
    
    bool cmp(Node A, Node B) {
        return A.x < B.x;
    }
    
    int f[N], g[N];
    int num[N];
    
    int cnt;
    priority_queue<int> q;
    
    void solve(int m, int f[N]) {
        len = 0, cnt = 0;
        while (q.size()) q.pop(); 
        memset(bel, 0, sizeof(bel));
        memset(num, 0, sizeof(num));
    
        for (int i = 1; i <= m; i ++) {
            int l = read(), r = read();
            seq[++ len] = (Node) { l, 0, i };
            seq[++ len] = (Node) { r, 1, i };
        }
    
        sort(seq + 1, seq + 1 + len, cmp);
    
        for (int i = 1; i <= len; i ++) {
            if (seq[i].state) {
                q.push(-bel[seq[i].id]);
            } else {
                if (q.size()) {
                    int id = -q.top(); q.pop();
                    bel[seq[i].id] = id;
                    num[id] ++;
                } else {
                    int id = ++ cnt;
                    bel[seq[i].id] = id;
                    num[id] ++;
                }
            }
        }
    
        for (int i = 1; i <= m; i ++) f[i] = f[i - 1] + num[i];
    }
    
    int main() {
        n = read(), m1 = read(), m2 = read();
    
        solve(m1, f);
        solve(m2, g);
    
        int ans = 0;
        for (int i = 0; i <= n; i ++) {
            int x = i, y = n - i;
    
            if (x > m1) x = m1;
            if (y < 0) y = 0; if (y > m2) y = m2;
    
            ans = max(ans, f[x] + g[y]);
        }
    
        printf("%d\n", ans);
    
        return 0;
    }

    T2. 括号序列

    LOJ 3543

    Solution

    显然 dp。线性 dp 不易处理题目中的变换规则,可以考虑区间 dp。

    首先可以 O(n2)\mathcal{O}(n^2) 预处理一个数组 ok(i,j)ok(i, j) 表示:区间 [i,j][i, j] 中的字符串能否表示为不超过 kk 个字符 * 的非空字符串。

    然后定义 dp 状态:

    • f0(l,r)f_0(l, r):表示区间 [l,r][l, r] 中的字符,能组成多少个符合规范的超级括号序列。
    • f1(l,r)f_1(l, r):表示区间 [l,r][l, r] 中的字符,能组成多少个形如 (A) 的超级括号序列。
    • f2(l,r)f_2(l, r):表示区间 [l,r][l, r] 中的字符,能组成多少个形如 SA 的超级括号序列。
    • f3(l,r)f_3(l, r):表示区间 [l,r][l, r] 中的字符,能组成多少个形如 AS 的超级括号序列。

    • 对于 f0f_0 的转移:
      • 第一种是形如 (...) 的转移。
      • 第二种是形如 AB、ASB 的转移。
        为了做到不重复计数(例如 ABC 可以看成 A + BC 和 AB + C,但是这两种转移本质上是一个方案),我们可以强行认为 AB、ASB 中的 A 是形如 (...) 的串,这样就不会重复计数了。
    f0(l,r)=f1(l,r)+∑l≤k<rf1(l,k)×(f0(k+1,r)+f2(k+1,r))f_0(l, r) = f_1(l, r) + \sum\limits_{l \leq k < r} f_1(l, k) \times \left(f_0(k + 1, r) + f_2(k + 1, r)\right)
    • 对于 f1f_1 的转移:
      • 首先要判断一下 sls_l 是否为字符 ( 或 ? 的其中一个,srs_r 是否为字符 ) 或 ? 的其中一个。
        若不满足,则 f1(l,r)=0f_1(l, r) = 0。
      • 第一种是形如 (*...*) 的转移。
      • 第二种是形如 (A) 的转移。
      • 第三种是形如 (SA) 的转移。
      • 第四种是形如 (AS) 的转移。
    f1(l,r)=[ok(l+1,r−1)=1]+f0(l+1,r−1)+f2(l+1,r−1)+f3(l+1,r−1)f_1(l, r) = [ok(l + 1, r - 1) = 1] + f_0(l + 1, r - 1) + f_2(l + 1, r - 1) + f_3(l + 1, r - 1)
    • 对于 f2f_2 的转移:
    f2(l,r)=∑l≤k<r,ok(l,k)=1f0(k+1,r)f_2(l, r) = \sum\limits_{l \leq k < r, ok(l,k) = 1} f_0(k + 1, r)
    • 对于 f3f_3 的转移:
    f3(l,r)=∑l<k≤r,ok(k,r)=1f0(l,k−1)f_3(l, r) = \sum\limits_{l < k \leq r, ok(k, r) = 1} f_0(l, k - 1)

    最后的答案即为 f0(1,n)f_0(1, n),时间复杂度 O(n3)\mathcal{O}(n^3)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 510;
    const int mod = 1e9 + 7;
    
    int n, k;
    char s[N];
    
    bool ok[N][N];
    
    bool inc(int i, int j) {
        if (s[i] != '(' && s[i] != '?') return 0;
        if (s[j] != ')' && s[j] != '?') return 0;
        return 1;
    }
    
    long long f[4][N][N];
    
    int main() {
        scanf("%d%d", &n, &k);
        scanf("%s", s + 1);
    
        for (int i = 1; i <= n; i ++)
            for (int j = i; j <= n; j ++) {
                if (j - i >= k) break;
                if (s[j] != '*' && s[j] != '?') break;
    
                ok[i][j] = 1;
            }
    
        for (int i = 1; i < n; i ++)
            if (inc(i, i + 1)) f[0][i][i + 1] = f[1][i][i + 1] = 1;
    
        for (int len = 3; len <= n; len ++)
            for (int l = 1; l <= n - len + 1; l ++) {
                int r = l + len - 1;
    
                // f_1: (...)
    
                if (inc(l, r)) {
                    if (ok[l + 1][r - 1]) f[1][l][r] = 1;
                    f[1][l][r] += f[0][l + 1][r - 1];
                    f[1][l][r] += f[2][l + 1][r - 1];
                    f[1][l][r] += f[3][l + 1][r - 1];
                    f[1][l][r] %= mod;
                }
    
                // f_2: SA
    
                for (int k = l; k < r; k ++) {
                    if (!ok[l][k]) break;
                    f[2][l][r] = (f[2][l][r] + f[0][k + 1][r]) % mod;
                }
    
                // f_3: AS 
    
                for (int k = r; k > l; k --) {
                    if (!ok[k][r]) break;
                    f[3][l][r] = (f[3][l][r] + f[0][l][k - 1]) % mod;
                }
    
                // f_0: all
    
                f[0][l][r] = f[1][l][r];
    
                for (int k = l; k < r; k ++)
                    f[0][l][r] = (f[0][l][r] + f[1][l][k] * f[0][k + 1][r]) % mod;
    
                for (int k = l; k < r; k ++)
                    f[0][l][r] = (f[0][l][r] + f[1][l][k] * f[2][k + 1][r]) % mod;
            }
    
        printf("%d\n", f[0][1][n]);
    
        return 0;
    }

    T3. 回文

    LOJ 3544

    Solution

    因为第一步的操作至多只有两种,所以可以对第一步的操作进行分类讨论。

    这里以第一步执行操作 1(取最左边的数)为例,第一步执行操作 2 同理。

    注意到题目中 bb 序列是回文序列,一定有 bi=b2n+1−ib_{i} = b_{2n + 1 - i}。

    所以在执行第 ii 次操作的时候,一定要保证第 2n+1−i2n + 1 - i 次操作时可以找到一个数与之对应。于是我们可以在考虑第 ii 次操作时,即刻判断第 2n+1−i2n + 1 - i 次操作。

    因为第一步执行了操作 1,显然有 b1=b2n=a1b_1 = b_{2n} = a_1,于是我们可以找到一个数 tar≠1\text{tar} \neq 1,使得 atar=a1a_{\text{tar}} = a_1。

    将 aa 序列分成两段 [2,tar)[2, \text{tar})、(tar,2n](\text{tar}, 2n],分别记这两段区间为 A,BA, B。其中 A,BA, B 的实际意义分别为:aa 序列在 左半段 / 右半段 还可以选的数的区间。

    显然,对于任意的 i(2≤i≤n)i(2 \leq i \leq n):

    • 第 ii 次操作只可以从「AA 的左端」或「BB 的右端」取。
      • 这一次取的数将会从「AA 的左端」或「BB 的右端」弹出。
    • 第 2n+1−i2n + 1 - i 次操作只可以从「AA 的右端」或「BB 的左端」取。
      • 这一次取的数将会从「AA 的右端」或「BB 的左端」弹出。

    于是我们可以使用两个双端队列 QA,QB\mathtt{Q_A}, \mathtt{Q_B} 来维护区间 A,BA, B 里的数。起初队列 QA\mathtt{Q_A} 从队头到队尾是 a2→atar−1a_2 \to a_{\text{tar} - 1},队列 QB\mathtt{Q_B} 从队头到队尾是 a2n→atar+1a_{2n} \to a_{\text{tar} + 1}。

    那么,对于任意的 i(2≤i≤n)i(2 \leq i \leq n),第 ii 次操作与第 2n+1−i2n + 1 - i 次操作选的数,一定即出现在 QA\mathtt{Q_A} 或 QB\mathtt{Q_B} 的队头,又出现在 QA\mathtt{Q_A} 或 QB\mathtt{Q_B} 的队尾。在找不到这样的数的时候,就无解;在有多种选数方案时,选择字典序最小的那一种。

    时间复杂度 O(n)\mathcal{O}(n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 500100;
    
    int n;
    int a[N * 2];
    
    int target;
    
    char ans[N * 2];
    
    deque<int> qA, qB;
    
    bool solve() {
        for (int i = 2; i <= n; i ++) {
            if (qA.size() == 0) {
                if (qB.front() == qB.back())
                    ans[i] = 'R', ans[2 * n + 1 - i] = 'R',
                    qB.pop_front(), qB.pop_back();
                else
                    return 0;
            } else if (qB.size() == 0) {
                if (qA.front() == qA.back())
                    ans[i] = 'L', ans[2 * n + 1 - i] = 'L',
                    qA.pop_front(), qA.pop_back();
                else
                    return 0;
            } else {
                if (qA.size() > 1 && qA.front() == qA.back()) {
                    ans[i] = 'L', ans[2 * n + 1 - i] = 'L',
                    qA.pop_front(), qA.pop_back();
                    continue;
                } else if (qA.front() == qB.back()) {
                    ans[i] = 'L', ans[2 * n + 1 - i] = 'R',
                    qA.pop_front(), qB.pop_back();
                    continue;
                }
    
                if (qB.front() == qA.back()) {
                    ans[i] = 'R', ans[2 * n + 1 - i] = 'L',
                    qB.pop_front(), qA.pop_back();
                    continue;
                } else if (qB.size() > 1 && qB.front() == qB.back()) {
                    ans[i] = 'R', ans[2 * n + 1 - i] = 'R',
                    qB.pop_front(), qB.pop_back();
                    continue;
                }
    
                return 0;
            }
        }
    
        return 1;
    }
    
    void work() {
        n = read();
    
        for (int i = 1; i <= 2 * n; i ++)
            a[i] = read();
    
        /* ----- ----- left ----- ----- */
    
        while (qA.size()) qA.pop_back();
        while (qB.size()) qB.pop_back();
    
        ans[1] = 'L', ans[2 * n] = 'L';
    
        for (int i = 2; i <= 2 * n; i ++)
            if (a[i] == a[1]) { target = i; break; }
    
        for (int i = 2; i < target; i ++) qA.push_back(a[i]);
        for (int i = 2 * n; i > target; i --) qB.push_back(a[i]);
    
        if (solve()) {
            for (int i = 1; i <= 2 * n; i ++) printf("%c", ans[i]);
            puts("");
    
            return;
        }
    
        /* ----- ----- right ----- ----- */
    
        while (qA.size()) qA.pop_back();
        while (qB.size()) qB.pop_back();
    
        ans[1] = 'R', ans[2 * n] = 'L';
    
        for (int i = 1; i < 2 * n; i ++)
            if (a[i] == a[2 * n]) { target = i; break; }
    
        for (int i = 1; i < target; i ++) qA.push_back(a[i]);
        for (int i = 2 * n - 1; i > target; i --) qB.push_back(a[i]);
    
        if (solve()) {
            for (int i = 1; i <= 2 * n; i ++) printf("%c", ans[i]);
            puts("");
    
            return;
        }
    
        /* ----- ----- No ----- ----- */
    
        puts("-1");
    }
    
    int main() {
        int T = read();
    
        while (T --)
            work();
    
        return 0;
    }

    T4. 交通规划

    LOJ 3545

    Solution

    (待填 …)