[CSP-J 2023] 小苹果

题目描述

小 Y 的桌子上放着 $n$ 个苹果从左到右排成一列，编号为从 $1$ 到 $n$。

小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。

每天在拿的时候，小苞都是从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道，多少天能拿完所有的苹果，而编号为 $n$ 的苹果是在第几天被拿走的？

输入格式

输入的第一行包含一个正整数 $n$，表示苹果的总数。

输出格式

输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为 $n$ 的苹果是在第几天。

样例 #1

样例输入 #1

8

样例输出 #1

5 5

提示

【样例 $1$ 解释】

小苞的桌上一共放了 $8$ 个苹果。
小苞第一天拿走了编号为 $1$、$4$、$7$ 的苹果。
小苞第二天拿走了编号为 $2$、$6$ 的苹果。
小苞第三天拿走了编号为 $3$ 的苹果。
小苞第四天拿走了编号为 $5$ 的苹果。
小苞第五天拿走了编号为 $8$ 的苹果。

【样例 $2$】

见选手目录下的 apple/apple2.in 与 apple/apple2.ans。

【数据范围】

对于所有测试数据有：$1\leq n\leq 10^9$。

测试点	$n\leq$	特殊性质
$1\sim 2$	$10$	无
$3\sim 5$	$10^3$	无
$6\sim 7$	$10^6$	有
$8\sim 9$	$10^6$	无
$10$	$10^9$	无

特殊性质：小苞第一天就取走编号为 $n$ 的苹果。

解析

题目描述

有 $n$ 个苹果手机排成一排，编号为 1 到 n。每天从最左边的第 1 个苹果手机开始，每隔 2 个拿一个苹果手机，拿完后将剩下的苹果手机重新排成一排。我们需要求解以下问题：

1. 多少天能拿完所有苹果手机？
2. 第 $n$ 个苹果手机是在第几天被拿走的？

解决方案

我们可以将“每隔 2 个拿一个苹果手机”理解为：将苹果手机每 3 个分为一组，每次取该组的第一个苹果手机。例如，对于有 11 个苹果手机的情况：

苹果手机编号	1	2	3	4	5	6	7	8	9	10	11
取走情况	取			取			取			取	取

标红的表示在这一轮被拿走的苹果手机。若剩余的苹果手机不足以构成完整的 3 个一组，则按不完整的一组来处理。

思路 1：求天数

每一轮取走的苹果手机数量等于分成的组数，即 $\lceil \frac{n}{3} \rceil$。我们通过暴力模拟，逐轮计算，将 $n$ 减去 $\lceil \frac{n}{3} \rceil$，直到 $n = 0$，操作的次数即为天数。

思路 2：第 n 个苹果手机的取走时间

最后一个苹果手机必然是在最后一组中。若要取走它，相当于该苹果手机处于最后一组的第一个。例如，对于 11 和 10 个苹果手机的情况：

• $n = 11$ 时，最后一个苹果手机编号为 11，且它位于最后一组的第一个；
• $n = 10$ 时，最后一个苹果手机编号为 10，但它不是这一组的第一个，故不在该轮被取走。

可以发现，当 n \mod 3 = 1 时，最后一个苹果手机是在该轮被取走的。因此，我们在暴力模拟中判断当前的 $n$ 是否满足 n \mod 3 = 1，若满足，则记录该轮数作为答案。

注意：我们只记录第一次出现 n \mod 3 = 1 的轮数，后续若有再出现则不再记录。

时间复杂度分析

每次操作将 $n$ 减去 $\lceil \frac{n}{3} \rceil$，大约相当于 $n \leftarrow \frac{2}{3}n$，可以近似认为每次将 $n$ 缩小一半。因此，时间复杂度为 $\Theta(\log_2 n)$，实际运行时可能会稍高一些。

代码实现

#include <iostream>
#include <cmath> 

using namespace std;

int n, res1, res2;

int main() {
    freopen("apple.in", "r", stdin);  // 重定向输入文件
    freopen("apple.out", "w", stdout);  // 重定向输出文件
    
    cin >> n;  // 读取苹果手机的数量
    
    for (int i = 1;; ++i) {
        if (n == 0) break;  // 当苹果手机数量为 0 时，停止
        if (!res2 && n % 3 == 1) res2 = i;  // 记录第一次 n % 3 == 1 的轮数
        n -= ceil(n / 3.0);  // 每轮取走的苹果数量
        ++res1;  // 记录天数
    }
    
    cout << res1 << ' ' << res2 << '\n';  // 输出答案
    
    return 0;  
}

代码解析

1. 输入输出重定向：通过 freopen 函数实现从文件中读取输入并将输出写入文件。
2. 输入 n：表示苹果手机的数量。
3. 主循环：
   • 每一轮循环中，将苹果手机数量按规则减少。
   • 在第一次满足 n \mod 3 = 1 时，记录当前的轮数。
4. 结果输出：输出总共的天数 res1 以及第 $n$ 个苹果手机被取走的轮数 res2。

[CSP-J 2023] 公路

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i + 1$ 的距离为 $v_i$ 公里。

公路上每个站点都可以加油，编号为 $i$ 的站点一升油的价格为 $a_i$ 元，且每个站点只出售整数升的油。

小苞想从站点 $1$ 开车到站点 $n$，一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 $d$ 公里。问小苞从站点 $1$ 开到站点 $n$，至少要花多少钱加油？

输入格式

输入的第一行包含两个正整数 $n$ 和 $d$，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 $n - 1$ 个正整数 $v_1, v_2... v_{n-1}$，分别表示站点间的距离。

输入的第三行包含 $n$ 个正整数 $a_1, a_2 ... a_n$，分别表示在不同站点加油的价格。

输出格式

输出一行，仅包含一个正整数，表示从站点 $1$ 开到站点 $n$，小苞至少要花多少钱加油。

样例 #1

样例输入 #1

5 4
10 10 10 10
9 8 9 6 5

样例输出 #1

79

提示

【样例 1 解释】

最优方案下：小苞在站点 $1$ 买了 $3$ 升油，在站点 $2$ 购买了 $5$ 升油，在站点 $4$ 购买了 $2$ 升油。

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

【数据范围】

对于所有测试数据保证：$1 \leq n \leq 10^5$，$1 \leq d \leq 10^5$，$1 \leq v_i \leq 10^5$，$1 \leq a_i \leq 10^5$。

测试点	$n \leq$	特殊性质
$1\sim 5$	$8$	无
$6\sim 10$	$10^3$	无
$11\sim 13$	$10^5$	A
$14\sim 16$	$10^5$	B
$17\sim 20$	$10^5$	无

• 特殊性质 A：站点 $1$ 的油价最低。
• 特殊性质 B：对于所有 $1 \leq i < n$，$v_i$ 为 $d$ 的倍数。

解析

反悔贪心思想

从左到右遍历每个加油站，当需要加油时，从之前经过的最便宜的加油站加油。这种策略确保每次加油的成本最小。

关键思路：

1. 维护变量 $f$：表示当前状态。

   • $f < 0$ 表示当前还剩下的油能行驶的公里数。
   • $f \geq 0$ 表示需要加油，加油量为 $\lceil \frac{s}{d} \rceil$，即需要加油来继续行驶。

2. 优化加油成本：当我们走到一个加油站时，回顾之前经过的加油站，选择加油费用最低的站点进行加油，以达到节省总费用的目的。

代码中的实现细节：

• 需要注意数据范围较大，因此所有涉及油量和费用的变量都需要使用 long long 类型。
• 时间复杂度为 $O(n)$，因为只需要遍历每个加油站一次。

代码实现

#include <bits/stdc++.h>  // 标准库的集合

using namespace std;  // 使用标准命名空间

using LL = long long;  // 定义 long long 类型的别名

const int N = 1e5 + 10;  // 定义最大数组长度

int v[N], a[N];  // v 用来存储距离，a 用来存储加油站的价格
int n, d;  // n 表示加油站数量，d 表示每次加油能走的距离

int main() {
    scanf("%d%d", &n, &d);  // 输入加油站数量和每次加油的最大行驶距离
    for (int i = 1; i < n; i++) scanf("%d", &v[i]);  // 输入各加油站间的距离
    int mi = INT_MAX;  // 初始化最小加油价格为最大整型值
    LL ans = 0, s = 0;  // ans 表示总费用，s 表示当前还需行驶的距离
    for (int i = 1; i < n; i++) {
        scanf("%d", &a[i]);  // 输入每个加油站的价格
        s += v[i];  // 累加当前需要行驶的距离
        mi = min(mi, a[i]);  // 更新到目前为止的最低加油价格
        if (s > 0) {  // 如果需要加油
            ans += (s + d - 1) / d * mi;  // 计算加油费用
            s -= (s + d - 1) / d * d;  // 减去已加油能够行驶的距离
        }
    }
    printf("%lld\n", ans);  // 输出总费用
    return 0;  // 结束程序
}

代码解析

1. 输入与初始化：首先读取加油站的数量 $n$ 和每次加油能够行驶的距离 $d$，然后初始化最小价格变量 $mi$ 和总费用 $ans$。

2. 距离与价格的计算：遍历每个加油站，计算累计需要行驶的距离 $s$ 并不断更新最小加油价格 $mi$。当需要加油时，根据当前行驶的距离和最小价格计算费用，并更新剩余的行驶距离。

3. 高效加油策略：通过这种贪心策略，每次都选择最便宜的加油站加油，确保总体费用最低。

总结

该方案利用贪心思想解决了最小化加油成本的问题。其核心在于通过回顾性选择，确保每次加油的费用尽可能低。

[CSP-J 2023] 一元二次方程

题目背景

众所周知，对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$，可以用以下方式求实数解：

• 计算 $\Delta = b ^ 2 - 4ac$，则:
  1. 若 $\Delta < 0$，则该一元二次方程无实数解。
  2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$。

例如：

• $x ^ 2 + x + 1 = 0$ 无实数解，因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$。
• $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x _ {1, 2} = 1$。
• $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x _ 1 = 1, x _ 2 = 2$。

在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。例如 $12$ 和 $18$ 的最大公因数是 $6$，即 $\gcd(12, 18) = 6$。

题目描述

现在给定一个一元二次方程的系数 $a, b, c$，其中 $a, b, c$ 均为整数且 $a \neq 0$。你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解，并按要求的格式输出。

在本题中输出有理数 $v$ 时须遵循以下规则：

• 由有理数的定义，存在唯一的两个整数 $p$ 和 $q$，满足 $q > 0$，$\gcd(p, q) = 1$ 且 $v = \frac pq$。

• 若 $q = 1$，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 $n$ 的值；

• 例如：

  • 当 $v = -0.5$ 时，$p$ 和 $q$ 的值分别为 $-1$ 和 $2$，则应输出 -1/2；
  • 当 $v = 0$ 时，$p$ 和 $q$ 的值分别为 $0$ 和 $1$，则应输出 0。

对于方程的求解，分两种情况讨论：

1. 若 $\Delta = b ^ 2 - 4ac < 0$，则表明方程无实数解，此时你应当输出 NO；

2. 否则 $\Delta \geq 0$，此时方程有两解（可能相等），记其中较大者为 $x$，则：

   1. 若 $x$ 为有理数，则按有理数的格式输出 $x$。

   2. 否则根据上文公式，$x$ 可以被唯一表示为 $x = q _ 1 + q _ 2 \sqrt r$ 的形式，其中：

      • $q _ 1, q _ 2$ 为有理数，且 $q _ 2 > 0$；
      • $r$ 为正整数且 $r > 1$，且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$（即 $r$ 不应是 $d ^ 2$ 的倍数）；

   此时：

   1. 若 $q _ 1 \neq 0$，则按有理数的格式输出 $q _ 1$，并再输出一个加号 +；
   2. 否则跳过这一步输出；

   随后：

   1. 若 $q _ 2 = 1$，则输出 sqrt({r})；
   2. 否则若 $q _ 2$ 为整数，则输出 {q2}*sqrt({r})；
   3. 否则若 $q _ 3 = \frac 1{q _ 2}$ 为整数，则输出 sqrt({r})/{q3}；
   4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$，此时输出 {c}*sqrt({r})/{d}；

   上述表示中 {n} 代表整数 {n} 的值，详见样例。

   如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 NO。

输入格式

输入的第一行包含两个正整数 $T, M$，分别表示方程数和系数的绝对值上限。

接下来 $T$ 行，每行包含三个整数 $a, b, c$。

输出格式

输出 $T$ 行，每行包含一个字符串，表示对应询问的答案，格式如题面所述。

每行输出的字符串中间不应包含任何空格。

样例 #1

样例输入 #1

9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

样例输出 #1

1
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

提示

【样例 #2】

见附件中的 uqe/uqe2.in 与 uqe/uqe2.ans。

【数据范围】

对于所有数据有：$1 \leq T \leq 5000$，$1 \leq M \leq 10 ^ 3$，$|a|,|b|,|c| \leq M$，$a \neq 0$。

测试点编号	$M \leq$	特殊性质 A	特殊性质 B	特殊性质 C
$1$	$1$	是	是	是
$2$	$20$	否	否	否
$3$	$10 ^ 3$	是	否	是
$4$	$10 ^ 3$	是	否	否
$5$	$10 ^ 3$	否	是	是
$6$	$10 ^ 3$	否	是	否
$7, 8$	$10 ^ 3$	否	否	是
$9, 10$	$10 ^ 3$	否	否	否

其中：

• 特殊性质 A：保证 $b = 0$；
• 特殊性质 B：保证 $c = 0$；
• 特殊性质 C：如果方程有解，那么方程的两个解都是整数。

解析

前置知识

我们需要了解解一元二次方程的基础知识。对于形如 $ax^2 + bx + c = 0$ 的一元二次方程（其中 $a \neq 0$），其根的求解公式为：

$x_{1, 2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

根据判别式 $\Delta = b^2 - 4ac$，可以讨论方程的实数解：

1. 当 $\Delta < 0$ 时，方程无实数解。
2. 当 $\Delta \geq 0$ 时，方程有两个实数解：

   $x_{1, 2} = \frac{-b \pm \sqrt{\Delta}}{2a}$

题目要求给出多个一元二次方程的较大实数解。

题目简述

给定 $T$ 组数据，每组数据包括 $a$、$b$、$c$ 三个系数，求解形如 $ax^2 + bx + c = 0$ 的一元二次方程的较大实数解。若方程无实数解，则输出 "NO"。

思路分析

这道题主要考查模拟计算以及如何处理输出中的数据化简、约分问题。

情况 1：当 $\Delta < 0$

当判别式 $\Delta = b^2 - 4ac$ 小于 0 时，方程无实数解，直接输出 "NO"。

情况 2：当 $\Delta \geq 0$

当 $\Delta \geq 0$ 时，方程有两个实数解。为了简化计算并避免正负号的麻烦，可以统一处理为 $a$ 取正，即：

if(a < 0) {
    a = -a;
    b = -b;
    c = -c;
}

方程的解为：

$x = \frac{-b + \sqrt{\Delta}}{2a}$

需要根据 $\Delta$ 的值进一步处理。

1. 当 $\Delta$ 是完全平方数：此时 $\sqrt{\Delta}$ 是有理数，较大实数解为：

   $x = \frac{-b + \sqrt{\Delta}}{2a}$

   此时只需将分子 $-b + \sqrt{\Delta}$ 和分母 $2a$ 进行约分并输出。

2. 当 $\Delta$ 不是完全平方数：此时 $\sqrt{\Delta}$ 为无理数。可将其表示为 $k\sqrt{t}$ 的形式，其中 $k$ 是最大的整数，使得 $\Delta = k^2 \times t$。于是较大实数解为：

   $x = \frac{-b}{2a} + \frac{k\sqrt{t}}{2a}$

   这部分需要将两个分数分别约分后再输出。

代码实现

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

// 读取输入
inline int read() {
    int x = 0, y = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
    return x * y;
}

// 求最大公因数
int gcd(int n, int m) {
    if (n % m == 0) return m;
    else return gcd(m, n % m);
}

// 约分
void YueFen(int &fenzi, int &fenmu) {
    bool f = (fenzi < 0 ? 1 : 0); // 负数处理
    if (f) fenzi *= -1;
    int k = gcd(fenzi, fenmu); // 约分
    fenzi /= k; 
    fenmu /= k;
    if (f) fenzi *= -1;
}

// 将 n 化为 k^2*t 的形式
int k, t;
void solve(int n) {
    for (int i = sqrt(n); i >= 1; i--) {
        int w = n / (i * i);
        if (w * i * i == n) {
            k = i;
            t = w;  // n = k^2 * t
            return;
        }
    }
}

int main() {
    //freopen("uqe.in", "r", stdin);
    //freopen("uqe.out", "w", stdout);
    int T = read(); // 读取测试数据组数
    for (int i = 1; i <= T; i++) {
        int a = read(), b = read(), c = read();
        int delta = b * b - 4 * a * c;
        
        if (delta < 0) {
            printf("NO\n");
            continue;
        }

        if (a < 0) a = -a, b = -b, c = -c;
        int sq = sqrt(delta);
        
        if (sq * sq == delta) { // 有理数情况
            int fenzi = -b + sq;
            int fenmu = 2 * a;
            YueFen(fenzi, fenmu);
            if (fenmu == 1) {
                printf("%d\n", fenzi);
            } else {
                printf("%d/%d\n", fenzi, fenmu);
            }
        } else { // 无理数情况
            solve(delta); // sqrt(delta) = k * sqrt(t)
            int fenzi = -b;
            int fenmu = 2 * a;
            YueFen(fenzi, fenmu);
            
            if (b != 0) {
                if (fenmu == 1) {
                    printf("%d", fenzi);
                } else {
                    printf("%d/%d", fenzi, fenmu);
                }
                printf("+");
            }

            fenzi = k;
            fenmu = 2 * a;
            YueFen(fenzi, fenmu);
            
            if (fenzi == 1 && fenmu == 1) {
                printf("sqrt(%d)", t);
            } else if (fenzi == 1) {
                printf("sqrt(%d)/%d", t, fenmu);
            } else if (fenmu == 1) {
                printf("%d*sqrt(%d)", fenzi, t);
            } else {
                printf("%d*sqrt(%d)/%d", fenzi, t, fenmu);
            }
            
            printf("\n");
        }
    }
    
    return 0;
}

代码详解

1. 输入函数 read：快速读取输入，适合大规模数据。
2. 最大公因数 gcd 函数：用于约分分子和分母。
3. YueFen 函数：负责对分数进行约分，处理负数情况。
4. solve 函数：将非完全平方数的 $\Delta$ 表示为 $k^2 \times t$ 的形式，方便后续处理。
5. 主函数 main：处理 $T$ 组测试数据，按不同情况输出较大解或 "NO"。

输出解释

• 当 $\Delta < 0$ 时，输出 "NO"。
• 当 $\Delta$ 是完全平方数时，输出约分后的较大解。
• 当 $\Delta$ 不是完全平方数时，输出无理数形式的较大解。

[CSP-J 2023] 旅游巴士

题目描述

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 $n$ 处地点，在这些地点之间连有 $m$ 条道路。其中 $1$ 号地点为景区入口，$n$ 号地点为景区出口。我们把一天当中景区开门营业的时间记为 $0$ 时刻，则从 $0$ 时刻起，每间隔 $k$ 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 $1$ 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 $k$ 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个 “开放时间”$a _ i$，游客只有不早于 $a _ i$ 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

输入格式

输入的第一行包含 3 个正整数 $n, m, k$，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 $m$ 行，每行包含 3 个非负整数 $u _ i, v _ i, a_ i$，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$，道路的“开放时间”为 $a _ i$。

输出格式

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

样例 #1

样例输入 #1

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

样例输出 #1

6

提示

【样例 #1 解释】

小 Z 可以在 $3$ 时刻到达景区入口，沿 $1 \to 3 \to 4 \to 5$ 的顺序走到景区出口，并在 $6$ 时刻离开。

【样例 #2】

见附件中的 bus/bus2.in 与 bus/bus2.ans。

【数据范围】

对于所有测试数据有：$2 \leq n \leq 10 ^ 4$，$1 \leq m \leq 2 \times 10 ^ 4$，$1 \leq k \leq 100$，$1 \leq u _ i, v _ i \leq n$，$0 \leq a _ i \leq 10 ^ 6$。

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a _ i = 0$
$3 \sim 5$	$10$	$15$	$100$	无
$6 \sim 7$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	$a _ i = 0$
$8 \sim 10$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	无
$11 \sim 13$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$a _ i = 0$
$14 \sim 15$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$u _ i \leq v _ i$
$16 \sim 20$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	无

解析

题目分析

给定一个带有边权的图，要求从起点到终点的最短路径，特别之处在于：

• 出发时刻和结束时刻都是 $k$ 的非负整数倍；
• 小 Z 不愿意在任何地点（包括景区入口、出口）或道路上停留，意味着当当前时间不满足要求时，必须将出发时间推迟至 $k$ 的整数倍。

本题看似不直接是经典的最短路问题，但可以通过边权为 1 的 BFS（广度优先搜索）进行求解，时间复杂度为 $O(n)$。然而，由于时间和路径数必须满足 $k$ 的倍数限制，路径计算过程稍显复杂。

核心思想

1. 路径数与时间的关系：出发时刻和结束时刻都是 $k$ 的非负整数倍，这意味着走过的路径数也应为 $k$ 的倍数。因此，当路径数和时间不满足要求时，必须调整出发时间至 $k$ 的整数倍。
2. BFS 实现：由于这是一个边权为 1 的图，最短路径可以通过广度优先搜索来解决，同时结合优先队列求最优解。
3. 避免死循环：运行过程中，可能会进入死循环。为了避免这种情况，可以通过记忆化来记录当前状态是否已经被处理过。

BFS 算法实现

void bfs(int st){
	priority_queue<node> que;  // 使用优先队列进行搜索
	memset(vis, 0x3f, sizeof vis);  // 初始化访问数组为极大值，表示未访问过
	que.push((node){0, 0, st});  // 初始状态，时间为 0，路径数为 0，从起点 st 开始
	vis[1][0] = 0;  // 起点状态的访问记录
	
	while (!que.empty()) {  // 当队列不为空时
		node h = que.top();
		que.pop();  // 弹出队列的顶部元素，当前节点 h
		int u = h.id, tim = h.t, dis = h.d;  // 当前节点 u 的编号、时间 tim、路径数 dis
		
		if (u == n && dis % k == 0) {  // 若到达终点并且路径数为 k 的倍数
			ans = tim + dis;  // 计算答案
			break;  // 退出循环
		}
		
		// 遍历 u 的所有邻接边
		for (int i = head[u]; i; i = e[i].to) {
			int v = e[i].v, w = e[i].w;  // 邻接点 v，边权 w
			int mod = (dis + 1) % k;  // 下一次路径数取模 k 的值
			
			// 如果当前时间可以直接通过该边
			if (tim + dis >= w) {
				if (vis[v][mod] <= tim) continue;  // 若该状态已经被访问过，跳过
				vis[v][mod] = tim;  // 更新访问时间
				que.push((node){tim, dis + 1, v});  // 将新的状态加入队列
			} else {  // 若当前时间无法通过该边
				int time = tim + ((w - tim - dis - 1) / k + 1) * k;  // 调整时间
				if (vis[v][mod] <= time) continue;  // 若该状态已经被访问过，跳过
				vis[v][mod] = time;  // 更新访问时间
				que.push((node){time, dis + 1, v});  // 将新的状态加入队列
			}
		}
	}
}

记忆化的必要性

考虑到可能存在多条路径到达同一个节点，为了避免多次处理相同的状态，采用记忆化来保存到达该节点时的最优状态。

具体情况如下：

1. 如果有两条不同路径到达同一个节点：
   • 假设第一条路径的出发时间为 $t_1$，路径数为 $dis_1$；
   • 第二条路径的出发时间为 $t_2$，路径数为 $dis_2$；
   • 如果 $t_1 \leq t_2$ 且 dis_1 \equiv dis_2 (\mod k)，且第一条路径在第二条路径之前被处理，则第一条路径一定是更优的选择。

通过这种方式，优先队列能够确保更早到达且路径数满足条件的路径优先被处理，从而避免死循环并确保找到最优解。

完整代码

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

const int maxn = 1e4 + 5;
int n, m, k, cnt = 1, ans;
int head[maxn], vis[maxn][105];

struct edge {
    int v, to, w;
} e[maxn << 1];

struct node {
    int t, d, id;
    bool operator <(const node &x) const {
        return t + d > x.t + x.d;  // 优先队列按时间和路径数的和进行排序
    }
};

void add(int u, int v, int w) {
    e[cnt].v = v, e[cnt].w = w, e[cnt].to = head[u];
    head[u] = cnt++;
}

void bfs(int st) {
    priority_queue<node> que;
    memset(vis, 0x3f, sizeof vis);  // 初始化访问数组
    que.push((node){0, 0, st});  // 将起点状态加入队列
    vis[1][0] = 0;  // 起点状态的访问记录
    
    while (!que.empty()) {
        node h = que.top();
        que.pop();
        int u = h.id, tim = h.t, dis = h.d;
        
        if (u == n && dis % k == 0) {  // 若到达终点且路径数为 k 的倍数
            ans = tim + dis;
            break;
        }
        
        for (int i = head[u]; i; i = e[i].to) {  // 遍历 u 的所有邻接点
            int v = e[i].v, w = e[i].w;
            int mod = (dis + 1) % k;
            
            if (tim + dis >= w) {  // 当前时间可以通过
                if (vis[v][mod] <= tim) continue;
                vis[v][mod] = tim;
                que.push((node){tim, dis + 1, v});
            } else {  // 当前时间无法通过，调整时间
                int time = tim + ((w - tim - dis - 1) / k + 1) * k;
                if (vis[v][mod] <= time) continue;
                vis[v][mod] = time;
                que.push((node){time, dis + 1, v});
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);  // 添加边
    }
    ans = -1;
    bfs(1);  // 从起点 1 开始搜索
    printf("%d", ans);  // 输出结果
    return 0;
}

总结

• 通过优先队列的 BFS 结合记忆化避免死循环，有效解决了路径和时间问题。
• 算法在时间复杂度上为 $O(n \log n)$，优先队列的使用使得每次处理节点时都能优先找到最优解。