COGS——T 438. 烦人的幻灯片

http://www.cogs.pro/cogs/problem/problem.php?pid=438

★☆ 输入文件：slides.in 输出文件：slides.out 简单对比
时间限制：1 s 内存限制：128 MB

【问题描述】

李教授将于今天下午作一次非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片(n≤26)，这n张幻灯片按照演讲要使用的顺序已经用数字l，2，…，n在上面编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母A，B，C，…再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是惟一的；若是出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们就称对应是无法实现的。

【输入格式】

幻灯片的情况通过一个文本文件slides.in输入。

文件的第1行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数Xmin，Xmax，Ymin，Ymax(整数之间用空格分开)为幻灯片的坐标，这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，…
再接下来的n行依次为n个数字编号的坐标x，y，显然在幻灯片之外是不会有数字的。

【输出格式】

要求将程序的运行结果写入一个名为slides.out的文本文件。若是对应可以实现，输出文件应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且各行以字母的升序排列，注意输出的字母要大写并且顶格；反之，若是对应无法实现，在文件的第1行顶格输出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

数据很水。。貌似随便写写就能过

 #include <cstring>

 #include <cstdio>

 int n,x,y,ans;

 struct Node

 {

     int xmax,xmin,ymax,ymin;

 }zm[];

 bool vis[];

 int rd[],match[],map[][];

 bool find(int u)

 {

     for(int v=;v<=n;v++)

         if(map[u][v]&&!vis[v])

         {

             vis[v]=;

             if(!match[v]||find(match[v]))

             {

                 match[v]=u;

                 return true;

             }

         }

     return false;

 }

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(;ch>''||ch<'';) ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';

 }

 int AC()

 {

     freopen("slides.in","r",stdin);

     freopen("slides.out","w",stdout);

     read(n);

     for(int i=;i<=n;i++)

         read(zm[i].xmin),read(zm[i].xmax),read(zm[i].ymin),read(zm[i].ymax);

     for(int i=;i<=n;i++)

     {

         read(x),read(y);

         for(int j=;j<=n;j++)

             if(zm[j].xmax>=x&&zm[j].xmin<=x&&zm[j].ymax>=y&&zm[j].ymin<=y)

                 map[i][j]=,rd[j]++;

     }

     for(int i=;i<=n;i++)

     {

         if(find(i)) ans++;

         memset(vis,,sizeof(vis));

     }

     bool flag=;

     for(int i=;i<=n;i++)

         if(rd[i]<) flag=;

     if(ans!=n||!flag) printf("None");

     else

     {

         for(int i=;i<=n;i++)

         {

             printf("%c ",'A'+i-);

             printf("%d\n",match[i]);

         }

     }

     return ;

 }

 int Hope=AC();

 int main(){;}

巴特西

COGS——T 438. 烦人的幻灯片

http://www.cogs.pro/cogs/problem/problem.php?pid=438

最新文章

热门文章