医院网站设计与实现,安全生产门户网站建设,彬县网站,大芬网站建设糊涂的教授
题目大意#xff1a;
有n个矩阵#xff08;有些部分重叠在一起#xff09;#xff0c;现在有一些位置写着一些数字#xff0c;表示它原来的序号#xff0c;问每一个矩阵原来的序号
原题#xff1a;
题目描述
陈教授是一个国际知名的教授#xff0c;很多…糊涂的教授
题目大意
有n个矩阵有些部分重叠在一起现在有一些位置写着一些数字表示它原来的序号问每一个矩阵原来的序号
原题
题目描述
陈教授是一个国际知名的教授很多单位都争先恐后邀请他演讲今天下午陈教授就要做一个非常重要的演讲。由于陈教授年纪大了对于一些不重要的小事情有点糊涂今天上午他把自己做演讲要用的幻灯片随便堆放在一起。因此演讲之前他不得不去整理这些幻灯片。由于时间很紧他希望尽可能简单地完成它。情况是这样陈教授这次演讲一共要用 n 张幻灯片n26这 n 张幻灯片按照演讲要使用的顺序已经用数字 12…n 在上面编上了号。因为幻灯片是透明的所以我们不能一下子看清每一个数字所对应的幻灯片。 现在我们用大写字母 ABC…再次把幻灯片依次编上号你的任务是编写一个程序把幻灯片的数字编号和字母编号对应起来显然这种对应应该是唯一的若是出现多种对应的情况或是某些数字编号和字母对应不起来我们就称对应是无法实现的。
输入
文件第一行只有一个数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输出样例
A 4
B 1
C 2
D 3解题思路
一个点在多少个矩阵之中为入读然后跑拓扑排序就可以了
代码
#includecstdio
#define max(a,b) (a)(b)?(a):(b)
using namespace std;
int n,k,p,num,ax,ay,x[30],xx[30],y[30],yy[30],l[30],pp[30],ans[30],a[30][30];
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d %d %d %d,x[i],xx[i],y[i],yy[i]);for (int i1;in;i){scanf(%d %d,ax,ay);for (int j1;jn;j)if (axx[j]axxx[j]ayy[j]ayyy[j])a[j][i]1,l[j];}kn;while (k){p0;for (int i1;in;i)if (l[i]1)//可以确定了{k--;p1;for (int j1;jn;j)if (a[i][j])//寻找连接的点{numj;break;}for (int j1;jn;j)if (a[j][num])//相连的点入度-1{a[j][num]0;l[j]--;}ans[i]num;//记录}if (!p){printf(None);break;}}if (p)for (int i1;in;i)printf(%c %d\n,i65-1,ans[i]);//输出
}
