题解：P13915 [PO Final 2024] 鬼抓人 / Tag

· · 题解

简单模拟。只需要弄清楚三个点：

  1. 人被抓后会认为自己是鬼。
  2. 鬼抓过人后知道自己不是鬼。
  3. 只有知道自己不是鬼的人去抓人才算作弊。

开一个数组记录每个人所认为的状态，按时间顺序模拟整个过程就好了。用 Trie 存每个人的名字的下标。

# include <bits/stdc++.h>

using namespace std;

string name[200004];
bool is[200004];
int cnt=1;

struct Trie
{
    int id;
    struct Trie* s[27];
};

struct Trie* t;

struct Trie* ini()
{
    struct Trie* tmp = (struct Trie*) malloc (sizeof (struct Trie));
    for(int i = 0; i < 27; i++)
    {
        tmp->s[i] = NULL;
    }   
    tmp->id = -1;
    return tmp;
}

void add(struct Trie* node,string s,int idx)
{   

    if (idx >= s.size())
    {
        node->id = cnt++;
        return ;
    }
    int c = s[idx]-'a';
    if (node->s[c] == NULL) node->s[c] = ini();
    add(node->s[c],s,idx+1);
    return ;
}

int getid(struct Trie* node,char s[],int idx)
{
    if (idx >= strlen(s))
    {
        return node->id;
    }
    return getid(node->s[s[idx]-'a'],s,idx+1);
}

int tot;
string ans[200004];
int chk[200004];

int main (void)
{
    int n,m;
    scanf ("%d %d",&n,&m);

    t = ini();
    for (int i=1;i<=n;i++)
    {
        cin >> name[i]; 
        add(t,name[i],0);
    }

    is[1] = 1;
    for (int i=1;i<=m;i++)
    {
        char s1[25],s2[25],s3[25];
        scanf ("%s %s %s",s1,s2,s3);
        int i1=getid(t,s1,0);
        int i2=getid(t,s3,0); 
        if (!is[i1] && !chk[i1])
        {
            ans[tot++] = name[i1];
            chk[i1] = 1;
        }
        is[i1]=0; 
        is[i2]=1;
    }

    printf ("%d\n",tot);
    sort(ans,ans+tot); 
    for (int i=0;i<tot;i++)
    {
        cout << ans[i] << ' ';
    }
    return 0;
}