CSP-J 2023题解

compaq · 2025-02-27 12:08:52 · 题解

T1

90 分做法： 与经典问题 “约瑟夫问题” 类似，我们可以对约瑟夫问题的背景稍加改动，即可模拟从第 1 ~n 个苹果中反复拿取苹果的过程，即：

• 每一轮报数从剩余的最左边的人开始；
• 每一轮报数从 1 开始，若报数除以 3 的余数为 1，则出列。

我们可以用布尔数组 vis [i] 表示第 i 个苹果是否已被拿走，若已经被拿走，则 vis [i] = true。代码实现时，可以使用二重循环，外层循环使拿取苹果过程重复进行，内层循环依次遍历第 i = 1~n 个苹果，当且仅当 vis [i] 为 false 时，才考虑将苹果计入 “报数” 中，如果报数模 3 为 1，则将第 i 个苹果拿走，对应地，vis [i]= true。

此方法需要开一个大小至少为 n 的数组，对于前 9 个数据点，n \le 10^6, 空间足够，但最后一个数据点n \le 10^9，空间限制，故期望得分90分。

100分做法：

先考虑第一问：n 个苹果拿完需要多少天？ 我们可以从 n 较小的情形入手，以输入样例的 n = 8 为例，第一轮会拿走第 1、4、7 个苹果。此时，我们可以对样例做突然调整：如果 n = 9、10、11，那么第一轮还会拿走几个苹果呢？，不难发现：

• n = 9 时，仍然只拿走第 1、4、7 个苹果，共 3 个；
• n = 10 时，需拿走第 1、4、7、10 个苹果，共 4 个；
• n = 11 时，仍然只拿走第 1、4、7、10 个苹果，共 4 个；

其实，问题中拿走苹果的规则，实际就是 “每三个苹果拿走一个”，我们可以考虑将 n 个苹果从左到右每 3 个分成一段，最后一段可能不足 3 个，则这一轮将拿走每一段的最左边的苹果，拿走的总数即分段的数量，在数学上可以使用向上取整记号(\lceil\frac{n}{3}\rceil)表示。 代码实现时，可以使用一个循环，反复使(n -=\lceil\frac{n}{3}\rceil)，直至 n 为 0，则循环总次数即为第一问的答案。

再考虑第二问：编号为 n 的苹果在第几天被拿走？ 解决第二问的关键点，在于关注到数据范围中的特殊性质：第一天就能取走编号为 n 的苹果。n 形如 3k + 1 这样的模 3 余 1 的正整数时，第 n 个苹果一定会在第 1 天被拿走。所以当 n 模 3 余 1 时，答案即为 1。但如果 n 不满足这一条件呢？ 其实，我们只需要注意到，在拿走苹果使 n 不断减小的过程中：

• 当 n 模 3 余 1 时，这一天就会拿走最后一个苹果；
• 反之，当 n 模 3 余数不为 1 时，这一天不会拿走最后一个苹果。

从而初始时，若 n 模 3 余数不为 1，则第 n 个苹果还会留着，直至某一时刻 n 模 3 余 1。所以我们可以在循环中反复判断当前苹果数 n 是否模 3 余 1，第一次判断成立时，此时已经经历过的循环次数就是第二问的答案。

最后，这一做法并不需要开数组，唯一需要分析的是时间复杂度。我们可以粗略估计：每一轮循环，n大约变为原来的 2/3，假设循环次数为 m，则(n \approx(\frac{3}{2})^m)，故(m = O(log_{\frac{3}{2}}n)=O(log n))。

T2

25 分做法：

我们会发现此时 n ≤ 8，n 非常小。所以直接暴力枚举这 n 个站点每一个是否去加油就可以了。总共有 2ⁿ种情况，这就是一个子集枚举的过程。可以使用 dfs 或者二进制枚举来实现。 对于每一种情况，我们只需要算出每个站点的花费就可以了。 因为我们要使得花费最少，所以买油的数量就是能够刚好到达下一次加油的站点所需要的油。这里可以直接模拟，从第一个站点出发（第一个站点必须买油，否则一定无法到达站点 n），每次跳到下一个需要买油的站点。 这个过程和 100 分做法中模拟的过程是类似的，可以参考 100 分做法的解析。

额外的 15 分：

对于性质 A，站点 1 的油价是最低的，也就是在其它地方买油一定没有在站点 1 买划算。 由于我们的油箱大小是无限的，所以直接在站点 1 买够能走到站点 n 的油就可以了。 答案就是(\left\lceil\frac{\sum v_{i}}{d}\right\rceil * a_{1})。

100 分做法： 我们可以发现从 1 号站点走到 2 号站点所需要的油一定是在 1 号站点买，从 2 号站点走到 3 号站点所需要的油，可以在 1 号站点和 2 号站点买，从 3 号站点走到 4 号站点所需要的油可以从 1、2、3 这三个站点买。 也就是说从 i 号站点走到 i + 1 号站点这一段路，我们需要的油可以从前 i 个站点去购买。其实就相当于在 i 号站点买油需要花费的代价是前 i 个站点买油所需要的最小值。 接下来，我们就按照刚才这个性质进行模拟。 每次从当前站点买够刚好能走到下一个站点的油就可以了。 我们定义一个变量，用 k 表示我们走到下一个站点后还能多走多少路程。 直接从第一个站点开始往后走。初始时 k = 0。

• 如果 k 小于走到下次买油的地方的路程（也就是 k < (v_{i}))，我们就在这里买油，并且更新 k 和答案（花费）。 此时所需要买油的数量其实就是(\left\lceil\frac{v_{i}-k}{d}\right\rceil)升，(v_{i}-k)是我们走到下一站还需要的路程，(\left\lceil\frac{v_{i}-k}{d}\right\rceil)表示走(v_{i}-k)需要消耗的油的数量。k 的变化就是新的(k=\left\lceil\frac{v_{i}-k}{d}\right\rceil * d - (v_{i}-k))。
• 否则的话，我们直接更新 k，让 k 减少我们走到下一个站点买油地方的路程 (k = k - v_{i})。
• 不断重复上述讨论直到走到 n 号站点。

时间复杂度：O (n)

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, d, v[N], a[N];
long long ans;
int main(){
    cin >> n >> d;
    for(int i = 1; i < n; i++) cin >> v[i];
    for(int i = 1; i <= n; i++) cin >> a[i];
    int minn = a[1]; // 能加的最便宜的油
    int rest = 0; // 剩下还能走的公里数
    for(int i = 1; i < n; i++){
        minn = min(a[i], minn);
        if(rest >= v[i]){
            rest -= v[i];
            continue;
        }
        int t = (v[i] - rest + d - 1) / d;
        ans += 1ll * t * minn;
        rest = t * d + rest - v[i];
    }
    printf("%lld\n",ans);
    return 0;
}

T3

25 分做法：

先来讨论特殊性质 B，也就是(c = 0)的情况，这个时候原本的方程就是(ax^{2}+bx = 0)，容易发现这个方程一定有实数解，并且两个解分别是(x_{1}=0),(x_{2}=-\frac{b}{a})。

• 当(x_{1}\geq x_{2})时，直接输出 0。

• 当(x_{1}< x_{2})时，我们来考虑输出(x_{2})（其实本质上相当于输出一个形如(\frac{q}{p})的数字，p,q均为整数）。

现在有两种情况。

• 第一种情况(x_{2})是个整数，也就是(b\%a == 0)，此时直接输出(-\frac{b}{a})的值。
• 第二种情况(x_{2})不是整数，也就是(b\%a!= 0)。此时我们需要按格式输出(x_{2})，可以给a,b都除以它们的最大公约数，从而把(x_{2})化成最简真分数的形式。记a,b的最大公约数是(gcd(a,b))，(a' = a / gcd(a,b)),(b' = b / gcd(a,b))。

此时需要输出的解(x_{2}=\frac{b'}{a'})。 需要特别注意的就是当(a'<0)时，输出的是(\{-b'\}/\{-a'\})这样的形式，当(a'>0)时，输出的是(\{b'\}/\{a'\})的形式。

50 分做法：

接着我们来讨论性质 A，也就是(b = 0)的情况，这个时候原本的方程会变成(ax^{2}+c = 0)。根据题意(\Delta = -4ac)，当(\Delta < 0)时方程无实数解，直接输出NO；否则，方程解的形式一定是(x_{1}=\frac{\sqrt{-4ac}}{2a}=\frac{\sqrt{-ac}}{a})，(x_{2}=-\frac{\sqrt{-4ac}}{2a}=-\frac{\sqrt{-ac}}{a})。最大的实数解是(x_{1})，下面考虑如何输出（本质上需输出形如(\frac{\sqrt{q}}{p})的数字，p，q均为整数）。

这里主要讨论(c\neq0)的情况，因为(c = 0)时直接输出 0 即可。

• 当(\sqrt{-ac})为整数时： 记(k = \sqrt{-ac})，需要输出的解就是(x=\frac{k}{a})，接下来直接利用处理性质 B 时的方法来做。

• 当(\sqrt{-ac})不为整数时：

  • 先把(\sqrt{-ac})转化为(k*\sqrt{r})的形式，保证不存在大于 1 的数d使得(d^{2}|r) 。 因为(-ac\leq M^{2})，令(k = 1)，(r = -ac)，用i从 2~M 枚举完全平方数，每次检查(-ac)是否是(i^{2})的倍数，若是则让k变为(k*i)（k为根号前系数），r变为\$(\frac{r}{i^{2}}) 。 此时要输出的解\$(x_{1}=\frac{k}{a}*\sqrt{r}) 。
  • 然后将(\frac{k}{a})化为最简分数形式： 记k和a的最大公约数是(gcd(a,k))，令(k' = k/gcd(a,k))，(a' = a/gcd(a,k)) 。 此时输出的解(x_{1}=\frac{k'}{a'}*\sqrt{r}) 。若(a'<0)，让(a')和(k')均变为相反数。 由于(\sqrt{-ac})不是整数，所以(r\neq1)，输出形式大致为(\{k'\}*sqrt(\{r\})/\{a'\}) 。

需要注意两个特殊情况：

• 当(k' = 1)时，不需要输出(\{k'\}*)这个部分。
• 当(a' = 1)时，不需要输出(/\{a'\})这个部分。

额外的 20 分：

现在我们来讨论性质 C，也就是如果方程有解，解一定是整数的情况。对于一元二次方程(ax^{2}+bx + c = 0)，(\Delta = b^{2}-4ac)。

• 当(\Delta < 0)时，方程无实数解，直接输出NO。

• 当(\Delta \geq 0)时，我们知道两个解(x_{1}*x_{2}=\frac{c}{a})。然后由于性质 C 保证如果有解，解一定是整数，所以我们可以通过枚举法来枚举这两个解。 由于答案一定是整数，说明(\Delta)一定是一个完全平方数，而且式子除以2a后可以整除，因此这里直接输出((-b + sqrt(\Delta))/2/a)就可以了。

100 分做法：

根据题意，我们可以知道对于一元二次方程(ax^{2}+bx + c = 0)，(\Delta = b^{2}-4ac)。

• 当(\Delta < 0)时，方程无实数解，直接输出NO。

• 当(\Delta \geq 0)时，方程两个解分别为(x_{1}=\frac{-b}{2a}+\frac{\sqrt{\Delta}}{2a})，(x_{2}=\frac{-b}{2a}-\frac{\sqrt{\Delta}}{2a})。

• 当(a < 0)时，最大的实数解是(x_{2})。此时我们记(a^{*} = -2a)，(b^{*} = b)。

• 当(a > 0)时，最大的实数解是(x_{1})。此时我们记(a^{*} = 2a)，(b^{*} = -b)。

我们会发现需要输出的解(x=\frac{b^{*}}{a^{*}}+\frac{\sqrt{\Delta}}{a^{*}})，并且(a^{*} > 0)。

接下来我们分两种情况进行讨论：

1. (\sqrt{\Delta})为整数时： 记(k = \sqrt{\Delta})。我们要输出的数是(x=\frac{b^{*}+k}{a^{*}})，输出这种形式的解的做法和讨论性质 B 时一致。
2. (\sqrt{\Delta})不是整数时： 我们要输出的数是(x=\frac{b^{*}}{a^{*}}+\frac{\sqrt{\Delta}}{a^{*}})，我们要输出的其实是两个部分，一个部分是(\frac{b^{*}}{a^{*}})，另一个部分是(\frac{\sqrt{\Delta}}{a^{*}})，中间用+连接。 所以我们可以先用之前的做法把第一部分输出。

需要特别注意，当(b^{*} = 0)时，也就是没有第一部分的时候。我们不需要输出第一部分和+。

而关于第二部分的输出，做法和讨论性质 A 时一致（当时我们需要输出的是(\frac{\sqrt{-ac}}{a})，现在则是(\frac{\sqrt{\Delta}}{a^{*}})。

注意：现在我们需要枚举的完全平方数的范围不再是(2^{2}\sim M^{2})，而是(1^{2}\sim(\sqrt{5}M)^{2})，因为(\Delta \leq 5M^{2})，所以我们的i需要从2枚举到(\lfloor\sqrt{5}M\rfloor)。

满分做法其实就是把之前的对于特殊性质 A 和特殊性质 B 的做法进行整合。

时间复杂度：(O(TM))

#include<bits/stdc++.h>
using namespace std;
int t, m, a, b, c;
int aa, bb, gd1, gd2;
int gcd(int a, int b){
    if(a % b == 0) return b;
    return gcd(b, a % b);
}
int main(){
    scanf("%d%d", &t, &m);
    while(t--){
        scanf("%d%d%d", &a, &b, &c);
        int det = b * b - 4 * a * c;
        if(det < 0){
            printf("NO\n");
            continue;
        }
        int ans1 = 1;
        for(int i = 2; i * i <= det; i++) {
            while(det % (i*i) == 0)
                ans1 *= i, det /= i * i;
        }
        aa = 2 * a; bb = -b;
        if(aa < 0) aa = -aa, bb = -bb;
        if(det == 1) det = 0, bb += ans1;
        gd1 = gcd(abs(bb), aa);
        gd2 = gcd(ans1, aa);
        if(det == 0) {
            if(bb % aa == 0) printf("%d", bb / aa);
            else printf("%d/%d", bb / gd1, aa / gd1);
        }
        else {
            if(bb != 0) {
                if(bb % aa == 0) printf("%d", bb / aa);
                else printf("%d/%d", bb / gd1, aa / gd1);
                printf("+");
            }
            if(ans1 / gd2 != 1) printf("%d*", ans1 / gd2);
            printf("sqrt(%d)", det);
            if(aa / gd2 != 1) printf("/%d", aa / gd2);
        }
        printf("\n");
    }
    return 0;
}

T4 P9751 [CSP-J 2023] 旅游巴士

35分做法：a_i == 0

设想如果开放时间为0的话，那说明在任何一个地点，都可以顺利走到下一点，不用考虑道路开放不开放的问题。而且第一次达到终点时，一定为答案要求的最早时间——这些数据点是最简单的了，这几乎就是bfs模板了。突破口就在此。

4出发，扩展到5，刚好离开。

那么在上述50分代码中，由于2号先扩展出来的t_1,使得vis[4][t_1 \% k]标记了， 导致3号扩展出来的t_2, 在代码的第30行被continue。 但实际上t_2答案更优！

改进办法就是先计算3号点扩展出来的t_2，就可以避免上述情况。

怎么操作？ 利用优先队列 替换普通队列即可！

只需将上述代码再次简单修改！

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 +10;
int n, m, k;

struct edge{
    int v, a;  // 顶点， 及这个点开放时间 
};

struct node{
    int p, t; // 顶点，及到这个点的时间 
    friend bool operator < (node x, node y){
        return x.t > y.t;//重载，时间越小，优先级越高 
    }
};

vector<edge>g[N];

bool vis[N][110];

int ans = INT_MAX;

void bfs(){
    priority_queue<node>q;// 替换成优先队列 
    q.push((node){1, 0});

    while(q.size()){
        node cur = q.top(); q.pop();

        if(cur.p == n && cur.t % k == 0) // 这次不是第一次搜到就是最优解了 
            ans = min(ans, cur.t);  // 第一次搜到可能延迟了很多个k 

        if(vis[cur.p][cur.t % k]) continue;

        vis[cur.p][cur.t % k] = true;

        for(int i = 0; i < g[cur.p].size(); i++){
            edge x = g[cur.p][i];
            if(cur.t >= x.a) 
                q.push((node){x.v, cur.t + 1});
            else{
                int wait = (x.a - cur.t + k - 1) / k * k;
                q.push((node){x.v, cur.t + 1 + wait});
            }
        }
    }
}

int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u, v, a;
        cin >> u >> v >> a;
        g[u].push_back((edge){v, a});
    }

    bfs();
    if(ans == INT_MAX) puts("-1");
    else cout << ans << '\n';
    return 0;
}

总结：

测试数据范围可能会引导我们思考的方向。从小范围数据开始着手考虑问题，慢慢再进一步优化算法，从而解决整个问题。