CSP-J 2023题解

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)

CPP

#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)

。

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

$(\sqrt{\Delta})$ 为整数时：记 $(k = \sqrt{\Delta})$ 。我们要输出的数是 $(x=\frac{b^{*}+k}{a^{*}})$ ，输出这种形式的解的做法和讨论性质 $B$ 时一致。
$(\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))

CPP

#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模板了。突破口就在此。

BFS

过程中，我们用

vis[u]

记录

u

点是否已经走过。那么在第一次遍历到

n

, 程序就会结束，此时的离开时间不一定是

k

的整数倍。有可能是第二次遍历到n时的时间才是

k

的倍数，所以只记录是否访问过点，是不行的。还需要记录某个时间点是否来过这个点。因此，需要将

vis

数组修改为二维，第二维记录到达这个点的时间。

但是又会出现一个问题，这样空间不就爆了吗？其实，第二维只需要记录对

k

的余数即可。因为，第二次或者后面扫描到同个点，且第二维的余数相同，肯定是没有第一次遍历到时的时间优的，一定是多了

k

的整数倍。这是因为

bfs

的搜索顺序，决定了早到达的时间一定小。题中，

k

最多取100，所以空间上是满足要求的。

CPP

#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;// 顶点，及到这个点的时间 
};

vector<edge>g[N];

bool vis[N][110];

int bfs(){
	queue<node>q;
	q.push((node){1, 0});
	
	while(q.size()){
		node cur = q.front(); q.pop();
		if(cur.p == n && cur.t % k == 0)// 第一次遇到的，且时间满足k倍，则一定是最优解 
			return cur.t;
		
		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]; // 扩展下一个点 
			q.push((node){x.v, cur.t + 1});
		}
	}
	return -1;
}

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});
	}
	cout << bfs() << '\n';
	return 0;
}

提交后，的确是35分！

接下来，我们加入道路的开放时间，进一步考虑。

从起点出发，想去下一个相邻的地点前，检查一下当前时间与开放时间的大小。

如果当前时间 >= 开放时间，那么可以通过，并将当前时间+1走到下一个相邻地点。
如果当前时间<开放时间，那么说明走不通。真的走不通了？不，我们只需要推迟出发时间即可。举个例子，

如果

k = 3

，

0

时刻从

1

出发，

1->2

的开放时间是

0

，

2->3

的开放时间是

1

3->4

的开放时间为

7

显然，上述例子中，

2

时刻在

3

号点，是无法到达

4

号点的，因为此时道路还没开放。题目中又规定不能等待。但是实际上，我们可以通过推迟出发时间来达到停留的效果。由于出发时间必须是

3

的倍数，因此增加的“等待"时间也必须是

k = 3

的倍数，

$2 + 3$ 时刻判断道路是否开放，如果不开放，则继续推迟一个出发时间。
$2 + 3 + 3$ ，此时发现可以通行，相当于等待了 $2$ 个 $k$ 的时间，到达 $4$ 号点。

那么，怎么计算需要多少个

k

等待时间

wait = （

开放时间

-

到达时间

+ k - 1）/ k * k;

这里要取上整。

这也是出发时间需要推迟的单位时间数。下面我们就对bfs简单改造一下，加上对开放时间的判断。如果到某个点的时候，下一个地点的开放时间已经过了，那么可以走下去，如果没过，则将到达时间增加k的若干倍。

CPP

#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; // 顶点，及到这个点的时间 
};

vector<edge>g[N];

bool vis[N][110];

int ans = INT_MAX;

void bfs(){
	queue<node>q;
	q.push((node){1, 0});
	
	while(q.size()){
		node cur = q.front(); q.pop();
		
		if(cur.p == n && cur.t % k == 0)
			ans = min(ans, cur.t);
		
		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;
}

提交后得到50分！

再进一步思考，剩余的哪里出了问题？思考下面的图：

1

出发，扩展两个节点

2

和

3

2

出发，扩展到4，时间为

t_1

;

3出发，扩展到4，时间为

t_2

，且

t_1 > t_2, t_1 \% k == t_2 \% k

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

那么在上述

50

分代码中，由于

2

号先扩展出来的

t_1

,使得

vis[4][t_1 \% k]

标记了，导致

3

号扩展出来的

t_2

, 在代码的第

30

行被

continue

。但实际上

t_2

答案更优！

改进办法就是先计算

3

号点扩展出来的

t_2

，就可以避免上述情况。

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

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

CPP

#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;
}

总结：

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

文章操作

T1

T2

T3

25 分做法：

50 分做法：

额外的 20 分：

100 分做法：

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

相关推荐

评论

CSP-J 2023题解