---

Z0000 冒险家协会（分支结构）

题意

给定整数 $k$（$0 \le k \le 100$），按区间输出档位：

区间	输出
$k < 20$	$0$
$20 \le k < 40$	$1$
$40 \le k < 60$	$2$
$60 \le k < 80$	$3$
$80 \le k < 100$	$4$
$k = 100$	$5$

解析

这是一道多路分支题。依次判断 $k$ 落在哪个区间即可。

两个易错点：

1. 区间是左闭右开。写成 if (k < 20) ... else if (k < 40) ... 时，后面的判断天然继承了前面的下界，不必重复写 k >= 20。
2. $k = 100$ 是单独一档，不能并入 $[80,100)$。若写成 else 输出 $5$，也能覆盖 $k=100$（因为前面已排除 $k<100$），但要注意此时 $k=100$ 只会在最后一个 else 里出现。

也可以换个角度：阈值共 $5$ 个 $\{20,40,60,80,100\}$，答案就是其中 $\le k$ 的个数——当 $k=100$ 时五个阈值都满足，恰好得 $5$，说明这个角度同样正确。本题数据包含 $k=0,19,20,\dots,100$ 等全部边界。

复杂度 $O(1)$，空间 $O(1)$。

标程

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

int main()
{
    int k;
    cin >> k;
    if (k < 20)
    {
        cout << 0;
    }
    else if (k < 40)
    {
        cout << 1;
    }
    else if (k < 60)
    {
        cout << 2;
    }
    else if (k < 80)
    {
        cout << 3;
    }
    else if (k < 100)
    {
        cout << 4;
    }
    else
    {
        cout << 5;
    }
    return 0;
}

---

Z0001 自律机关（整除与取模）

题意

测试轨道长 $N$ 米，机关从起点每秒前进一次：第 $1,3,5,\dots$ 秒走 $A$ 米，第 $2,4,6,\dots$ 秒走 $B$ 米。累计前进达到 $N$ 米即到终点，求最少需要的秒数。

解析

把相邻两秒看作一个周期：一个周期前进 $A+B$ 米，耗时 $2$ 秒。

设 $d=\left\lfloor \dfrac{N}{A+B}\right\rfloor$，$r=N\bmod (A+B)$。

• 前 $d$ 个完整周期前进 $d(A+B)$ 米，耗时 $2d$ 秒；
• 若 $r=0$，恰好到达，答案为 $2d$；
• 否则还差 $r$ 米：第 $2d+1$ 秒再走 $A$ 米，若 $r\le A$ 则到达，答案为 $2d+1$；否则第 $2d+2$ 秒再走 $B$ 米，答案为 $2d+2$。

也可以逐秒模拟，交替累加 $A$ 和 $B$，直到累计距离达到 $N$。模拟耗时 $O(T)$，其中 $T$ 为答案，且 $T\le N$；本题允许模拟解通过。上面的周期公式只需 $O(1)$ 时间，效率更高。

注意：$A+B$ 最大为 $2\times10^9$，仍小于 $2^{31}-1$。由于 $A,B$ 都至少为 $1$，机关最晚在 $N$ 秒后到达，所以实际答案不超过 $N\le10^9$；各中间量和实际输出均可用 int 存储，标准程序即用 int。

复杂度 $O(1)$，空间 $O(1)$。

标程

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

int n, a, b, d, r, ans;

int main()
{
    cin >> n >> a >> b;
    d = n / (a + b);
    r = n % (a + b);
    ans = d * 2;
    if (r == 0)
    {
        cout << ans;
    }
    else if (r <= a)
    {
        cout << ans + 1;
    }
    else
    {
        cout << ans + 2;
    }
    return 0;
}

Z0002 天衡山石塔（循环与一维数组）

题意

从左到右给出 $N$ 座塔的高度 $h_i$。从最右端向左看，一座塔若右侧存在高度不低于它的塔就被挡住，否则可见。求可见塔数。

解析

从右向左扫描，维护「右侧已经出现过的最大高度」$mx$。当前塔 $h_i$ 能看见，当且仅当它严格高于右侧所有塔，即 $h_i > mx$。

• 看见时：答案加一，并把 $mx$ 更新为 $h_i$；
• 被挡住时不做任何事。

为什么是严格大于：题面说「不低于它」即遮挡，所以等于 $mx$ 的塔也会被挡住，只有严格大于才可见。若写成 h[i] >= mx 会把与最高塔等高的塔多算一次。

也可以写 $O(N^2)$ 暴力：对每座塔检查其右侧是否全部更矮。子任务 1 的 $N \le 1000$ 允许暴力；子任务 2 的 $N \le 3\times10^5$ 必须用 $O(N)$ 扫描，数据中特意放了严格递减序列，会让带提前退出的暴力退化为 $O(N^2)$ 而超时。

高度不超过 $10^9$，答案不超过 $N$，都在 int 范围内。

复杂度 $O(N)$，空间 $O(N)$。

标程

#include <bits/stdc++.h>
using namespace std;
int n, h[300005];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    int ans = 0, mx = 0;
    for (int i = n; i >= 1; i--)
    {
        if (h[i] > mx)
        {
            ans++;
            mx = h[i];
        }
    }
    cout << ans << endl;
    return 0;
}

---

Z0003 岩渊裂变（数位分离与 long long）

题意

对正整数 $n$（$10 \le n \le 10^{18}$）反复操作：设 $a$ 为最高位数字，$b$ 为去掉最高位后剩余低位组成的数，把 $n$ 变成 $|b-a|$，直到 $n$ 是一位数。输出最终结果。

解析

核心是数位分离：取出最高位和去掉最高位后的低位。

• 用 while (t >= 10) { p *= 10; t /= 10; } 求出最高位所在的位权 $p$ 和最高位数字 t；
• 最高位即 high = t，低位组成的数即 low = n % p；
• 令 n = abs(low - high)。

因为 $n$ 最大到 $10^{18}$，必须使用 long long，否则读入就会溢出。子任务 1/2 的 $n \le 10^9$ 用 int 也能过（$10^9 < 2^{31}$），但子任务 3 的 $10^{18}$ 只有 long long 存得下——数据里有 10 个点超过 $10^9$，专门卡这个问题。

边界：$n$ 恰为 $10$ 的幂（如 $1000$）时 low = 0，得 $|0-1|=1$，与样例一致。

设当前最高位位权为 $p$（$p \ge 10$）。最高位 $a \in [1,9]$，低位 $b \in [0,p-1]$，故 $|b-a| \le p-1$，一次操作后数值至少减少一位。若原数有 $D$ 位，至多执行 $D-1$ 次；每次数位分离耗时 $O(D)$，总时间 $O(D^2)$，额外空间 $O(1)$。最大输入 $10^{18}$ 为 $19$ 位，位权最大取到 $10^{18}$（不会乘到 $10^{19}$），所有中间量与差的绝对值都在 long long 范围内。

标程

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

int main()
{
    long long n;
    cin >> n;

    while (n >= 10)
    {
        long long t = n;
        long long p = 1;
        while (t >= 10)
        {
            p *= 10;
            t /= 10;
        }

        long long high = t;
        long long low = n % p;
        n = abs(low - high);
    }

    cout << n;
    return 0;
}

---

Z0004 教令院书页（字符串与计数数组）

题意

给出 $n$ 个小写字符串。对每个字母 a 到 z，求它在每一串中出现的次数的最小值 $m$，然后按字典序把该字母输出 $m$ 次，拼成一个字符串。

解析

对每个字母维护一个「到目前为止所有串中出现次数的最小值」ans[26]：

1. 初始化 ans[j] 为一个足够大的值（本题串长 $\le 50$，初值取 $100$ 即可）；
2. 逐串读入，先用 cnt[26] 统计该串中每个字母的出现次数（每串开始前清零）；
3. 对每个字母执行 ans[j] = min(ans[j], cnt[j])；
4. 最后按 a 到 z 输出 ans[j] 遍。

易错点：ans 的初值不能是 $0$，否则最小值永远是 $0$，公共字母恒为空。此外计数数组必须每串重置，否则会累加成「总和」而不是「最小值」。

若某字母在任意一串中没有出现，ans 会变成 $0$，自然不输出；若所有字母都是 $0$，则输出一个空行。

复杂度 $O(\text{总字符数} + 26n)$，空间 $O(26)$。

标程

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

int ans[26];
int cnt[26];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < 26; i++)
    {
        ans[i] = 100;
    }

    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        memset(cnt, 0, sizeof(cnt));
        for (int j = 0; j < (int)s.size(); j++)
        {
            cnt[s[j] - 'a']++;
        }
        for (int j = 0; j < 26; j++)
        {
            ans[j] = min(ans[j], cnt[j]);
        }
    }

    for (int i = 0; i < 26; i++)
    {
        for (int j = 1; j <= ans[i]; j++)
        {
            cout << (char)('a' + i);
        }
    }
    cout << '\n';
    return 0;
}

---

Z0005 神里织锦（二维数组与模拟）

题意

一块 $100 \times 100$ 的方格画板。给出 $N$ 张 $10 \times 10$ 正方形彩纸的左下角坐标 $(x,y)$（$0 \le x,y \le 90$）。彩纸可重叠，求被覆盖的格子总数，重叠只算一次。

解析

用布尔二维数组 vis[100][100] 标记每个格子是否被覆盖：

1. 每读入一张彩纸，把它覆盖的 $100$ 个格子（dx, dy 从 $0$ 到 $9$）置为 true；
2. 全部贴完后统计 vis 中 true 的个数。

因为 $x,y \le 90$，所以 $x+9 \le 99$，贴纸一定在画板内，不会越界。

这个做法天然处理重叠：同一格子被多张贴纸覆盖时，仍然只被标记一次，最后只统计一次。子任务 1 的 $N \le 5$ 且互不重叠，直接输出 $100N$ 也对；子任务 2 有重叠，必须用标记或等价方法去重。

坐标范围小，复杂度 $O(100N + 10000)$，空间 $O(10000)$。

标程

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

bool vis[101][101];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        for (int dx = 0; dx < 10; dx++)
        {
            for (int dy = 0; dy < 10; dy++)
            {
                vis[x + dx][y + dy] = true;
            }
        }
    }

    // 每个格子只统计一次，自动处理贴纸重叠。
    int ans = 0;
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            ans += vis[i][j];
        }
    }
    cout << ans;
    return 0;
}

---

Z0006 天空岛试炼（找规律与计数）

题意

有 $n$ 行 $m$ 列的棋盘，左上角为 $(1,1)$。第 $0$ 秒时，除 $(1,1)$ 外每格长出一枚金币。此后每一秒，一个格子继续长出金币，当且仅当它自己和**上下左右四个相邻格（在棋盘内）**在上一秒都长出了金币；否则不再生长。过程持续到没有格子再生长。求恰好长出 $x$ 枚金币的格子数。

解析

先在一块小棋盘上逐秒模拟，找规律。下面以 $3\times4$ 为例，记每个格子已经长出的金币数。

第 $0$ 秒，除 $(1,1)$ 外都长出 $1$ 枚：

0 1 1 1
1 1 1 1
1 1 1 1

第 $1$ 秒，一个格子要继续生长，必须它自己以及棋盘内的上、下、左、右邻居上一秒都生长过。只有紧挨着从不生长的 $(1,1)$ 的 $(1,2)$、$(2,1)$ 停了下来，其余继续：

0 1 2 2
1 2 2 2
2 2 2 2

继续逐秒模拟到不再变化，最终每个格子的金币数是：

0 1 2 3
1 2 3 4
2 3 4 5

观察这张表：第 $i$ 行第 $j$ 列恰好是 $(i-1)+(j-1)$，也就是它到 $(1,1)$ 的曼哈顿距离。

为什么是这个规律：记 $d=i+j-2$。第 $0$ 秒恰好是所有 $d>0$ 的格子生长。设「第 $t$ 秒生长 $\iff d>t$」。对 $d>0$ 的格子，它在棋盘内至少有上方或左方邻居，距离为 $d-1$；其余棋盘内邻居的距离只可能是 $d-1$ 或 $d+1$。于是它连同全部棋盘内邻居在第 $t$ 秒都生长，当且仅当 $d-1>t$，即 $d>t+1$，归纳成立。所以距离为 $d$ 的格子在第 $0,1,\dots,d-1$ 秒各生长一次，共 $d=(i-1)+(j-1)$ 枚金币。（单行、单列同理；$1\times1$ 只有起点，任何合法 $x$ 的答案都是 $0$。）

于是问题变成：统计满足 $(i-1)+(j-1)=x$、$1\le i\le n$、$1\le j\le m$ 的格子数。令 $A=i-1\in[0,n-1]$、$B=j-1\in[0,m-1]$，即数 $A+B=x$ 的解。固定 $A$ 得 $B=x-A$，要求 $0\le B\le m-1$，即

$$\max(0,\,x-(m-1))\le A\le\min(n-1,\,x).$$

所以答案为 $\max\bigl(0,\ \min(n-1,x)-\max(0,x-m+1)+1\bigr)$；当 $x$ 超出可达范围（如 $x>n+m-2$）时区间为空，答案为 $0$。

复杂度 $O(1)$，空间 $O(1)$。

标程

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

int main()
{
	int n, m, x;
	cin >> n >> m >> x;
	int l = max(0, x - m + 1);
	int r = min(n - 1, x);
	cout << max(0, r - l + 1);
	return 0;
}

---

Z0007 计时塔（分支结构与边界）

题意

给出两个 24 小时制时刻，求闭区间内的整点个数。若结束时刻早于开始时刻，则结束时刻视为第二天。

解析

先把两个时刻都换算成从当天 00:00 起的分钟数：$a=60h_1+m_1$，$b=60h_2+m_2$。若 $b<a$，说明跨到了第二天，令 $b\leftarrow b+1440$。

整点发生在每个小时的 :00。从开始时刻所在的小时之后到结束时刻所在的小时，每到一条整点边界就响一次，因此先算 $\left\lfloor b/60\right\rfloor-\left\lfloor a/60\right\rfloor$。若开始时刻本身就落在整点（即 $m_1=0$），它也应计入，再加 $1$。

$$\text{ans}=\left\lfloor \frac{b}{60}\right\rfloor-\left\lfloor \frac{a}{60}\right\rfloor+[\,m_1=0\,] $$

这样做没有遗漏也没有重复：区间内的每个整点，要么就是开始时刻本身（仅当 $m_1=0$），要么对应从开始到结束之间跨过的某条整小时边界，而两者被分别记为 $[\,m_1=0\,]$ 和差值两部分。

样例 1 跨过午夜后有两个整点；样例 2 补计起点；样例 3 间隔接近一天，仍至多 $24$ 次。

复杂度 $O(1)$，额外空间 $O(1)$。

标程

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

int main() {
    int h1, m1, h2, m2;
    cin >> h1 >> m1 >> h2 >> m2;
    int a = h1 * 60 + m1, b = h2 * 60 + m2;
    if (b < a) b += 1440;
    cout << b / 60 - a / 60 + (m1 == 0) << '\n';
    return 0;
}

---

Z0008 榜单（循环与最值维护）

题意

每加入一个正整数，输出当前前缀中按份数计的第二大和严格小于最大值的最大值，缺失时为 $0$。

解析

子任务 1 中分数互不相同，第二大与严格第二大相等，只需维护最大的两个数。完整任务还要注意最高分可能重复：此时按份数计的第二大等于最高分，但严格第二大仍是另一个更小的数。

维护三个量：

• mx：当前最大值；
• cnt：当前最大值出现的次数；
• sec：当前严格第二大，不存在时为 $0$。

读到 $x$ 时按三种情况更新：

• $x>mx$：原来的 mx 退化为 sec，令 sec = mx、mx = x、cnt = 1；
• $x=mx$：只是最大值又多了一份，cnt++；
• $x<mx$：它只可能刷新 sec，令 sec = max(sec, x)。

这样三个量在每次读入后都准确描述当前前缀的状态。输出时，若 cnt >= 2，按份数计的第二大就是 mx，否则为 sec；严格第二大始终是 sec。

例如 $9,9,10$ 的第三步，旧最大值 $9$ 成为严格第二大；样例 2 全相等时严格第二大始终不存在。

复杂度 $O(n)$，额外空间 $O(1)$，分数与计数都在 int 范围内。

标程

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, mx = 0, sec = 0, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x > mx) {
            sec = mx;
            mx = x;
            cnt = 1;
        } else if (x == mx) {
            cnt++;
        } else {
            sec = max(sec, x);
        }
        cout << (cnt >= 2 ? mx : sec) << ' ' << sec << '\n';
    }
    return 0;
}

---

Z0009 解码（字符串与贪心）

题意

轨道上有 $N$ 个位置，每个位置是一辆矿车 P 或一块煤 H。每辆矿车至多领取一块距离不超过 $K$ 的煤，每块煤至多给一辆矿车。求最多能领到煤的矿车数。

解析

子任务 1 的 $N\le 20$，可以暴力：对每辆矿车枚举左右各 $K$ 格，找到第一块还没被用过的煤就匹配。完整范围 $N\le 2\times10^4$ 时，若每辆矿车都从头再扫一遍左右 $K$ 格，重复扫描会变慢，需要用一个指针记住「最靠左的、还没被领走的煤」。

贪心做法：从左到右扫描矿车，维护一个指针 j 指向当前最靠左的、尚未被领取的煤的位置（初始为 $0$）。

• 遇到煤就跳过；
• 遇到位置 $i$ 的矿车时，先把 j 更新为 $\max(j,\ i-K)$（它够不到的更靠左的煤不再可能被后面任何一辆矿车用到），再从 j 开始向右扫到 $\min(N-1,\ i+K)$；找到第一块煤就领取并让 j 右移一位。

为什么这样贪心是对的：把每辆矿车和它能领的煤看成一段长度为 $2K+1$ 的区间。按从左到右处理矿车时，当前矿车与它右边所有矿车相比，能用的煤都在更靠左的位置，因此「能领就领最左边那块」不会挤占后面矿车的更优选择——任何一份把当前矿车配给更靠右的煤的方案，都可以交换成配给最靠左的可用煤而不减少匹配数。这正是区间匹配的标准贪心。

复杂度：j 只会单向右移，所有矿车合起来扫描的区间总长为 $O(N)$（算上每辆车定位起点的一次比较），时间 $O(N)$；空间 $O(N)$ 存字符串。

标程

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    int ans = 0, j = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'H')
        {
            continue;
        }
        j = max(j, i - k);
        while (j <= min(n - 1, i + k))
        {
            if (s[j] == 'H')
            {
                ans++;
                j++;
                break;
            }
            j++;
        }
    }
    cout << ans << endl;
    return 0;
}

---

Z0010 红石分拣（数组与逆序对计数）

题意

用「交换相邻两辆矿车」这一种操作，使所有偶数编号的矿车都排到奇数编号前面，求最少交换次数。

解析

只看每辆矿车的奇偶性：目标是把所有偶数放到所有奇数前面。一个偶数 $a_i$ 最终必须跨过它左边的每一个奇数；反之，两个同奇偶的矿车之间永远不需要交换。因此最少交换次数就等于「所有偶数左侧的奇数个数之和」：

$$\text{ans}=\sum_{\substack{1\le i\le n\\ a_i\text{ 为偶数}}}\Bigl|\{\,j<i: a_j\text{ 为奇数}\,\}\Bigr| $$

这个下界可以达到：每次相邻交换可以消除一对「奇数在左、偶数在右」的相邻逆序对，而不增加其他逆序对，按此反复交换恰好用这么多步。

扫描一遍即可：维护 cnt 表示已经遇到的奇数个数。读到偶数时，它左侧的奇数正好是 cnt 个，令 ans += cnt；读到奇数时 cnt++。

子任务 1 的 $n\le 1000$ 可以直接模拟冒泡过程得到同样答案；完整范围 $n\le 10^5$ 用上面的计数法，时间 $O(n)$。

注意：当数组是「大量奇数在前、大量偶数在后」时，答案会接近 $\frac{n^2}{4}$（例如 $n=10^5$ 时约 $2.5\times10^9$），超过了 int 的范围，必须用 long long。正式数据中有多个这样的测试点专门卡 int。

复杂度 $O(n)$，额外空间 $O(1)$。

标程

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

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x % 2 == 0)
        {
            ans += cnt;
        }
        else
        {
            cnt++;
        }
    }
    cout << ans;
    return 0;
}

---

Z0011 礼包交易（数学与分类讨论）

题意

只用面额 $5$ 和 $8$，在总额不超过 $n$ 的前提下，求最多能花出的金额，输出 $n$ 减去它。

解析

子任务 1 的 $n\le 100$ 可以暴力：枚举买了 $x$ 个 $5$ 颗礼包、$y$ 个 $8$ 颗礼包，在 $5x+8y\le n$ 下取最大的 $5x+8y$。完整范围 $n\le 10^9$ 显然不能枚举。

关键在于观察较大的数能否凑出：

$$28=5\times4+8,\quad 29=5\times1+8\times3,\quad 30=5\times6,\quad 31=5\times3+8\times2,\quad 32=8\times4 $$

$28,29,30,31,32$ 这连续的 $5$ 个数都能凑出。之后只要在某个能凑出的数上再加一个 $5$ 就能得到下一个能凑出的数，所以所有 $n\ge 28$ 的整数都能恰好花完，答案都是 $0$。而 $n<28$ 时只有有限种组合，直接枚举即可。

因此实现只需：若 $n\ge 28$ 输出 $0$，否则在小范围内枚举 $x,y$ 求最大花费。

复杂度：$n\ge 28$ 时 $O(1)$；$n<28$ 时枚举量是常数，整体 $O(1)$，额外空间 $O(1)$。

标程

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

int main()
{
    int n;
    cin >> n;
    if (n >= 28)
    {
        cout << 0;
        return 0;
    }
    int best = 0;
    for (int x = 0; x * 5 <= n; x++)
    {
        for (int y = 0; x * 5 + y * 8 <= n; y++)
        {
            best = max(best, x * 5 + y * 8);
        }
    }
    cout << n - best;
    return 0;
}

---

Z0012 能量环流（二分答案）

题意

$n$ 台发生器在时刻 $0$ 同时启动，第 $i$ 台每 $a_i$ 分钟产出 $1$ 单位能量。求最早的 $t$，使累计产量不少于 $k$。

解析

时刻 $t$ 的累计产量是

$$S(t)=\sum_{i=1}^{n}\left\lfloor \frac{t}{a_i}\right\rfloor $$

$S(t)$ 随 $t$ 单调不降：$t$ 变大，每一台的产量 $\lfloor t/a_i\rfloor$ 都不会减少。因此「$S(t)\ge k$ 是否成立」关于 $t$ 是单调的，可以二分答案。

二分区间取 $[0,10^{18}]$（题面保证答案不超过 $10^{18}$）。每次取中点 mid，逐台累加 $\lfloor mid/a_i\rfloor$；一旦达到 $k$ 就提前退出。若 $S(mid)\ge k$，说明答案 $\le mid$，收缩右界；否则答案 $>mid$，收缩左界。循环结束时左界即最小可行时刻。

溢出说明：累加时一旦 sum >= k 就立即退出，所以 sum 在退出前至多为 $(k-1)$ 加上本次的 $\lfloor mid/a_i\rfloor \le 10^{18}$，不超过 $2\times10^{18} < \text{LLONG\_MAX}$，用 long long 安全。

子任务 1 的规模很小，也可以从 $t=0$ 起逐分钟累加直到达标；完整范围答案可达 $10^{18}$，必须二分。

复杂度 $O(n\log 10^{18})$，空间 $O(n)$。

标程

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

ll a[100005];

int main() {
    ll n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    ll lo = 0, hi = (ll)1e18;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            sum += mid / a[i];
            if (sum >= k) break;
        }
        if (sum >= k) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

---

Z0013 最短航线（BFS 与分层图）

题意

$n\times m$ 的网格，每格有一个传送阵编号。从起点到终点，走到相邻格花费 $1$ 金币，使用同编号传送阵花费 $0$ 金币但会消耗一次传送机会，最多传送 $k$ 次。求最少金币。

解析

这是边权只有 $0$ 和 $1$ 的最短路问题：走路是权 $1$ 的边，传送是权 $0$ 的边。又因为传送次数有限，需要把状态扩展成 $(x,y,t)$，表示「已经使用了 $t$ 次传送、当前在 $(x,y)$」时的最小金币花费，$t\in[0,k]$。

• 走路：$(x,y,t)\to(x',y',t)$，权重 $1$；
• 传送：$(x,y,t)\to(\text{所有同编号格},t+1)$，权重 $0$。

对 $0/1$ 边权的图用双端队列 BFS：遇到权 $0$ 的边把新状态压到队首，权 $1$ 的边压到队尾，就能保证按花费从小到大处理。

关键优化：传送时不必每到一个格子都把同编号的格子全部再扩展一遍。若当前编号为 $c$，在「已用 $t$ 次传送」这一层里，编号 $c$ 只需要扩展一次。因为双端队列 BFS 是按花费非降弹出的，第一次遇到编号 $c$、层数 $t$ 的状态，一定是这些格子中花费最小的，之后再从别的同编号格子扩展只会得到不更优的花费。于是用 vis[c][t] 记录「编号 $c$ 在第 $t$ 层是否已扩展过」，每个 $(\text{编号},t)$ 组合只做一次批量扩展。不这样优化时，每次传送都要重扫整组，最坏复杂度会退化到无法接受——这也是子任务 1（小网格）与完整范围的区别：小网格随便暴力能过，大网格必须优化。

答案取 $\min_{0\le t\le k} dp[x_2][y_2][t]$。

复杂度：每个状态最多入队常数次；传送的批量扩展总量为「每个编号每层一次，合计 $O(nm)$」，乘上 $k$ 层，整体约 $O(nmk)$。空间 $O(nmk)$。

标程

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

const int INF = 1 << 29;
int n, m, K;
int num[1005][1005];
bool vis[1005][6];
int dp[1005][1005][6];
vector<pair<int, int>> grp[1005];
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int main() {
    scanf("%d %d %d", &n, &m, &K);
    int sx, sy, tx, ty;
    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &num[i][j]);
            grp[num[i][j]].push_back({i, j});
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int t = 0; t <= K; t++) dp[i][j][t] = INF;
    dp[sx][sy][0] = 0;

    deque<array<int, 3>> dq;
    dq.push_back({sx, sy, 0});
    while (!dq.empty()) {
        array<int, 3> cur = dq.front();
        dq.pop_front();
        int x = cur[0], y = cur[1], t = cur[2], d = dp[x][y][t];
        int c = num[x][y];

        // 传送：编号 c 在第 t 层只需扩展一次（0-1 BFS 中首次弹出即为最小花费）
        if (t < K && !vis[c][t]) {
            vis[c][t] = true;
            for (auto &p : grp[c]) {
                int nx = p.first, ny = p.second;
                if (d < dp[nx][ny][t + 1]) {
                    dp[nx][ny][t + 1] = d;
                    dq.push_front({nx, ny, t + 1});
                }
            }
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (d + 1 < dp[nx][ny][t]) {
                dp[nx][ny][t] = d + 1;
                dq.push_back({nx, ny, t});
            }
        }
    }

    int ans = INF;
    for (int t = 0; t <= K; t++) ans = min(ans, dp[tx][ty][t]);
    printf("%d\n", ans);
    return 0;
}