【题目描述】
Bessie正在申请计算机科学的研究生,并取得了一所久负盛名的计算机科学实验室的面试通知。
然而,为了避免冒犯任何人,Bessie有意先确定实验室的
N
N
N
名现有成员的相对资历。
没有两名实验室成员的资历相同,但确定他们的资历深浅可能并不好办。
为此,Bessie将会对实验室的出版物进行调查。
每份出版物均包含一个作者列表,为所有
N
N
N
名实验室成员的一个排列。
列表按每名实验室成员对这篇文章的贡献
降序
排列。
如果多名研究员的贡献相等,则按
字典序
排列。
由于更有资历的实验室成员负有更多的管理责任,更有资历的研究员从不会比资历较浅的研究员做出更多的贡献。
例如,在一个由资历较浅的学生Elsie、资历较深的教授Mildred、以及十分资深的教授Dean组成的实验室中,可能存在一篇论文Elsie-Mildred-Dean,如果他们做出了不等的贡献(也就是说,Elsie做出的贡献比Mildred更多,Mildred比Dean更多)。
然而,也有可能存在一篇论文Elsie-Dean-Mildred,如果Mildred和Dean做出了相等的贡献,而Elsie做出了更多的贡献。
给定实验室的
K
K
K
份出版物,对于实验室中每对研究员,如果可能的话帮助Bessie判断其中谁的资历更深。
【输入格式】
输入的第一行包含两个整数
K
K
K
和
N
N
N
。
第二行包含
N
N
N
个空格分隔的字符串,为实验室的成员的名字。每个字符串均由小写字母组成,且至多包含
10
10
10
个字符。
以下
K
K
K
行,每行包含
N
N
N
个空格分隔的字符串,表示一份出版物的作者列表。
【输出格式】
输出
N
N
N
行,每行
N
N
N
个字符。在第
i
i
i
行内,对于所有
j
≠
i
j≠i
j
=
i
,当可以确定第
i
i
i
名成员比第
j
j
j
名成员资历更深时字符
j
j
j
为
1
1
1
,当可以确定第
i
i
i
名成员比第
j
j
j
名成员资历更浅时字符
j
j
j
为
0
0
0
,当不能由给定的出版物确定时为
?
。
第
i
i
i
行的字符
i
i
i
应为
B
,因为这是Bessie最喜欢的字母。
【数据范围】
1
≤
N
,
K
≤
100
1≤N,K≤100
1
≤
N
,
K
≤
100
【输入样例1】
1 3
dean elsie mildred
elsie mildred dean
【输出样例1】
B11
0B?
0?B
【样例1解释】
在这个样例中,单独一份论文elsie-mildred-dean并不能提供足够的信息判断Elsie比Mildred资历更深或更浅。
然而,我们可以推断出Dean一定比这两名研究员资历更深,从而资历排序为Elsie<Mildred<Dean和Mildred<Elsie<Dean均是可能的。
【输入样例2】
2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred
【输出样例2】
B00
1B0
11B
【样例2解释】
在这个样例中,唯一能与两篇论文相一致的资历排序为Elsie<Mildred<Dean,这是因为基于第一个样例所提供的信息,第二篇论文可以帮助我们推断出Mildred比Elsie的资历更深。
【分析】
假设
a
a
a
和
b
b
b
的资历分别为
E
a
E_a
E
a
和
E
b
E_b
E
b
,贡献分别为
C
a
C_a
C
a
和
C
b
C_b
C
b
,若能确定
E
a
<
E
b
E_a<E_b
E
a
<
E
b
,则一定满足
C
a
>
C
b
C_a>C_b
C
a
>
C
b
,即在论文中
a
a
a
的名字出现在
b
b
b
的前面,且
a
a
a
到
b
b
b
之间的名字不是全按字典序升序排列。
因此我们可以遍历论文的每个名字
i
i
i
,在
i
i
i
的后面找到第一个字典序降序的名字
j
j
j
,那么
j
j
j
及其之后的所有人资历都严格高于
i
i
i
。
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
const int N = 110;
int g[N][N];//g[a][b] = 1表示a的资历比b高
int n, m;
unordered_map<string, int> id;
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
id[s] = i;
}
string name[N];
while (m--)
{
for (int i = 0; i < n; i++) cin >> name[i];
for (int i = 0; i < n; i++)
{
int j = i + 1;
while (j < n && name[j] > name[j - 1]) j++;//找到第一个降序的名字
while (j < n)//j之后的所有人资历都严格比i高
{
int a = id[name[i]], b = id[name[j]];
g[b][a] = 1;
j++;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
if (i == j) cout << 'B';
else if (!g[i][j] && !g[j][i]) cout << '?';
else cout << g[i][j];
cout << endl;
}
return 0;
}