题解：P9938 [USACO21OPEN] Acowdemia II B

· · 题解

前言

题目传送门

思路

这道题算是一道挺简单的模拟了。

我们用一个数组 ans 来存储答案，在刚开始的时候，把数组初始化为 ?，然后在开始做题。

对于每一篇论文的作者列表中，不难发现，当这一次输入的名字的字典序，小于前一个名字的字典序时，前面所有人的贡献都会比这个人大，所以，这个人的资历比前面任何一个人的资历要深，所以这个时候我们把这个人处于输入的第几个数设为 i，把第 1 个到这个人前面的那个人，用 j 循环，所以，当这样时，ans _ {i , j} = 1 且 ans _ {j , i} = 0。

当这个人的字典序大于前一个人的字典序时，就要往前找到最后一次字典序小于前一个字典序，把这个位置标记为 t，从 1 循环到 t 在这之间的全部都没最开始那个人的资历深。

代码

#include<bits/stdc++.h>
using namespace std;
char ans[101][101];
map<string,int>mp;
int main()
{
    int k,n;
    cin>>k>>n;
    for(int i=1;i<=n;i++)
    {
        string str;
        cin>>str;
        mp[str]=i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans[i][j]='?';
        }
    }
    while(k--)
    {
        string str[101];
        for(int i=1;i<=n;i++)
        {
            cin>>str[i];
        }
        for(int i=2;i<=n;i++)
        {
            if(str[i]<str[i-1])
            {
                for(int j=1;j<=i-1;j++)
                {
                    if(ans[mp[str[i]]][mp[str[j]]]=='?')
                    {
                        ans[mp[str[i]]][mp[str[j]]]='1';
                    }
                    if(ans[mp[str[j]]][mp[str[i]]]=='?')
                    {
                        ans[mp[str[j]]][mp[str[i]]]='0';
                    }
                }
            }
            else
            {
                int t=i;
                while(str[t]>str[t-1])
                {
                    t--;
                }
                t--;
                for(int j=1;j<=t;j++)
                {
                    if(ans[mp[str[i]]][mp[str[j]]]=='?')
                    {
                        ans[mp[str[i]]][mp[str[j]]]='1';
                    }
                    if(ans[mp[str[j]]][mp[str[i]]]=='?')
                    {
                        ans[mp[str[j]]][mp[str[i]]]='0';
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            {
                cout<<"B";
            }
            else
            {
                cout<<ans[i][j];
            }
        }
        cout<<endl;
    }
    return 0;
}