CSP 2023 提高级第一轮 CSP-S 2023初试题 程序阅读第三题解析

2024-09-01 03:44

本文主要是介绍CSP 2023 提高级第一轮 CSP-S 2023初试题 程序阅读第三题解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

三、完善程序(单选题,每小题 3 分,共计 30 分)

一、题目阅读

(第 k 小路径)给定一张 n 个点 m 条边的有向无环图,定点编号从 0 到 n−1,对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第 k 小的路径。保证存在至少 k 条路径。上述参数满足 1≤n,m≤105,1≤k≤1018。

在程序中,我们求出从每个点出发的路径数量。超过 1018 的数都用 1018 表示。然后我们根据 k 的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];int next(std::vector<int> cand, long long &k) {std::sort(cand.begin(), cand.end());for (int u : cand) {if (①) return u;k -= f[u];}return -1;
}int main() {std::cin >> n >> m >> k;for (int i = 0; i < m; ++i) {int u, v;std::cin >> u >> v; // 一条从u到v的边E[u].push_back(v);++deg[v];}std::vector<int> Q;for (int i = 0; i < n; ++i)if (!deg[i]) Q.push_back(i);for (int i = 0; i < n; ++i) {int u = Q[i];for (int v : E[u]) {if (②)Q.push_back(v);--deg[v];}}std::reverse(Q.begin(), Q.end());for (int u : Q) {f[u] = 1;for (int v : E[u])f[u] = ③;}int u = next(Q, k);std::cout << u << std::endl;while (④) {⑤;u = next(E[u], k);std::cout << u << std::endl;}return 0;
}

二、代码分析

题目地意思是有一张有向无环图,任意一个顶点开始通过相连边到达某个顶点算一个路径,比如说1,2有边相连,那么1算一条路径,1 -> 2算一条路径,2也算一条。

按字典序排好后就是:1,1 -> 2,2。

代码解析:

首先处理各个顶点之间的关系,并拓扑排序,然后倒过来(这是动态规划的常态,从最后开始。变色部分会解释)

接下来时整个推算过程。

f[i]表示以 i 为起点的路径总数,那么我们可以推算出这样的一个公式。

f[u] = f[E[u][0]]+f[E[u][1]]+...+f[E[u][n]]   +  1

E[u][1, 2, ... , n]代表u的邻接节点。

为什么呢?假设u只有一个邻接节点v,u为起点的路径总数个数是1(u->v) + f[v](u->v->...,其中v->...部分就是f[v])。

看到第41行,我们知道 f 数组是用来存放以某个节点为起点的路径数量,那么我们应该去遍历它的每个邻接节点,这就是为什么要反转结果了,反转之后,与其他关联最多的总是已经处理(请注意,拓扑排序不是那度数排序!别踩坑)。

然后我们计算出以它为起点出发的路径数量。

next函数的作用如下:

        接着我们第一次调用next函数。

        cand就是Q。

        将它排好序之后就是第一个顶点的选择,那么按字典序来肯定选最小的啊,所以我们取了第一个元素。

        接着按照题意,我们应该看看,我以u做起点的路径个数够不够k,如果够了,那么就不要往下了,反正肯定就是以u开始了。如果不够,那还要取下一个节点做开始,以此类推......

        当够了的时候,我们要把k减小,减小前面的总个数。(这好比把单位一点一点缩小)

        接着每次将对应起点的临界矩阵送给next函数同样道理地处理......

三、题目分析

1. ①处应填()

A. k >= f[u]

B.  k <= f[u]
C.  k > f[u]
D.  k < f[u]

2. ②处应填()

A. deg[v] == 1

B.  deg[v] == 0
C.  deg[v] > 1
D.  deg[v] > 0

3. ③处应填()

A. std::min(f[u] + f[v], LIM)

B.  std::min(f[u] + f[v] + 1, LIM)
C.  std::min(f[u] * f[v], LIM)
D.  std::min(f[u] * (f[v] + 1), LIM)

4. ④处应填()

A. u != -1

B. !E[u].empty()

C. k > 0
D.  k > 1

5. ⑤处应填()

A. K+=f[u]

B.  k-=f[u]
C. --k
D. ++k

这篇关于CSP 2023 提高级第一轮 CSP-S 2023初试题 程序阅读第三题解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1125851

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

Java中的runnable 和 callable 区别解析

《Java中的runnable和callable区别解析》Runnable接口用于定义不需要返回结果的任务,而Callable接口可以返回结果并抛出异常,通常与Future结合使用,Runnab... 目录1. Runnable接口1.1 Runnable的定义1.2 Runnable的特点1.3 使用Ru

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》:本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac