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

相关文章

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

SpringBoot实现微信小程序支付功能

《SpringBoot实现微信小程序支付功能》小程序支付功能已成为众多应用的核心需求之一,本文主要介绍了SpringBoot实现微信小程序支付功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作... 目录一、引言二、准备工作(一)微信支付商户平台配置(二)Spring Boot项目搭建(三)配置文件

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3