T1

求时间间隔最短的两个时刻

• 排序，求最短的相邻时刻的时间间隔。

#include <bits/stdc++.h>

using namespace std;
void Solve() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int x, y, i = 0; i < n; ++i) {
        scanf("%02d:%02d", &x, &y);
        a[i] = x * 60 + y;
    }
    sort(a.begin(), a.end());
    int p = 0;
    for (int i = 1; i < n; ++i)
        if (a[i + 1] - a[i] < a[p + 1] - a[p])
            p = i;
    printf("%02d:%02d ", a[p] / 60, a[p] % 60);
    printf("%02d:%02d\n", a[p + 1] / 60, a[p + 1] % 60);
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

T2

给定一个数组 ，每次操作可以选一个 加 ，在极大值数量最多的情况下，最小化操作次数。

• 显然，极大值的最大数量为 ，即极小值极大值交替：小大小大小…，不妨用 表示极值序列。
• 由于操作只能加，所以 变成极大值的操作次数为
• 如果 为奇数，则答案即为
• 如果 为偶数，极值序列为 ，即最后一个极大值可以后移一位，选择 作为极大值，总操作变为 。此时，极值序列为 ，同理，倒数第二个极大值也可以后移一位。依此类推，直到第一个极大值后移，极值序列变为 。倒序遍历数组统计所有情况的答案即可。

#include <bits/stdc++.h>

using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (auto &x : a) scanf("%d", &x);
    long long sum = 0, ans = 0;
    auto f = [&](int i) { return max(0, max(a[i - 1], a[i + 1]) + 1 - a[i]); };
    for (int i = 1; i < n; i += 2)
        sum += f(i);
    ans = sum;
    if (n % 2 == 0) {
        for (int i = n - 2; i; i -= 2)
            sum += f(i) - f(i - 1), ans = min(ans, sum);
    }
    printf("%lld\n", ans);
    return 0;
}

T3

给定一个 矩阵 ，表示烟花点燃的状态。如果一个位置及其上下左右的烟花都点燃了，则该位置从当前时刻开始往后的每一秒都会释放 个烟花。每一秒已点燃的烟花将四周的烟花点燃。问总释放的烟花数量大于等于 的最短时间。

• 定义 表示： 及其上下左右是否都是 ；
• 记 和 分别表示当前的 的数量和当前的时间；
• 如果 ，则 会在 秒释放 个烟花；否则如果 ，则 会在 秒将四周的烟花点燃，即在 秒一定有 ，故 会在 秒释放 1 个烟花。
• 按时间 依次处理，先统计当前时刻被点燃的烟花中新增的 的数量，再统计累计烟花释放数量 ，如果 ，则 即为所求；对于其余的烟花，它们会在 秒释放烟花，统计贡献，然后向四周扩展，记录 秒被点燃的烟花；滚动数组模拟这个过程即可。
• 如果最后 ，则答案为 。

#include <bits/stdc++.h>

using namespace std;
int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vector<string> a(n, string(m, 0));
    for (auto &s : a) scanf("%s", s.data());
    auto check = [&](int i, int j) {
        int f = a[i][j] == '1';
        if (i > 0) f &= a[i - 1][j] == '1';
        if (i < n - 1) f &= a[i + 1][j] == '1';
        if (j > 0) f &= a[i][j - 1] == '1';
        if (j < m - 1) f &= a[i][j + 1] == '1';
        return f;
    };
    int cnt = 0, sum = 0, T = 0;
    vector<pair<int, int>> p, q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] == '1')
                q.push_back({i, j});
    constexpr int dx[] = {0, 0, 1, -1};
    constexpr int dy[] = {1, -1, 0, 0};
    for (; !q.empty(); swap(p, q), p.clear()) {
        for (int i = 0; i < q.size(); ++i) {
            auto [x, y] = q[i];
            if (check(x, y)) ++cnt, swap(q[i], q.back()), q.pop_back(), --i;
        }
        sum += cnt, ++T;
        if (sum >= k)
            break;
        cnt += q.size();
        for (auto [i, j] : q)
            for (int d = 0; d < 4; ++d) {
                int x = i + dx[d], y = j + dy[d];
                if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == '0') {
                    a[x][y] = '1';
                    p.push_back({x, y});
                }
            }
    }
    if (sum < k) T += (k - sum + cnt - 1) / cnt;
    printf("%d\n", T);
    return 0;
}

实际上这题数据非常水，不按时间依次处理直接 BFS 都能过。提供几个 Hack 数据：

3 4 12
0100
1001
0100
2

3 4 13
0100
1001
0100
3