天梯赛 L3-025 那就别担心了

news/2024/3/29 1:18:24/文章来源:https://blog.csdn.net/qq_45554473/article/details/130283603

原题链接:

PTA | 程序设计类实验辅助教学平台

题目描述:

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。

输入格式:

输入首先在一行中给出两个正整数 N(1<N≤500)和 M,分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行,每行给出一对命题之间的推理关系,即两个命题的编号 S1 S2,表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系,且任一命题不能循环自证(即从该命题出发推出该命题自己)。

最后一行给出待检验的两个命题的编号 A B

输出格式:

在一行中首先输出从 A 到 B 有多少种不同的推理路径,然后输出 Yes 如果推理是“逻辑自洽”的,或 No 如果不是。

题目保证输出数据不超过 109。

输入样例 1:

7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1

输出样例 1:

3 Yes

输入样例 2:

7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1

输出样例 2:

3 No

解题思路:

注意:题目要求判断是否逻辑自洽是判断从A点起的所有路径是否都能够到达B。

记忆化搜索、树形dp。

设f[i]为顶点i到达顶点B的路径数,那么f[i]=i的所有子节点到达顶点B的路径总数。

重点来了,如何判断是否逻辑自洽?

其实可以在dfs的过程中同时判断,只要路径中有任何一个f[i]为0,也就是到达B的路径数为0,即不满足逻辑自洽,否则满足逻辑自洽。

代码(CPP):

给出两份代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m, A, B, cnt;
vector<int> G[maxn];
int Cnt[maxn];
bool flag = true;int dfs(int v)
{if(Cnt[v])  // 备忘录,,记忆化搜索,查备忘录内有无记录,有则不需要再次计算return Cnt[v];for (int i = 0; i < G[v].size(); i++){Cnt[v] += dfs(G[v][i]);}if(Cnt[v] == 0)  // 如果路径上有任何一个点无法到达B,则这个逻辑图不是逻辑融洽的flag = false;return Cnt[v];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;while(m--){int u, v;cin >> u >> v;G[u].push_back(v);}cin >> A >> B;Cnt[B] = 1;dfs(A);cout << Cnt[A] << " " << (flag ? "Yes" : "No");return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m, A, B, cnt;
vector<int> G[maxn];
int Cnt[maxn];
bool flag = true;int dfs(int v)
{if(Cnt[v])  // 备忘录,,记忆化搜索,查备忘录内有无记录,有则不需要再次计算return Cnt[v];for (int i = 0; i < G[v].size(); i++){Cnt[v] += dfs(G[v][i]);}if(Cnt[v] == 0)  // 如果路径上有任何一个点无法到达B,则这个逻辑图不是逻辑融洽的flag = false;return Cnt[v];
}
int main()
{
//     freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;while(m--){int u, v;cin >> u >> v;G[u].push_back(v);}cin >> A >> B;Cnt[B] = 1;dfs(A);cout << Cnt[A] << " " << (flag ? "Yes" : "No");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_102748.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用java 实现二叉树创建

二叉树是数据结构中的一个重要的概念&#xff0c;二叉树的概念最早由 Linus Torvalds在1958年提出。他给出了一个树形数据结构&#xff0c;可以用来存储二叉树。每个节点的左子树和右子树都是空&#xff0c;中间层是子树。在一个给定的空间中&#xff0c;每一个节点都有两个左右…

相机雷达联合标定cam_lidar_calibration

文章目录 运行环境&#xff1a;1.1 ROS环境配置1&#xff09;工作空间创建和编译2&#xff09;官方数据集测试环境 2.1 在线标定1&#xff09;数据类型2&#xff09;标定板制作3&#xff09;配置文件4&#xff09;开始标定5&#xff09;完整实现步骤 3.1 python版本选择3.2 rvi…

4年的测试工程师,你遇到过自身瓶颈期吗?又是怎样度过的?

从毕业到现在已经快4年啦&#xff0c;一直软件测试行业混迹。我不是牛人&#xff0c;但是自我感觉还算是个合格的测试工程师&#xff0c;有必要写下自己将近4年来的经历&#xff0c;给自我以提示&#xff0c;给刚入行的朋友提供点参考。 貌似这一点适应的行业最广&#xff0c;…

Java——二叉搜索树的后序遍历序列

题目链接 牛客在线oj题——二叉搜索树的后序遍历序列 题目描述 输入一个整数数组&#xff0c;判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 数据范围&#xff1a; 节点数量 0≤n≤1000 …

自习室管理系统的设计与实现(论文+源码)_kaic

摘要 近年来&#xff0c;随着高校规模的逐步扩大&#xff0c;学生对高校自习室座位的需求也在不断增加。然而&#xff0c;一些高校仍然采用人工管理学院自习室座位&#xff0c;这大大降低了管理效率。显然&#xff0c;开发一个成本低、占用资源少、能提高高校自习室座位管理效率…

Junit 5 如何使用 Guice DI

Guice 是一个依赖注入的小清新工具。 相比 Spring 的依赖管理来说&#xff0c;这个工具更加小巧&#xff0c;我们可以在测试中直接使用。 Junit 5 在 Junit 中使用就没有那么方便了&#xff0c;因为 Junit 没有 Guice 的注解。 你需要手动写一个类&#xff0c;在这个类中&a…

ABeam Insight | 智能制造系列(6):虚拟/增强现实(VR/AR)×智能制造

虚拟现实&#xff08;VR&#xff09;和增强现实&#xff08;AR&#xff09;的概念早在20世纪60年代就被提出&#xff0c;但由于当时的技术水平无法满足相关应用的需求&#xff0c;这些概念并没有引起广泛关注。直到近年来随着计算机技术的飞速发展&#xff0c;虚拟现实和增强现…

nodejs+vue 文旅旅游公司智能管理OA系统

通过本次设计&#xff0c;让我学到了更多的知识&#xff0c;而且在设计中会有一些问题出现&#xff0c;最后通过查阅资料和在老师和同学的帮助下完成了系统的设计和开发&#xff0c;使得这次系统的开发非常的有意义。同时通过这次系统的设计也让我明白了自己在哪方面有不足&…

【PWN刷题__ret2text】[CISCN 2019华北]PWN1

ret2text~ 前言 依旧是简单的ret2text 一、checksec查看 No canary found 没有开启栈溢出保护 二、IDA反汇编 双击进入func() 发现后门函数system("cat/flag")&#xff1b;根据语义&#xff0c;函数提供了修改v1&#xff0c;判断v2是否等于11.28125&#xff0c;如…

项目沟通管理5大技巧 第4个很重要

1、充分使用twitter管理沟通模型 项目沟通会议可以充分使用witter的管理沟通模型&#xff0c;提高会议沟通效率。使用此模型&#xff0c;主要是有三步&#xff1a; 第一步&#xff1a;倾听&#xff0c;项目经理需要保持中立的立场&#xff0c;不先表态&#xff0c;让团队成员畅…

SAP ABAP 使用SICF发布HTTP API接口

一、SE24创建类&#xff1a;Z_HCX_HTTP 1、创建类&#xff1a; 2、切换到接口&#xff08;interface&#xff09;页签&#xff0c;输入IF_HTTP_EXTENSION &#xff0c;回车。切换到方法&#xff08;method&#xff09;页签&#xff0c;双击IF_HTTP_EXTENSION~HANDLE_REQUEST进…

STM32 产生随机数方式

STM32 产生随机数方式 C语言的stdlib.h库里的srand(unsigned seed)和rand(void)函数&#xff0c;可以配合产生伪随机数。其中srand(seed)产生算法种子&#xff0c;再由rand()通过算法产生随机数&#xff0c;产生的随机数在宏定义RAND_MAX范围内。如果seed不变&#xff0c;则产…

URL 转为QR code(二维码)

推荐一个良心的网站&#xff0c;能够免费地将url、text编码为二维码&#xff0c;而且还能设计logo、颜色等。 https://www.the-qrcode-generator.com/ 如下图&#xff1a; 可以自己定义logo、颜色&#xff1a; 还能查看扫描历史等统计信息&#xff1a; 上述所有功能都是免…

【虚拟仿真】Unity3D打包WEBGL后播放视频(VideoPlayer组件)

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 本篇文章实现Unity3D打包WEBGL后播放视频&#xff0c;如下图所…

VGG网络与中间层特征提取

1. 背景 VGG是常见的用于大型图片识别的极深度卷积网络&#xff0c; 这里主要介绍VGG网络预测在ImageNet数据集上的训练及预测。 2. ImageNet图像数据集简介 ImageNet包含了145W张224*224像素的三通道彩色图像数据集&#xff0c;图像划分为1000个种类。其中训练集130W张&…

Observability:添加免费和开放的 Elastic APM 作为 Elastic 可观察性部署的一部分 - 8.x

作者&#xff1a;David Hope 在最近的一篇博文中&#xff0c;我们向你展示了如何开始使用 Elastic 可观察性的免费开放层。 下面&#xff0c;我们将介绍你需要做些什么来扩展你的部署&#xff0c;这样你就可以开始免费从应用程序性能监控&#xff08;APM&#xff09;或跟踪集群…

可算是熬出头了,测试4年,费时8个月,入职阿里,涨薪14K

前言 你的努力&#xff0c;终将成就无可替代的自己。 本科毕业后就一直从事测试的工作&#xff0c;和多数人一样&#xff0c;最开始从事点点点的工作&#xff0c;看着自己的同学一步一步往上走&#xff0c;自己还是在原地踏步&#xff0c;说实话这不是自己想要的状态。 一年半…

为什么你永远不应该在CSS中使用px来设置字体大小

代码部署后可能存在的BUG没法实时知道&#xff0c;事后为了解决这些BUG&#xff0c;花了大量的时间进行log 调试&#xff0c;这边顺便给大家推荐一个好用的BUG监控工具 Fundebug。 在Josh Collinsworth的博客文章“永远不要用px作为字体大小”中&#xff0c;作者讨论了为什么不…

Ceph入门到精通-Ceph 编排器简介

第 1 章 Ceph 编排器简介 作为存储管理员&#xff0c;您可以将 Ceph 编排器与 Cephadm 实用程序搭配使用&#xff0c;能够发现设备并在 Red Hat Ceph Storage 集群中创建服务。 1.1. 使用 Ceph Orchestrator Red Hat Ceph Storage Orchestrators 是经理模块&#xff0c;主要…

C语言函数大全-- o 开头的函数

C语言函数大全 本篇介绍C语言函数大全-- o 开头的函数 1. obstack_init&#xff0c;obstack_free&#xff0c;obstack_alloc&#xff0c;obstack_blank&#xff0c;obstack_grow 1.1 函数说明 函数声明函数功能void obstack_init(struct obstack *obstack_ptr);它是 POSIX …