网页美工培训哪里好,宁波seo平台,写wordpress导航栏,传奇类网页游戏排行榜烦人的幻灯片 烦人的幻灯片问题描述输入输出格式输入格式输出格式 输入输出样例输入样例#xff1a;输入样例一#xff1a;输入样例二#xff1a; 输出样例#xff1a;输出样例一#xff1a;输出样例二#xff1a; 正确做法拓扑排序 代码 烦人的幻灯片
问题描述
李教授… 烦人的幻灯片 烦人的幻灯片问题描述输入输出格式输入格式输出格式 输入输出样例输入样例输入样例一输入样例二 输出样例输出样例一输出样例二 正确做法拓扑排序 代码 烦人的幻灯片
问题描述
李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人他把自己做演讲要用的幻灯片随便堆放在一起。因此演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者他希望尽可能简单地完成它。情况是这样教授这次演讲一共要用n张幻灯片n≤26这n张幻灯片按照演讲要使用的顺序已经用数字12…n在上面编上了号。因为幻灯片是透明的所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母ABC。。。再次把幻灯片依次编上号如图如示我们可以很快发现编号为A的幻灯片是第4张把它抽出来后我们又可以确定编号为C的幻灯片是第2张。。。
你的任务是编写一个程序把幻灯片的数字编号和字母编号对应起来显然这种对应应该是唯一的若是出现多种对应的情况或是某些数字编号和字母对应不起来我们就称对应是无法实现的。
输入输出格式
输入格式
文件第一行只有一个数n表示有n张幻灯片接下来的n行第行包括4个整数XminXmaxYminYmax整数之间用空格分开为幻灯片的坐标这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为ABC。。。再接下来的n行依次为n个数字编号的坐标XY显然在幻灯片之外是不会有数字的。
输出格式
若是对应可以实现你的输出文件应该包括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进行排序的算法。在拓扑排序中图中的节点表示任务或事件有向边表示任务之间的依赖关系。拓扑排序的目标是找到一种排序方式使得所有任务都按照依赖关系的顺序被执行。
拓扑排序的步骤如下
初始化一个队列将所有入度为0的节点加入队列中。从队列中取出一个节点并将其输出。将该节点的所有邻接节点的入度减1。如果某个邻接节点的入度变为0将其加入队列中。重复步骤2-4直到队列为空。拓扑排序的过程可以理解为不断移除入度为0的节点并将其输出。如果图中存在环路则无法进行拓扑排序因为环路中的节点无法确定顺序。
拓扑排序的应用非常广泛例如任务调度、编译顺序、依赖关系分析等。它可以帮助我们理清任务之间的依赖关系确保任务按照正确的顺序执行避免出现循环依赖或执行顺序混乱的情况。
代码
#includebits/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 xx1xx2yy1yy2;
}
int main()
{cin n;for (int i1;in;i)cin p[i].x1 p[i].x2 p[i].y1 p[i].y2;for (int i1;in;i){cin d[i].x d[i].y;for (int j1;jn;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 k1;kn;k)for (int tmp0,i1;in;i)if (!o[i] d[i].b1){for (int j1;jn;j)if (tu[j][i]){tmpj;break;}z[tmp]i;for (int j1;jn;j)if (tu[tmp][j]){tu[tmp][j]0;d[j].b--;}l;break;}if (l!n){cout None;return 0;}for (int i1;in;i)cout char(64i) z[i] endl;return 0;
}
