C 题：煎牛肉

题目描述

阿斯特（Asrit）想煎牛肉。他有一个大平底锅，最多可以同时放下 n 块牛肉。

煎牛肉的规则如下：

• 每块牛肉有 k 个面；
• 煎任意一个面恰好需要 1 秒；
• 翻面不消耗额外时间；
• 牛肉可以随时拿起或放下。如果某块牛肉还没有煎完所有 k 个面，它可以暂时离开平底锅，之后再放回去继续煎剩下的面。

现在阿斯特要煎 m 块牛肉，请你求出所需的最少秒数。

算法思路

本题是一道极简的调度问题，不需要模拟煎肉过程，只需要考虑两个必然的下界，而这两个下界恰好可以达到。

总工作量：
总共需要煎的面数为
\[ \text{total\_sides} = m \times k \]

下界 1 —— 平底锅容量限制
平底锅每秒最多只能煎 n 个面（因为最多同时放 n 块，每块煎一个面）。因此，即使没有任何空闲，所需时间也至少是
\[ \left\lceil \frac{m \times k}{n} \right\rceil \]

下界 2 —— 单块牛肉的时间限制
同一块牛肉有 k 个面，而同一秒内一块牛肉最多只能煎一个面（你不能同时煎同一块的两个面）。因此，不管锅有多大，煎完一块牛肉至少需要 k 秒，所以总时间至少为 k。

综上，答案至少是这两个下界的最大值： \[ \text{ans} = \max\left(k,\ \left\lceil \frac{m \times k}{n} \right\rceil\right) \]

为什么这个下界一定能达到？
当总时间 T 满足 T ≥ k 且 n × T ≥ m × k 时，我们可以把 m × k 个“面任务”安排到 T 个时间槽中，每个时间槽有 n 个空位，总计 n × T 个空位，足以容纳所有任务。同时，由于 T ≥ k，没有任何一块牛肉会需要在同一秒内煎两个面（因为每块牛肉的 k 个面可以均匀分布在前 k 秒内，剩余时间只用于其他块）。因此通过轮换放取，可以保证所有面都在 T 秒内煎完。该构造方法常见于“多机调度”或“装箱”问题，此处不赘述细节。

参考代码（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, k;          // n: 容量, m: 块数, k: 面数
    cin >> n >> m >> k;

    ll total_sides = m * k;                      // 总面数
    ll ans = max(k, (total_sides + n - 1) / n); // 上取整除法

    cout << ans << '\n';
    return 0;
}

---

K 题：数字 "8" 的判断

题目描述

给定一个由 0 和 1 组成的矩阵，表示一张像素图。你需要判断该像素图是否构成数字 "8"。

当且仅当满足以下两个条件时，认为该像素图表示数字 "8"：

1. 所有值为 1 的像素点恰好构成 一个 四连通块。
2. 在该 1 的连通块内部，恰好存在 两个 "洞"。

其中，"洞"定义为满足以下条件的 0 的四连通块：

• 该连通块被 1 完全包围（即其所有相邻的外部像素均为 1）且 均不与矩阵边界接触。

说明：两个像素点在四连通意义下相邻，当且仅当它们在上下左右四个方向之一相邻。

算法思路

本题核心是连通块计数，利用 DFS / BFS 对 0 和 1 分别进行四连通标记。

步骤

1. 外围填充：在原矩阵外圈添加一层 0，以便于后续处理边界连通性。

2. 标记外部 0：从 (0,0) 开始 DFS，将所有与边界相连的 0 连通块标记为已访问（这些 0 不属于洞）。

3. 扫描内部：遍历原矩阵内部所有未访问的像素（即 (1,1) 到 (n,m)），每遇到一个未访问的像素，就对其所在的连通块进行 DFS，并记录该连通块的颜色（0 或 1），同时计数： - cnt1：1 连通块的数量。 - cnt0：0 连通块的数量（即洞的数量）。

4. 判断条件： - cnt1 == 1（所有 1 构成一个连通块）。 - cnt0 == 2（恰好两个洞）。

满足以上两个条件则输出 This is eight.，否则输出 I don't know what this number is.

---

正确性说明

• 外部 0 被预先标记，所以扫描时未访问的 0 一定是被 1 完全包围且不接触边界的，符合“洞”的定义。
• 数字 "8" 的拓扑结构恰有一个外边界（1 的连通块）和两个内部空洞（上下两个圈），因此上述计数条件充分必要。

参考代码（C++）

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

const int xx[] = {1, 0, -1, 0};
const int yy[] = {0, 1, 0, -1};

int n, m;
vector<vector<int>> g;
vector<vector<int>> vis;

void dfs(int x, int y, int c) {
    vis[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x + xx[i], ny = y + yy[i];
        if (nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1) continue;
        if (vis[nx][ny] || g[nx][ny] != c) continue;
        dfs(nx, ny, c);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    g.assign(n + 2, vector<int>(m + 2, 0));
    vis.assign(n + 2, vector<int>(m + 2, 0));

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> g[i][j];

    // 标记所有与边界相连的 0
    dfs(0, 0, 0);

    vector<int> ans(2, 0); // ans[0] 表示 0 连通块数，ans[1] 表示 1 连通块数

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!vis[i][j]) {
                dfs(i, j, g[i][j]);
                ans[g[i][j]]++;
            }

    if (ans[1] == 1 && ans[0] == 2)
        cout << "This is eight." << endl;
    else
        cout << "I don't know what this number is." << endl;

    return 0;
}

---

总结

本题的关键在于利用 DFS 统计内外连通块数量，并正确区分边界 0 与内部“洞”。只要理清四连通的定义和包围关系，代码实现并不复杂。