题解：P9938 [USACO21OPEN] Acowdemia II B

首先根据每篇出版物构建一个资历比较矩阵 \(g\)，其中 \(g_{a,b} = 1\) 表示研究员 \(a\) 比 \(b\) 资历更高。

遍历每篇出版物，识别出第一个降序的名字，然后假定该名字之后的所有研究员资历都比当前名字对应的研究员资历高即可。

代码：

#include<bits/stdc++.h>
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;
}