358

A - Welcome to AtCoder Land

请判断 $S$ 是否为 "AtCoder"。 $T$ 是否为"Land"。

void solve() {
    string s, t;cin >> s >> t;
    if (s == "AtCoder" && t == "Land") {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B - Ticket Counter

在 AtCoder 乐园的入口处，有一个售票亭，游客在此排队逐个购票。每个人的购票过程需要 $A$ 秒。一旦排在队伍前面的人完成购票，下一个人（如果有的话）就会立即开始他们的购票过程。

目前，售票点没有人排队， $N$ 人会陆续前来购票。具体地说， $i$ 这个人将在 $T_{i}$ 秒后到达售票点。如果已经有人排队，他们会排在队伍的最后；如果没有，他们会立即开始购票。这里， $T_{1} < T_{2} < \dots < T_{N}$ .

对于每个 $i (1 \leq i \leq N)$ ，确定从现在起 $i$ /th 的人将在多少秒后完成购票。

#define int long long
void solve() {
    int n, a;cin >> n >> a;
    int pre = 0;
    for (int i = 0; i < n; i++) {
        int t;cin >> t;
        int ans = max(pre, t) + a;
        cout << ans << '\n';
        pre = ans;
    }
}

C - Popcorn

在 AtCoder 乐园里，有 $N$ 个爆米花摊位，编号从 $1$ 到 $N$ 。它们有 $M$ 种不同口味的爆米花，标号为 $1, 2, \dots, M$ ，但并不是每个摊位都出售所有口味的爆米花。 $1 \leq N, M \leq 10$

高桥获得了关于每个摊位出售哪些口味爆米花的信息。这些信息由长度为 $M$ 的 $N$ 字符串 $S_{1}, S_{2}, \dots, S_{N}$ 表示。如果 $S_{i}$ 的 $j$ 个字符是 "o"，则表示 $i$ 摊位出售 $j$ 口味的爆米花。如果是 "x"，则表示 $i$ 号摊位不出售 $j$ 口味的爆米花。每个摊位至少出售一种口味的爆米花，每种口味的爆米花至少在一个摊位上出售。

高桥想尝遍所有口味的爆米花，但又不想走动太多。求高桥至少要去多少个摊位才能买到所有口味的爆米花？

根据数据量，直接二进制枚举即可。

void solve() {
    int n, m;cin >> n >> m;
    vector<string> s(n);
    for (int i = 0;i < n;i++) {
        cin >> s[i];
    }
    int ans = 1e9;
    for (int i = 1;i < (1 << n);i++) {
        vector<int> vis(m);
        for (int j = 0;j <= __lg(i);j++) {
            if (((i >> j) & 1)) {
                for (int k = 0;k < m;k++) {
                    if (s[j][k] == 'o') {
                        vis[k] = 1;
                    }
                }
            }
        }
        int ok = 1;
        for (int j = 0;j < m;j++) {
            if (!vis[j])ok = 0;
        }
        if (ok)ans = min(ans, __builtin_popcount(i));
    }
    cout << ans << '\n';
}

D - Souvenirs

AtCoder 乐园的一家纪念品商店出售 $N$ 盒子。

这些盒子的编号为 $1$ 至 $N$ ，盒子 $i$ 的价格为 $A_{i}$ 日元，里面有 $A_{i}$ 块糖果。

高桥想从 $N$ 盒中买 $M$ 盒，然后送给 $1, 2, \dots, M$ 的 $M$ 人每人一盒。

在这里，他想买的盒子要满足以下条件：

对于每个 $i = 1, 2, \dots, M$ 人， $i$ 都能得到至少装有 $B_{i}$ 粒糖果的盒子。

请注意，不允许给一个人多个盒子，也不允许给多个人同一个盒子。

求是否可能买到满足条件的 $M$ 盒，如果可能，求高桥需要支付的最小总金额。

D 题最简单的一次，双指针即可。

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= m;i++)cin >> b[i];
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    int sum = 0, j = 1;
    for (int i = 1;i <= n && j <= m;i++) {
        if (a[i] >= b[j]) {
            sum += a[i];j++;
        }
    }
    if (j <= m) {
        cout << "-1\n";return;
    }
    cout << sum << '\n';
}

E - Alphabet Tiles

求长度在 $[1, k]$ 之间的由大写英文字母组成的字符串中，满足以下条件的字符串的个数 (模为 $998244353$ )：

对于满足 $1 \leq i \leq 26$ 的每个整数 $i$ ，下面的条件都成立：
- $a_{i}$ 满足 a[i] = 'a' + i - 1
- 字符串中 $a_{i}$ 的出现次数介于区间 $[0, c_{i}]$ 。

$1 \leq K \leq 1000, 0 \leq C_{i} \leq 1000$

Solution

DP+组合数, 是个原题：ABC234_F

典 ——和 P1077 摆花基本一样

$d p_{i, j}$ 代表使用前 $i$ 种字母，已经组成了长度为 $j$ 的字符串的方案数。

转移方程： $d p_{i, j} = \sum_{k = 0}^{min (c_{i}, j)} d p_{i - 1, j - k} \times (\binom{j}{k})$

前 $i$ 种字母长度为 $j$ 的字符串可以由前 $i - 1$ 种字母长度为 $j - k$ 的字符串加上 $k$ 个该字符转移而来，而每种可以转移过来的方式有多种(在长度为 $j$ 的字符串种有 $k$ 个该字符可以任意调换位置，方案数 $(\binom{j}{k})$ )

#define int long long
constexpr int mod = 998244353;
int a[27], f[27][1010], c[1010][1010];
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= 26;i++)cin >> a[i];

    for (int i = 0;i <= n;i++)c[i][0] = 1, c[i][1] = i;
    for (int i = 2;i <= n;i++) {
        for (int j = 2;j <= n;j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];c[i][j] %= mod;
        }
    }

    f[0][0] = 1;
    for (int i = 1;i <= 26;i++) {
        for (int j = 0;j <= n;j++) {
            for (int k = 0;k <= min(a[i], j);k++) {
                f[i][j] += f[i - 1][j - k] * c[j][k];f[i][j] %= mod;
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        ans += f[26][i];ans %= mod;
    }
    cout << ans << '\n';
}

F - Easiest Maze

斯努克计划在 AtCoder 乐园建造一个迷宫作为新景点。迷宫是一个有 $N$ 行和 $M$ 列的网格，右上角单元格的顶边是入口，右下角单元格的底边是出口。他将通过在相邻单元格之间适当放置墙壁来创建迷宫。

他喜欢简单的迷宫，因此他希望从入口到出口的路径正好经过 $K$ 个单元格，且没有任何分支。请判断是否可能创建这样一个迷宫，如果可能，请建造一个。

例如，在下图中， $N = 3$ 和 $M = 3$ ，并在实线处设置墙壁（除入口和出口外，墙壁总是设置在外围）。在这种情况下，从入口到出口的路径正好经过 $7$ 个单元格，没有任何分支。
|125

下面是一个正式的说明。

有一个网格，网格中有 $N$ 行和 $M$ 列。让 $(i, j)$ 表示位于从上往下第 $i$ 行和从左往上第 $j$ 列的单元格。对于每一对边相邻的单元格，你可以决定是否在它们之间放置一堵墙。确定是否有可能放置墙来满足以下条件，如果有可能，请构建一个这样的放置方式。

考虑一个有 $N M$ 个顶点的无向图 $G$ 。 $G$ 的每个顶点都由一对整数 $(i, j) (1 \leq i \leq N, 1 \leq j \leq M)$ 唯一标注。两个不同的顶点 $(i_{1}, j_{1})$ 和 $(i_{2}, j_{2})$ 由一条边连接，当且仅当 $| i_{1} - i_{2} | + | j_{1} - j_{2} | = 1$ 和网格上对应的单元格 $(i_{1}, j_{1})$ 和 $(i_{2}, j_{2})$ 之间没有墙。

条件：存在一条顶点为 $K$ 的简单路径连接两个顶点 $(1, M)$ 和 $(N, M)$ ，且包含顶点 $(1, M)$ 和 $(N, M)$ 的连通部分仅由该路径组成。

G - AtCoder Tour

AtCoder Land 由一个网格表示，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示第 $i$ 行和第 $j$ 列上的单元格。

高桥从 $(S_{i}, S_{j})$ 单元格开始，重复下面的操作 $K$ 次：

他要么停留在当前单元格，要么移动到相邻单元格。在此操作之后，如果他位于 $(i, j)$ 单元格，他将获得 $A_{i, j}$ 的趣味值。

请找出他能获得的最大总乐趣值。

Solution

$d p_{o p, i, j} = max (d p_{o p, i, j}, d p_{o p - 1, p r e i, p r e j} + A_{i, j})$
时间复杂度： $O (n^{2} m^{2})$

#define int long long
int dx[] = {1, 0, -1, 0, 0};
int dy[] = {0, 1, 0, -1, 0};
void solve() {
    int n, m, K;
    cin >> n >> m >> K;
    int Si, Sj;
    cin >> Si >> Sj;
    Si--;
    Sj--;
    vector<vector<int>> A(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }
    int N = min(n * m, K);
    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(n, vector<int>(m, INT_MIN)));
    dp[0][Si][Sj] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                for (int l = 0; l < 5; l++) {
                    int x = j + dx[l];
                    int y = k + dy[l];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        dp[i + 1][x][y] = max(dp[i + 1][x][y], dp[i][j][k] + A[x][y]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, dp[N][i][j] + (K - N) * A[i][j]);
        }
    }
    cout << ans << '\n';
}