首页 > 代码库 > 4735 烦人的幻灯片 （拓扑）
4735 烦人的幻灯片 （拓扑）
4735 烦人的幻灯片
时间限制: 2 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
帅气的作者将于今天下午作一次非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的oier，他希望尽可能简单地完成它。帅气的作者这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1~n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。 现在我们用大写字母A,B,C……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。
输入描述 Input Description
文件的第一行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数xmin,xmax,ymin,ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在文件中出现的顺序从前到后依次编号为A,B,C……，再接下来的n行依次为n个数字编号的坐标x,y，显然在幻灯片之外是不会有数字的。
输出描述 Output Description
若是对应可以实现，输出文件应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。首行末无多余的空格。
样例输入 Sample Input
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
样例输出 Sample Output
A 4
B 1
C 2
D 3
数据范围及提示 Data Size & Hint
1 #include<iostream> 2 using namespace std; 3 #define N 110 4 5 int h,z; //横坐标，及纵坐标 6 int n; 7 int stack[N],head; //栈 8 int map[N][N]; 9 struct picture{10 picture() //初始化 11 {12 top=ans=0;13 }14 int x,xx; //Xmin，Xmax，15 int y,yy; //Ymin，Ymax16 int top; //表示一张幻灯片有几组数字其对应 17 void add() //添加一组数字坐标与幻灯片对应 18 {19 top++;20 }21 void reduce() //减少与幻灯片对应的数字坐标 22 {23 top--;24 }25 int ans; //表示幻灯片对应的数字 26 }pi[N];27 void in_() //输入 28 {29 cin>>n;30 for(int i=1;i<=n;++i)31 {32 cin>>pi[i].x>>pi[i].xx>>pi[i].y>>pi[i].yy;33 }34 for(int i=1;i<=n;++i)35 {36 cin>>h>>z;37 for(int j=1;j<=n;++j) //遍历一遍数字是否可能在幻灯片上38 {39 if(h>=pi[j].x&&h<=pi[j].xx&&z>=pi[j].y&&z<=pi[j].yy)40 {41 pi[j].add(); //一张幻灯片可能有几组数字 42 map[j][i]=1; //标记 43 }44 }45 }46 }47 bool topo_() //拓扑 48 {49 for(int i=1;i<=n;++i)50 {51 if(pi[i].top==0)return false ; //若没有与幻灯片对应的；返回0； 52 if(pi[i].top==1)53 {54 stack[++head]=i;55 }56 }57 if(head==0)return false ; //若没有，只有一组数字，与幻灯片对应的幻灯片，返回0； 58 while(head!=0)59 {60 int d=stack[head]; 61 head--; 62 for(int i=1;i<=n;++i)63 {64 if(map[d][i]==1) 65 pi[d].ans=i; //记下答案 66 }67 for(int i=1;i<=n;++i)68 {69 if(map[i][pi[d].ans]==1)70 {71 map[i][pi[d].ans]=0; 72 pi[i].reduce();73 if(pi[i].top==1)stack[++head]=i; //再找再入栈 74 }75 }76 }77 for(int i=1;i<n;++i)78 if(pi[i].ans==0)return false;79 return true;80 }81 void out_() //输出 82 {83 for(int i=1;i<=n;++i)84 cout<<char(i+64)<<pi[i].ans<<endl; //强制类型转换输出 85 }86 int main()87 {88 in_();89 if(topo_())out_();90 else cout<<"None";91 return 0;92 }
4735 烦人的幻灯片 （拓扑）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。