题目传送门

题目大意

根据经过贡献值和字典序排列后的字符串确定资历深浅，贡献值大的资历浅。

思路

• 利用 STL 中的 map 容器将姓名作为下标存储贡献值的优先级（STL 容器不熟的点这）。
• 定义一个二维数组，存储 $n_i$ 与 $n_j$ 的大小关系，优先级高的为 $1$，低的为 $0$​。
• 具体实现详见代码注释。

代码实现

//改自Yulicezzz的代码
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp> 
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int MAXN=1e5+7;
map<string,int>name;
string s[MAXN];
int mp[1005][1005];
int n,m;
signed main()         
{     
    cin>>m>>n;//按题意输入
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        name[s[i]]=i;//map存储优先级
    }
    while(m--)
    {
        int l=1;//记录上一个级别的最后一个位置
        s[0]='z'+25;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            if(s[i]<s[i-1])
            {
                l=i;//更新
            }
            for(int j=1;j<l;j++)
            {
                mp[name[s[j]]][name[s[i]]]=-1;//根据优先级存入数组
                mp[name[s[i]]][name[s[j]]]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
                mp[i][j]==1?cout<<"1":mp[i][j]==-1?cout<<"0":cout<<"?";//输出矩阵
            else
                cout<<"B";//如果 i=j 则输出 B
        }
        puts("");
    }
    return 0;
}

时间复杂度

约 $O(m ⋅ n^2)$。