1395：烦人的幻灯片(slides)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
李教授将于今天下午作一次非常重要的演讲。不幸的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1~n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母A,B,C……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。
【输入】
第一行只有一个整数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
【输出样例】
A 4
B 1
C 2
D 3
1. #include <bits/stdc++.h> 2. using namespace std; 3. int n; 4. struct nod{ 5. int x1, y1, x2, y2; // 节点结构体，记录框区间的坐标信息 6. } nods[30]; 7. struct Slide{ 8. char c; // 存储字符编号 9. int id; // 存储对应的数字编号 10. bool operator<(const Slide a) const{ 11. return c< a.c; // 用于排序的较运算符 12. } 13. }; 14. vector<int> v[30]; // 存储每个区间可能相交的点的编号 15. set<int> st[30]; // set 是为了方便删除，存储每个点可能属于的区间编号 16. vector<Slide> ans; // 存储最终的结果 17. bool Solve(){ 18. queue<int> q; 19. for(int i = 1;i <= n; i++) 20. if(st[i].size() == 1) q.push(i); // 将只有一个相邻节点的点入队 21. while(!q.empty()){ 22. int t = q.front(); // 当前节点 23. q.pop(); 24. int u = *st[t].begin(); // 相邻节点 25. st[t].clear(); // 清除当前节点的相邻节点集合 26. ans.push_back({u + 'A' - 1, t}); // 添加当前节点和相邻节点到结果中 27. for(auto it : v[u]){ 28. st[it].erase(u); // 删除相邻节点的连接 29. if(st[it].size() == 1) q.push(it); // 如果相邻节点只有一个连接，将其入队 30. } 31. } 32. return (ans.size() == n); // 判断是否找到了符合条件的解 33. } 34. int main() 35. { 36. cin >> n; // 输入区间数量 37. for(int i = 1; i <= n; i++) 38. cin >> nods[i].x1 >> nods[i].x2 >> nods[i].y1 >> nods[i].y2; // 输入每个区间的坐标信息 39. for(int i = 1, x, y; i <= n; i++){ 40. cin >> x >> y; // 输入坐标 41. for(int j = 1; j <= n; j++){ 42. if(x >= nods[j].x1 && x <= nods[j].x2 && y >= nods[j].y1 && y <= nods[j].y2){ 43. v[j].push_back(i); // 将点与区间进行连接 44. st[i].insert(j); // 记录点与相邻区间的关系 45. } 46. } 47. } 48. if(Solve()){ // 如果有解 49. sort(ans.begin(), ans.end()); // 对结果进行排序 50. for(auto a : ans) 51. cout << a.c << " " << a.id << endl; // 输出结果 52. } 53. else 54. cout << "None"; // 没有找到符合条件的解 55. return 0; 56. }
