题解：SP3374 SCAVHUNT - Scavenger Hunt

__CrossBow_EXE__ · 2025-08-05 19:25:40 · 题解

题意

CEXE 有 n 个字符串，他给了你 n-1 个类似“字符串 x 的后面是字符串 y”的信息。他想让你按顺序输出所有字符串。

分析

楼下代码又臭又长，我来发一个简单的双 map 做法。

具体地，记一个 cnt 表示字符串出现的次数，一个 to 表示每个关系。不难发现起点和重点在给出的关系中只会出现一次，那我们遍历 cnt，结合“起点有后继”的条件找出起点，在根据 to 中记录的消息逐个输出即可。

稍微讲一下 map 的遍历。我们可以用 auto 类型的变量遍历一个 map，这样这个变量会变成一个 pair，这个 pair 的第一项表示键，第二项表示值。

代码

#include<bits/stdc++.h>
using namespace std;
#define up(_name_,_leftbound_,_rightbound_) for(auto _name_=(_leftbound_);(_name_)<=(_rightbound_);++(_name_))
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
map<string,int> cnt;
map<string,string> to;
string start;
void solve(int cases){
    cout<<"Scenario #"<<cases<<":"<<endl;
    cnt.clear();to.clear();
    n=read();
    up(i,1,n-1){
        string x,y;
        cin>>x>>y;
        cnt[x]++,cnt[y]++;
        to[x]=y;
    }
    for(auto x:cnt){
        if(x.second==1&&to.find(x.first)!=to.end()) start=x.first;
    }
    while(start!=""){
        cout<<start<<endl;
        start=to[start];
    }
    puts("");
    return;
}
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T=read();
    up(i,1,T) solve(i);
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/8/5 19:03:28
PROBLEM:SP3374
CODE BY __CrossBow_EXE__ Luogu uid967841
CEXE好闪，拜谢CEXE。
*/