题目分析

本题中 FBI 对犯罪分子藏身之处进行监视，已知犯罪分子数量 n 以及他们的用户 ID，同时有一系列关于人员进出（E、L）和消息拦截（M）的日志记录，目标是将犯罪分子姓名和用户 ID 进行匹配，若无法确定则显示 ???，且结果按犯罪分子姓名字母顺序输出。

算法标签

逻辑推理与匹配算法 枚举

解题思路读取输入：

读取犯罪分子数量 n 和用户 ID 列表，以及后续的日志记录。初始化数据结构：创建一个字典来存储犯罪分子姓名和对应的用户 ID，初始时所有用户 ID 都标记为 ???。处理日志记录：对于 E（进入）记录，将人员姓名记录下来，此时还无法确定其用户 ID。对于 L（离开）记录，由于在本题中离开记录本身并不能直接帮助确定用户 ID，所以可暂不做处理（或记录下离开人员姓名用于后续检查是否有未匹配的情况）。对于 M（消息拦截）记录，若当前藏身之处（可通过进入但未离开的人员姓名集合表示）中有人员姓名，且其用户 ID 尚未确定，则将该消息拦截的用户 ID 分配给该人员。如果藏身之处有多个人员姓名且用户 ID 尚未确定，这就需要结合其他日志记录进一步分析，比如后续是否有新的消息拦截记录来明确具体匹配关系。检查未匹配情况：遍历所有犯罪分子姓名，若其用户 ID 仍为 ???，则保持不变。排序输出：将存储犯罪分子姓名和用户 ID 的字典按犯罪分子姓名进行排序，然后按要求格式输出每个犯罪分子姓名及其对应的用户 ID。

代码实现步骤（c++）

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
using namespace std;
struct node
{
    string x,y;
}save[22];

map<string,int> g;
string sg[22];
map<string,int> g1;
int n;
int cnt;

int mark[22];
int map1[22][22];
int pre[22];

int dfs(int s)
{
    for(int i=1;i<=n;i++)
    {
        if( mark[i]==1 || map1[s][i]==0 ) continue;
        mark[i]=1;
        if( pre[i]==-1 || dfs(pre[i])==1)
        {
            pre[i]=s;
            return 1;
        }
    }
    return 0;
}

int xyl()
{
    int sum=0;
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=n;i++)
    {
        memset(mark,0,sizeof(mark));
        sum += dfs(i);
    }
    return sum;
}

int cmp(node t,node t1)
{
    return t.x < t1.x;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        string tmp;
        cin>>tmp;
        g[tmp]=i;
        sg[i]=tmp;
    }
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            map1[i][j]=1;
    int cnt=1;
    char key;
    while(cin>>key&&key!='Q')
    {
        string tmp;
        cin>>tmp;
        if( key=='E' )
        {
            if( g1[tmp]==0 ) g1[tmp] = cnt++;
            mark[ g1[tmp] ]=1;
            //sg1[ g1[tmp] ]=tmp;
            save[ g1[tmp] ].x=tmp;
            save[ g1[tmp] ].y="???";
            continue;
        }
        if(key=='M')
        {
            for(int i=1;i<=n;i++)
            {
                if( mark[i]==0 )
                {
                    map1[i][ g[tmp] ]=0;
                }
            }
            continue;
        }
        if(key=='L')
        {
            if( g1[tmp]==0 ) g1[tmp]=cnt++;
            mark[ g1[tmp] ] = 0;
            //sg[ g1[tmp] ]=tmp;
            save[ g1[tmp] ].x=tmp;
            save[ g1[tmp] ].y="???";
            continue;
        }
    }
        int sum = xyl();
        int tpre[22];
        for(int i=1;i<=n;i++)
            tpre[i]=pre[i];
        for(int j=1;j<=n;j++)
        {
            int i=tpre[j];
            map1[i][j]=0;
            if( xyl() != sum )
            {
                save[i].y = sg[j];
            }
            map1[i][j]=1;
        }
        sort(save+1,save+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            cout<<save[i].x<<":"<<save[i].y<<endl;
        }
    return 0;
}