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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

EMLOG程序单页友链和标签增加美化

单页友联效果图: 标签页面效果图: 源码介绍 EMLOG单页友情链接和TAG标签,友链单页文件代码main{width: 58%;是设置宽度 自己把设置成与您的网站宽度一样,如果自适应就填写100%,TAG文件不用修改 安装方法:把Links.php和tag.php上传到网站根目录即可,访问 域名/Links.php、域名/tag.php 所有模板适用,代码就不粘贴出来,已经打

跨系统环境下LabVIEW程序稳定运行

在LabVIEW开发中,不同电脑的配置和操作系统(如Win11与Win7)可能对程序的稳定运行产生影响。为了确保程序在不同平台上都能正常且稳定运行,需要从兼容性、驱动、以及性能优化等多个方面入手。本文将详细介绍如何在不同系统环境下,使LabVIEW开发的程序保持稳定运行的有效策略。 LabVIEW版本兼容性 LabVIEW各版本对不同操作系统的支持存在差异。因此,在开发程序时,尽量使用

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

OWASP十大安全漏洞解析

OWASP(开放式Web应用程序安全项目)发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南,它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析: 1. 注入漏洞(Injection) 描述:攻击者通过在应用程序的输入数据中插入恶意代码,从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响:可能导致数据泄

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动