学校训练赛的一些题解

第二十一届宁波大学程序设计竞赛（重现赛链接）

C 游戏开发部的小游戏 (C)

赛时并没有写出来，果然dp还得多练）

将所有石头视为容量为 \(n\) 的背包，每堆石头的数量即背包中物品的质量，对于 \(a_i \leq f_i\leq b_i\)，由于 \(f_i\) 最终取值唯一，可当作分组背包处理。将大小为 \(i\) 的 \(t\) 组石子装入剩余容量为 \(j - i\times t\) 的背包，由组合数公式，\(dp[j]\) 方案总数增加 \(dp[j - i\times t] * {{n - j + i\times t}\choose i\times t}/ (i!)^t/(t!)\).

G 黑天鹅的记忆解析 (G)

又是dp题，首先排除 \(s\) 的前 \(m\) 个元素无法组成 \(t\) 的显然不合法情况，设 \(dp[i][j][k]\) 表示考虑到 \(s\) 的第 \(i\) 位、\(t\) 的 \(j\) 至 \(k\) 位已经匹配完成的情况，\(s_i = t_j\) 时即可从 \(j\) 或 \(k\) 端点转移，复杂度 \(O(m^3)\).

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i] == t[j]) {
                for(int k = 0; k < j; k++) {
                    dp[i + 1][k][j] += dp[i][k][j - 1];
                }
                for(int k = j + 1; k < m; k++) {
                    dp[i + 1][j][k] += dp[i][j + 1][k];
                }
                dp[i + 1][j][j] += 2;
            }
        }
    }
    printf("%lld", dp[m][0][m - 1]);

另有：xht说可以暴力dfs，由于每次只能将字符放在开头或结尾处，状态不会超过 \(2^{20}\) 种，想了想挺有道理的，太有实力了）

I 小 Y.的魔法书 (I)

设 \(dp[i][j][k]\) 表示目前考虑到 \(t\) 的第 \(i\) 位、\(s\) 的第 \(j\) 位（怎么和上题有某种类似之处），待匹配的左括号数量为 \(k\) 的方案数。数据范围允许 \(n^2m\) 暴力转移，但不同的匹配过程可能得到相同结果，可以规定额外加入字符时 \(s'\) 不等于 \(s_j\)，避免重复情况出现。

    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= min(i, m); j++) {
            for(int k = 0; k <= i; k++) {
                if(j) {
                    if(s[j] == '(') {
                        if(k) add(dp[i][j][k], dp[i - 1][j - 1][k - 1]); // add取模加法
                        if(k < i) add(dp[i][j][k], dp[i - 1][j][k + 1]);
                        add(dp[i][j][k], dp[i - 1][j][k] * 26 % mo);
                    }
                    else if(s[j] == ')') {
                        if(k < i) add(dp[i][j][k], dp[i - 1][j - 1][k + 1]);
                        if(k) add(dp[i][j][k], dp[i - 1][j][k - 1]);
                        add(dp[i][j][k], dp[i - 1][j][k] * 26 % mo);
                    }
                    else {
                        if(k) add(dp[i][j][k], dp[i - 1][j][k - 1]);
                        if(k < i) add(dp[i][j][k], dp[i - 1][j][k + 1]);
                        add(dp[i][j][k], dp[i - 1][j - 1][k]);
                        add(dp[i][j][k], dp[i - 1][j][k] * 25 % mo);
                    }
                } else {
                    if(k < i) add(dp[i][j][k], dp[i - 1][j][k + 1]);
                    if(k) add(dp[i][j][k], dp[i - 1][j][k - 1]);
                    add(dp[i][j][k], dp[i - 1][j][k] * 26 % mo);
                }
            }
        }
    }
    printf("%lld\n", dp[n][m][0]);

K 五彩斑斓的世界 (K)

若某种颜色出现次数多于4，两两相连后一定会出现交点，可直接判断Yes输出；对于 \(cnt \leq 3\) 的情况，每种颜色的连线将多边形分成2或3个区间，随机生成哈希值作为不同区间的权值，使用线段树区间修改权值、单点查询相同颜色顶点的权值，若权值不相等，则说明该连线至少跨越一个区间，即存在相交情况。

ll val[N * 4], lz[N * 4];
void build(int i, int l, int r) {
    val[i] = lz[i] = 0;
    if(l >= r) return;
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
}
void pushdown(int i) {
    if(lz[i]) {
        val[i * 2] ^= lz[i];
        val[i * 2 + 1] ^= lz[i];
        lz[i * 2] ^= lz[i];
        lz[i * 2 + 1] ^= lz[i];
        lz[i] = 0;
    }
}
void modify(int i, int l, int r, int ql, int qr, ll d) {
    if(ql <= l && qr >= r) {
        val[i] ^= d;
        lz[i] ^= d;
        return;
    }
    pushdown(i);
    int mid = (l + r) / 2;
    if(ql <= mid) modify(i * 2, l, mid, ql, qr, d);
    if(qr > mid) modify(i * 2 + 1, mid + 1, r, ql, qr, d);
}
ll query(int i, int l, int r, int q) {
    if(l == r) return val[i];
    pushdown(i);
    int mid = (l + r) / 2;
    if(q <= mid) return query(i * 2, l, mid, q);
    return query(i * 2 + 1, mid + 1, r, q);
}

由于维护的有效值为单点权值，甚至不需要pushup操作，非常的好写。