当前位置: 首页 > news >正文

烦人的幻灯片——拓扑排序

烦人的幻灯片

  • 烦人的幻灯片
    • 问题描述
    • 输入输出格式
      • 输入格式
      • 输出格式
    • 输入输出样例
      • 输入样例:
        • 输入样例一:
        • 输入样例二:
      • 输出样例:
        • 输出样例一:
        • 输出样例二:
  • 正确做法
    • 拓扑排序
  • 代码

在这里插入图片描述

烦人的幻灯片

问题描述

李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人,他把自己做演讲要用的幻灯片随便堆放在一起。因此,演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者,他希望尽可能简单地完成它。情况是这样,教授这次演讲一共要用n张幻灯片(n≤26),这n张幻灯片按照演讲要使用的顺序已经用数字1,2,…,n在上面编上了号。因为幻灯片是透明的,所以我们不能一下子看清每一个数字所对应的幻灯片。

现在我们用大写字母A,B,C,。。。再次把幻灯片依次编上号,如图如示,我们可以很快发现编号为A的幻灯片是第4张,把它抽出来后我们又可以确定编号为C的幻灯片是第2张,。。。

你的任务是编写一个程序,把幻灯片的数字编号和字母编号对应起来,显然这种对应应该是唯一的;若是出现多种对应的情况或是某些数字编号和字母对应不起来,我们就称对应是无法实现的。

输入输出格式

输入格式

文件第一行只有一个数n,表示有n张幻灯片,接下来的n行第行包括4个整数Xmin,Xmax,Ymin,Ymax(整数之间用空格分开),为幻灯片的坐标,这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A,B,C,。。。再接下来的n行依次为n个数字编号的坐标X,Y,显然在幻灯片之外是不会有数字的。

输出格式

若是对应可以实现,你的输出文件应该包括n行,每一行为一个字母和一个数字,并且各行以字母的升序排列,注意输出的字母要大写并且顶格;反之,若是对应无法实现,在文件的第一行顶格输出None即可。行首行末无多余空格。

输入输出样例

输入样例:

输入样例一:

4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11

输入样例二:

2
0 2 0 2
0 2 0  2
1 1
1 1

输出样例:

输出样例一:

A4
B1
C2
D3

输出样例二:

None

正确做法

拓扑排序

拓扑排序是一种对有向无环图(DAG)进行排序的算法。在拓扑排序中,图中的节点表示任务或事件,有向边表示任务之间的依赖关系。拓扑排序的目标是找到一种排序方式,使得所有任务都按照依赖关系的顺序被执行。

拓扑排序的步骤如下:

  1. 初始化一个队列,将所有入度为0的节点加入队列中。
  2. 从队列中取出一个节点,并将其输出。
  3. 将该节点的所有邻接节点的入度减1。
  4. 如果某个邻接节点的入度变为0,将其加入队列中。
  5. 重复步骤2-4,直到队列为空。
  6. 拓扑排序的过程可以理解为不断移除入度为0的节点,并将其输出。如果图中存在环路,则无法进行拓扑排序,因为环路中的节点无法确定顺序。

拓扑排序的应用非常广泛,例如任务调度、编译顺序、依赖关系分析等。它可以帮助我们理清任务之间的依赖关系,确保任务按照正确的顺序执行,避免出现循环依赖或执行顺序混乱的情况。

代码

#include<bits/stdc++.h>
using namespace std;
struct pian{ int x1,x2,y1,y2; }p[30];
struct dian{ int x,y,b; }d[30];
int n,l,z[30];
bool tu[30][30],o[30];
bool t(int x,int y,int x1,int x2,int y1,int y2)
{return x>=x1&&x<=x2&&y>=y1&&y<=y2;
}
int main()
{cin >>n;for (int i=1;i<=n;i++)cin >>p[i].x1 >>p[i].x2 >>p[i].y1 >>p[i].y2;for (int i=1;i<=n;i++){cin >>d[i].x >>d[i].y;for (int j=1;j<=n;j++)if (t(d[i].x,d[i].y,p[j].x1,p[j].x2,p[j].y1,p[j].y2)){d[i].b++;tu[j][i]=1;}}for (int k=1;k<=n;k++)for (int tmp=0,i=1;i<=n;i++)if (!o[i] && d[i].b==1){for (int j=1;j<=n;j++)if (tu[j][i]){tmp=j;break;}z[tmp]=i;for (int j=1;j<=n;j++)if (tu[tmp][j]){tu[tmp][j]=0;d[j].b--;}l++;break;}if (l!=n){cout <<"None";return 0;}for (int i=1;i<=n;i++)cout <<char(64+i) <<z[i] <<endl;return 0;
}

相关文章:

烦人的幻灯片——拓扑排序

烦人的幻灯片 烦人的幻灯片问题描述输入输出格式输入格式输出格式 输入输出样例输入样例&#xff1a;输入样例一&#xff1a;输入样例二&#xff1a; 输出样例&#xff1a;输出样例一&#xff1a;输出样例二&#xff1a; 正确做法拓扑排序 代码 烦人的幻灯片 问题描述 李教授…...

无涯教程-Perl - ord函数

描述 此函数返回EXPR指定的字符的ASCII数值,如果省略则返回$_。例如,ord(A)返回值为65。 语法 以下是此函数的简单语法- ord EXPRord返回值 该函数返回整数。 例 以下是显示其基本用法的示例代码- #!/usr/bin/perl -wprint("ord() ", ord(G), "\n"…...

Python爬虫:js逆向调式操作及调式中遇到debugger问题

Python爬虫:js逆向调式操作及调式中遇到debugger问题 1. 前言2. js逆向调式操作2.1 DOM事件断点2.2 XHR/提取断点(用于请求接口参数加密处理)2.3 请求返回的数据是加密的2.4 hook定位参数 3. 调式中遇到debugger问题3.1 解决方式(一律不在此处暂停)3.2 问题&#xff1a;点击一律…...

HTML网页制作技巧:打造出色的用户体验

HTML是构建网页的基础语言&#xff0c;掌握一些关键的技巧可以帮助您创建出色的用户体验。本文将介绍一些HTML网页制作的技巧&#xff0c;从布局和样式到交互和可访问性&#xff0c;为您提供有用的指导。无论您是初学者还是有经验的开发者&#xff0c;这些技巧都将对您的网页设…...

探究使用HTTP代理ip后无法访问网站的原因与解决方案

目录 访问网站的原理是什么 1. DNS解析 2. 建立TCP连接 3. 发送HTTP请求&#xff1a; 4. 服务器响应&#xff1a; 5. 浏览器渲染&#xff1a; 6. 页面展示&#xff1a; 使用代理IP后访问不了网站&#xff0c;有哪些方面的原因 1. 代理IP的可用性&#xff1a; 2. 代理…...

SpringBoot 全局异常处理进阶

待总结 参考文章&#xff1a; SpringBoot 全局异常处理进阶&#xff1a;使用 ControllerAdvice 对不同的 Controller 分别捕获异常并处理 SpringBoot 对 controller 层捕获全局异常并处理的方法&#xff08;ControllerAdvice 和 ExceptionHandler&#xff09; 注解RestCont…...

数据结构(一):顺序表详解

在正式介绍顺序表之前&#xff0c;我们有必要先了解一个名词&#xff1a;线性表。 线性表&#xff1a; 线性表是&#xff0c;具有n个相同特性的数据元素的有限序列。常见的线性表&#xff1a;顺序表、链表、栈、队列、数组、字符串... 线性表在逻辑上是线性结构&#xff0c;但…...

【周末闲谈】人工智能热潮下的AIGC到底指的是什么?

生成式人工智能AIGC&#xff08;Artificial Intelligence Generated Content&#xff09;是人工智能1.0时代进入2.0时代的重要标志。 个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️周末闲谈】 系列目录 ✨第一周 二进制VS三进制 ✨第二周 文心一…...

sklearn垃圾邮件分类

在Python中&#xff0c;可以使用机器学习算法来进行垃圾邮件分类。下面是一个简单的示例&#xff0c;使用朴素贝叶斯算法进行垃圾邮件分类&#xff1a; import pandas as pd from sklearn.feature_extraction.text import CountVectorizer from sklearn.model_selection impor…...

UI美工设计岗位的工作职责

UI美工设计岗位的工作职责1 职责&#xff1a; 1、负责软件界面的美术设计、创意工作和制作工作; 2、根据各种相关软件的用户群&#xff0c;提出构思新颖、有高度吸引力的创意设计; 3、对页面进行优化&#xff0c;使用户操作更趋于人性化; 4、维护现有的应用产品; 5、收集和…...

ES6链判断运算符(?.)的正确打开方式

在实际应用中&#xff0c;如果读取对象内部 的某个属性&#xff0c;往往需要判断一下&#xff0c;属性的上层对象是否存在。比如&#xff0c;读取message.body.user.firstName这个属性&#xff0c;安全的写法是写成下下面这样&#xff1a; // 错误的写法 const firstName mes…...

删除块参照 删除块定义

删除块参照 void CDwgDatabaseUtil::DeleteBlockReference(CString strBlockName) {// 锁定文档acDocManager->lockDocument(acDocManager->curDocument());AcDbObjectId objRecId;if (...

机器学习笔记:李宏毅ChatGPT:生成式学习的两种策略

1 策略1 “各个击破”——autoregressive model “各个击破”——一个一个生成出来 2 策略2 &#xff1a; “一次到位”——non-autoregressve model 一步到位&#xff0c;全部生成出来 2.1 non-autoregressive model 如何确定长度&#xff1f; 两种策略 策略1&#xff1a;始…...

React 组件防止冒泡方法

背景 在使用 antd 组件库开发时&#xff0c;发现点击一个子组件&#xff0c;却触发了父组件的点击事件&#xff0c;比如&#xff0c;我在一个折叠面板里面放入一个下拉框或者对下拉框列表渲染做定制&#xff0c;每个下拉框候选项都有一个子组件… 解决 其实这就是 Javascri…...

MAUI+Blazor 如何开启浏览器调试工具

文章目录 前言如何开启调试模式输入快捷键打开浏览器有什么意义&#xff1f; 前言 MAUIBlazor其实就是浏览器套壳&#xff0c;我觉得很有意义&#xff0c;因为现在性能已经不是主要的限制了&#xff0c;很多时候讲究的快速开发。而且MAUIBlazor跨平台的未来感觉实在是太香了。…...

【Spring MVC】Spring MVC基于注解的程序开发

目录 一、什么是Spring MVC 二、Spring MVC项目的创建和使用 1、实现客户端和服务器端之间的连接 1.1、RequsestMapping注解 1.2、RequestMapper的简单使用 1.3、使用GetMapping和POSTMapping注解来实现HTTP连接 三、获取参数 1、实现获取单个参数 2、实现获取对象 3…...

前端探索之旅

目录 简介:内容大纲:第一章 前端开发简介1.1 前端开发的定义和作用1.2 前端开发的职责1.3 前端开发的技能要求1.4 前端开发的发展前景总结&#xff1a; 第二章 HTML基础2.1 HTML基本结构2.2 常见HTML标签和元素 第三章 CSS基础3.1 CSS基本语法3.2 常见CSS选择器3.3 常见CSS属性…...

“冰箭卫士·IP发布会”首次亮相第14届海峡两岸(厦门)文博会

2023年8月6日,“冰箭卫士IP发布会”首次亮相海峡两岸文博会思明馆。此次发布会由厦门市文化创意产业协会、厦门理工&#xff08;集美区&#xff09;政产学研基地主办&#xff0c;厦门市文化创意产业协会IP设计研究院、厦门一笔之上文化发展有限公司、冰箭应急安全科技研究院承办…...

数学建模学习(9):模拟退火算法

模拟退火算法(Simulated Annealing, SA)的思想借 鉴于固体的退火原理&#xff0c;当固体的温度很高的时候&#xff0c;内能比 较大&#xff0c;固体的内部粒子处于快速无序运动&#xff0c;当温度慢慢降 低的过程中&#xff0c;固体的内能减小&#xff0c;粒子的慢慢趋于有序&a…...

带你认识储存以及数据库新技术演进

01经典案例 1.0 潜在问题 02存储&数据库简介 2.1 存储器层级架构 2.1 数据怎么从应用到存储介质 2.1 RAID技术 2.2 数据库 数据库分为 关系型数据库 和 非关系型数据库 2.2.2 非关系型 2.2.1 关系型 2.3 数据库 vs 经典存储-结构化数据管理 2.3.1 数据库 vs 经典存储-事务能…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...