AcWing 3746. 牛的学术圈 II（思维题）

【题目描述】
Bessie正在申请计算机科学的研究生，并取得了一所久负盛名的计算机科学实验室的面试通知。
然而，为了避免冒犯任何人，Bessie有意先确定实验室的$N$名现有成员的相对资历。
没有两名实验室成员的资历相同，但确定他们的资历深浅可能并不好办。
为此，Bessie将会对实验室的出版物进行调查。
每份出版物均包含一个作者列表，为所有$N$名实验室成员的一个排列。
列表按每名实验室成员对这篇文章的贡献降序排列。
如果多名研究员的贡献相等，则按字典序排列。
由于更有资历的实验室成员负有更多的管理责任，更有资历的研究员从不会比资历较浅的研究员做出更多的贡献。
例如，在一个由资历较浅的学生Elsie、资历较深的教授Mildred、以及十分资深的教授Dean组成的实验室中，可能存在一篇论文Elsie-Mildred-Dean，如果他们做出了不等的贡献（也就是说，Elsie做出的贡献比Mildred更多，Mildred比Dean更多）。
然而，也有可能存在一篇论文Elsie-Dean-Mildred，如果Mildred和Dean做出了相等的贡献，而Elsie做出了更多的贡献。
给定实验室的$K$份出版物，对于实验室中每对研究员，如果可能的话帮助Bessie判断其中谁的资历更深。

【输入格式】
输入的第一行包含两个整数$K$和$N$。
第二行包含$N$个空格分隔的字符串，为实验室的成员的名字。每个字符串均由小写字母组成，且至多包含$10$个字符。
以下$K$行，每行包含$N$个空格分隔的字符串，表示一份出版物的作者列表。

【输出格式】
输出$N$行，每行$N$个字符。在第$i$行内，对于所有$j\ne i$，当可以确定第$i$名成员比第$j$名成员资历更深时字符$j$为$1$，当可以确定第$i$名成员比第$j$名成员资历更浅时字符$j$为$0$，当不能由给定的出版物确定时为?。
第$i$行的字符$i$应为B，因为这是Bessie最喜欢的字母。

【数据范围】
$1\le N,K\le 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$和$b$的资历分别为$E_a$和$E_b$，贡献分别为$C_a$和$C_b$，若能确定$E_a<E_b$，则一定满足$C_a>C_b$，即在论文中$a$的名字出现在$b$的前面，且$a$到$b$之间的名字不是全按字典序升序排列。

因此我们可以遍历论文的每个名字$i$，在$i$的后面找到第一个字典序降序的名字$j$，那么$j$及其之后的所有人资历都严格高于$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;
}