首页 > > 程序设计 > C/C++ >

SID1190471 / 烦人的幻灯片暴力出奇迹！！！…

2018-06-17 22:48:30来源：未知阅读 ()

PID221 / 烦人的幻灯片 ☆

提交你的代码
查看讨论和题解

题目描述

李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己做演讲要用的幻灯片随便堆放在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。情况是这样，教授这次演讲一共要用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

输出

A4
B1
C2
D3
暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹暴力出奇迹、】

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 struct node
 6 {
 7     int xmin;
 8     int xmax;
 9     int ymin;
10     int ymax;
11     int vis;
12     int bj;
13 }a[1001];
14 struct zb
15 {
16     int x;
17     int y;
18     int vis;
19     int bj;
20 }b[1001];
21 int n;
22 int flag=0;
23 char hh='A';
24 int ans[1001];
25 void dfs(int p)
26 {
27     if(p==n+1)
28     {
29         if(flag==0)
30         {
31             for(int i=1;i<=n;i++)
32             {
33                 ans[i]=a[i].bj;
34             }
35             flag=1;
36         }
37         else 
38         {
39             for(int i=1;i<=n;i++)
40             {
41                 if(a[i].bj!=ans[i])
42                 {
43                     printf("None");
44                     flag=2;
45                     return;
46                 }
47             }
48         }
49         
50         /*for(int i=1;i<=n;i++)
51         printf("%c %d\n",hh,a[i].bj);
52         flag=1;
53         return;*/
54     }
55     for(int j=1;j<=n;j++)
56         {
57             if(a[j].vis==0)
58             {
59                 for(int k=1;k<=n;k++)
60                 {
61                     if(a[j].xmin<b[k].x&&a[j].xmax>b[k].x&&a[j].ymin<b[k].y&&a[j].ymax>b[k].y&&b[k].vis==0)
62                     {
63                         a[j].vis=1;
64                         b[k].vis=1;
65                         a[j].bj=k;
66                         dfs(p+1);
67                         if(flag==2)return;    
68                         b[k].vis=0;
69                         a[j].vis=0;
70                     }
71                 }
72                 
73             }
74             
75         }
76 }
77 int main()
78 {
79     
80     scanf("%d",&n);
81     for(int i=1;i<=n;i++)
82         scanf("%d%d%d%d",&a[i].xmin,&a[i].xmax,&a[i].ymin,&a[i].ymax);
83     for(int i=1;i<=n;i++)
84         scanf("%d%d",&b[i].x,&b[i].y);
85     dfs(1);
86     if(flag==1)
87     for(int i=1;i<=n;i++)
88     {
89         printf("%c%d\n",hh++,ans[i]);
90     }
91     return 0;
92     
93 }