本文共 19602 字，大约阅读时间需要 65 分钟。

L1-064 估值一亿的AI核心代码 (20分)

题意：按题意处理字符串

思路：有空格的处理，要好好讨论清楚。然后就是 “I”、“you” 互换的处理

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int q;string s;void solve(string& s,string s1,string s2){
       int len=s1.size();    for(int p=0;; ++p)    {
           p=s.find(s1,p);        if(p==-1) break;        if((p==0||!isalnum(s[p-1]))&&(p+len==s.size()||!isalnum(s[p+len])))            s.replace(p,len,s2);    }}int main(){
       cin>>q;    getchar();    while(q--)    {
           getline(cin,s);        cout<<s<<"\n";        while(s[0]==' ') s.erase(s.begin());        while(s[s.size()-1]==' ') s.erase(s.end()-1);        for(int i=0; i<s.size(); ++i)        {
               if(s[i]==' ')            {
                   while(s[i+1]==' ') s.erase(s.begin()+i+1);                if(!isalnum(s[i+1])) s.erase(s.begin()+i);            }        }        for(int i=0; i<s.size(); ++i)            if(s[i]>='A'&&s[i]<='Z'&&s[i]!='I') s[i]=s[i]-'A'+'a';        solve(s,"can you","X can");        solve(s,"could you","X could");        solve(s,"I","you");        solve(s,"me","you");        for(int i=0; i<s.size(); ++i)        {
               if(s[i]=='?') s[i]='!';            if(s[i]=='X') s[i]='I';        }        cout<<"AI: "<<s<<"\n";    }    return 0;}

L2-001 紧急救援 (25分)

题意：给定一个 n 个点 m 条边的无向图。给定起点 s 和终点 d 。无向图带有点权和边权。请你输出，从 s 到 d 的最短路径数、最短路中最大的点权和，从 s 到 d 的路径。

思路：最短路模板题。用 path 记录路径数，dis 记录最短路，maxval 记录从 s 到当前点的最大点权和，pre 记录路径

#include <bits/stdc++.h>#define fi first#define se second#define ll long longusing namespace std;const int maxn=500+5,inf=1e9;int n,m,s,d;int dis[maxn],path[maxn],val[maxn],maxval[maxn];int visit[maxn],pre[maxn];vector<pair<int,int> > e[maxn];void dijstra(){
       for(int i=1; i<=n; ++i) dis[i]=inf,visit[i]=0,pre[i]=-1;    maxval[s]=val[s];    dis[s]=0;    path[s]=1;    priority_queue<pair<int,int> > pq;    pq.push({
   0,s});    while(!pq.empty())    {
           auto t=pq.top();        pq.pop();        int u=t.se;        if(visit[u]) continue;        visit[u]=1;        for(auto x: e[u])        {
               int v=x.fi,w=x.se;            if(dis[u]+w<dis[v])            {
                   dis[v]=dis[u]+w;                path[v]=path[u];                maxval[v]=maxval[u]+val[v];                pre[v]=u;                pq.push({
   -dis[v],v});            }            else if(dis[u]+w==dis[v])            {
                   path[v]+=path[u];                if(maxval[v]<maxval[u]+val[v])                {
                       maxval[v]=maxval[u]+val[v];                    pre[v]=u;                }            }        }    }}int main(){
       scanf("%d%d%d%d",&n,&m,&s,&d);    s++,d++;    for(int i=1; i<=n; ++i) scanf("%d",&val[i]);    for(int i=1; i<=m; ++i)    {
           int u,v,w;        scanf("%d%d%d",&u,&v,&w);        u++,v++;        e[u].push_back({
   v,w});        e[v].push_back({
   u,w});    }    dijstra();    printf("%d %d\n",path[d],maxval[d]);    vector<int> ans;    for(int i=d; i!=-1; i=pre[i]) ans.push_back(i);    reverse(ans.begin(),ans.end());    int m=ans.size();    for(int i=1; i<=m; ++i) printf("%d%c",ans[i-1]-1,i==m?'\n':' ');    return 0;}

L2-002 链表去重 (25分)

L2-004 这是二叉搜索树吗？ (25分) （二叉搜索树：前序遍历建树）

题意：给定一棵二叉搜索树或者其镜像前序遍历的结果。问这 n 个点是否符合一棵二叉搜索树的特性。$(1\le n\le 1000)$

思路：递归建树之后，后序遍历，如果有 n 个点都在，那么就说明合法。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1010+5;int n;int val[maxn];vector<int> ans;struct Node{
       int val;    Node *ls,*rs;};Node* solve1(int l,int r){
       if(l>r) return NULL;    int l1=l+1,r1=r;    while(l1<=r&&val[l1]<val[l]) l1++;    while(r1>=l+1&&val[r1]>=val[l]) r1--;    if(l1!=r1+1) return NULL;    Node* node=new Node;    node->val=val[l];    node->ls=solve1(l+1,r1);    node->rs=solve1(l1,r);    return node;}Node* solve2(int l,int r){
       if(l>r) return NULL;    int l1=l+1,r1=r;    while(l1<=r&&val[l1]>=val[l]) l1++;    while(r1>=l+1&&val[r1]<val[l]) r1--;    if(l1!=r1+1) return NULL;    Node* node=new Node;    node->val=val[l];    node->ls=solve2(l+1,r1);    node->rs=solve2(l1,r);    return node;}void dfs(Node* root){
       if(root==NULL) return;    dfs(root->ls);    dfs(root->rs);    ans.push_back(root->val);}void print(){
       puts("YES");    for(int i=1; i<=n; ++i) printf("%d%c",ans[i-1],i==n?'\n':' ');}int main(){
       scanf("%d",&n);    for(int i=1; i<=n; ++i) scanf("%d",&val[i]);    Node* root=solve1(1,n);    dfs(root);    if(ans.size()==n) print();    else    {
           ans.clear();        root=solve2(1,n);        dfs(root);        if(ans.size()==n) print();        else puts("NO");    }    return 0;}

L2-006 树的遍历 (25分) （二叉树：后序 + 中序 建树）

题意：给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n;int a[maxn],b[maxn];struct Node{
       int val;    Node* ls,*rs;};Node* solve(int l1,int r1,int l2,int r2){
       if(l1>r1) return NULL;    if(l1==r1)    {
           Node* node=new Node;        node->val=a[l1];        node->ls=NULL;        node->rs=NULL;        return node;    }    int pos;    for(pos=l1; pos<=r1; ++pos)        if(a[pos]==b[r2]) break;    int len1=pos-1-l1+1;    int len2=r1-(pos+1)+1;    Node* node=new Node;    node->val=a[pos];    node->ls=solve(l1,pos-1,l2,l2+len1-1);    node->rs=solve(pos+1,r1,l2+len1,r2-1);    return node;}vector<int> ans;void bfs(Node* root){
       queue<Node*> q;    q.push(root);    while(!q.empty())    {
           Node* node=q.front();        q.pop();        if(node==NULL) continue;        ans.push_back(node->val);        q.push(node->ls);        q.push(node->rs);    }}int main(){
       scanf("%d",&n);    for(int i=1; i<=n; ++i) scanf("%d",&b[i]);    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);    Node* root=solve(1,n,1,n);    bfs(root);    n=ans.size();    for(int i=1; i<=n; ++i) printf("%d%c",ans[i-1],i==n?'\n':' ');    return 0;}

L2-007 家庭房产 (25分) （并查集维护）

题意：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

思路：并查集维护信息，包括家庭人口数、家庭总房产面积、家庭房产总套数

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n;struct Node{
       int pa,st,tot,sz;} p[maxn];int visit[maxn];struct Node2{
       int id;    int peo;    double st;    double area;    bool operator<(const Node2& b) const    {
           if(area==b.area) return id<b.id;        return area>b.area;    }};int find(int x){
       return p[x].pa==x?x:p[x].pa=find(p[x].pa);}void merge(int u,int v){
       int ru=find(u),rv=find(v);    if(ru!=rv)    {
           if(ru<rv) swap(ru,rv);        p[ru].pa=rv;        p[rv].sz+=p[ru].sz;        p[rv].st+=p[ru].st;        p[rv].tot+=p[ru].tot;    }}int main(){
       for(int i=0; i<maxn; ++i)    {
           p[i].pa=i;        p[i].sz=1;        p[i].st=0;        p[i].tot=0;    }    scanf("%d",&n);    for(int i=1; i<=n; ++i)    {
           int id,fa,mo,k;        scanf("%d%d%d%d",&id,&fa,&mo,&k);        visit[id]=1;        if(fa!=-1) merge(id,fa),visit[fa]=1;        if(mo!=-1) merge(id,mo),visit[mo]=1;        for(int j=1; j<=k; ++j)        {
               int x;            scanf("%d",&x);            visit[x]=1;            merge(id,x);        }        int ru=find(id);        int a,b;        scanf("%d%d",&a,&b);        p[ru].st+=a;        p[ru].tot+=b;    }    vector<Node2> ans;    for(int i=0; i<maxn; ++i)        if(p[i].pa==i&&visit[i])        {
               ans.push_back({
   i,p[i].sz,1.0*p[i].st/p[i].sz,1.0*p[i].tot/p[i].sz});        }    sort(ans.begin(),ans.end());    printf("%d\n",ans.size());    for(auto x: ans)        printf("%04d %d %.3lf %.3lf\n",x.id,x.peo,x.st,x.area);    return 0;}

L2-008 最长对称子串 (25分) （Manachar模板）

题意：对给定的字符串，本题要求你输出最长对称子串的长度。

思路：Manachar模板题

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int Manachar(string s){
       int n=s.size();    s.resize(2*n+3);    vector<int> len(2*n+3,0);    for(int i=n-1; i>=0; --i)    {
           s[2*i+2]=s[i];        s[2*i+3]='#';    }    s[0]='$',s[1]='#',s[2*n+2]='@';    int ans=-1,mid,r=0;    for(int i=1; i<=2*n+1; ++i)    {
           if(r>i) len[i]=min(len[2*mid-i],r-i);        else len[i]=1;        while(s[i-len[i]]==s[i+len[i]]) len[i]++;        if(i+len[i]>r) r=i+len[i],mid=i;        ans=max(ans,len[i]-1);    }    return ans;}string s;int main(){
       getline(cin,s);    int ans=Manachar(s);    cout<<ans<<"\n";    return 0;}

L2-010 排座位 (25分) （并查集 + 两个关系的判断）

题意：布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

思路： 根据输入输出的要求，处理四种关系。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=110;int n,m,k;int pa[maxn],mp[maxn][maxn];int find(int x){
       return pa[x]==x?x:pa[x]=find(pa[x]);}void merge(int u,int v){
       int ru=find(u),rv=find(v);    if(ru!=rv) pa[ru]=rv;}int main(){
       cin>>n>>m>>k;    for(int i=1; i<=n; ++i) pa[i]=i;    for(int i=1; i<=m; ++i)    {
           int u,v,w;        cin>>u>>v>>w;        mp[u][v]=mp[v][u]=w;        if(w==1) merge(u,v);    }    while(k--)    {
           int u,v;        cin>>u>>v;        int ru=find(u),rv=find(v);        if(mp[u][v]==1&&ru==rv) puts("No problem");        else if(mp[u][v]==0&&ru!=rv) puts("OK");        else if(mp[u][v]==-1&&ru==rv) puts("OK but...");        else if(mp[u][v]==-1&&ru!=rv) puts("No way");    }    return 0;}

L2-011 玩转二叉树 (25分) （二叉树：中序遍历 + 前序遍历 建树）

题意： 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

思路： 中序遍历 + 前序遍历 建树

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n;int a[maxn],b[maxn];struct Node{
       int val;    Node* ls,* rs;};Node* build(int l1,int r1,int l2,int r2){
       if(l1>r1) return NULL;    int pos=-1;    for(int i=l1; i<=r1; ++i)        if(a[i]==b[l2])        {
               pos=i;            break;        }    int len1=pos-l1,len2=r1-pos;    Node* node=new Node;    node->val=b[l2];    node->ls=build(l1,pos-1,l2+1,l2+1+len1-1);    node->rs=build(pos+1,r1,l2+len1+1,r2);    return node;}vector<int> ans;void bfs(Node* root){
       queue<Node*> q;    q.push(root);    while(!q.empty())    {
           Node* t=q.front();        q.pop();        ans.push_back(t->val);        if(t->rs!=NULL) q.push(t->rs);        if(t->ls!=NULL) q.push(t->ls);    }}int main(){
       scanf("%d",&n);    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);    for(int i=1; i<=n; ++i) scanf("%d",&b[i]);    Node* root=build(1,n,1,n);    bfs(root);    int m=ans.size();    for(int i=1; i<=m; ++i) printf("%d%c",ans[i-1],i==m?'\n':' ');    return 0;}

L2-012 关于堆的判断 (25分) （最小堆的构造）

题意：给定一个堆，判断命题是否正确。

思路：掌握好堆的构造即可。h[0]可以设置成最大值或者最小值，这样便于判断。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n,m,x,h[maxn],sz=0;void insert(int x){
       int i=++sz;    h[i]=x;    while(h[i/2]>h[i])    {
           swap(h[i/2],h[i]);        i=i/2;    }}int get(int x){
       for(int i=1; i<=sz; ++i)        if(h[i]==x) return i;}int main(){
       scanf("%d%d",&n,&m);    h[0]=-1e9;    for(int i=1; i<=n; ++i) scanf("%d",&x),insert(x);    getchar();    while(m--)    {
           int x,y;        string s;        getline(cin,s);        char t[50];        for(int i=0; i<s.size(); ++i) t[i]=s[i];        t[s.size()]='\0';        if(s.find("root")!=-1)        {
               sscanf(t,"%d",&x);            puts(x==h[1]?"T":"F");        }        else if(s.find("and")!=-1)        {
               sscanf(t,"%d and %d",&x,&y);            int p1=get(x);            int p2=get(y);            puts(p1/2==p2/2?"T":"F");        }        else if(s.find("parent")!=-1)        {
               sscanf(t,"%d is the parent of %d",&x,&y);            int p1=get(x);            int p2=get(y);            puts(p1==p2/2?"T":"F");        }        else if(s.find("child")!=-1)        {
               sscanf(t,"%d is a child of %d",&x,&y);            int p1=get(x);            int p2=get(y);            puts(p1/2==p2?"T":"F");        }    }    return 0;}

L2-013 红色警报 (25分) （连通块判断）

题意：战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

思路：暴力判断连通块即可。连通块多了不止一个，即时警报就好

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=510;int n,m,k;int visit[maxn],vis[maxn];vector<int> e[maxn];int mp[maxn][maxn];void dfs(int u){
       visit[u]=1;    for(int v=1; v<=n; ++v)    {
           if(!mp[u][v]||visit[v]) continue;        dfs(v);    }}int solve(){
       memset(visit,0,sizeof(visit));    int cnt=0;    for(int i=1; i<=n; ++i)        if(!visit[i]) dfs(i),cnt++;    return cnt;}int main(){
       scanf("%d%d",&n,&m);    for(int i=1; i<=m; ++i)    {
           int u,v;        scanf("%d%d",&u,&v);        u++,v++;        mp[u][v]=mp[v][u]=1;    }    scanf("%d",&k);    int cnt1=solve();    int cnt=0;    while(k--)    {
           int x;        scanf("%d",&x);        x++;        for(int i=1; i<=n; ++i) mp[x][i]=mp[i][x]=0;        int cnt2=solve();        if(cnt2>cnt1+1) printf("Red Alert: City %d is lost!\n",x-1);        else printf("City %d is lost.\n",x-1);        if(!vis[x]) cnt++,vis[x]=1;        if(cnt==n) puts("Game Over.");        cnt1=cnt2;    }    return 0;}

L2-014 列车调度 (25分) （set 的应用）

题意：两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

思路：维护一个 set ，每次找都将当前的车子排在编号恰好比自己大的前面

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n,x;int main(){
       set<int> s;    scanf("%d",&n);    for(int i=1; i<=n; ++i)    {
           scanf("%d",&x);        auto it=s.lower_bound(x);        if(it!=s.end()) s.erase(*it);        s.insert(x);    }    cout<<s.size()<<"\n";    return 0;}

L2-016 愿天下有情人都是失散多年的兄妹 (25分) （dfs）

题意：大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

思路：题目中有一个细节，说两个人同辈，那么就建完图 dfs 跑 4 层就好了。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n,m,sex[maxn],visit[maxn],ok;vector<int> e[maxn];void dfs(int u,int depth){
       if(depth<=0) return;    for(auto v: e[u])    {
           if(v==-1) continue;        if(visit[v])        {
               ok=0;            return;        }        visit[v]=1;        dfs(v,depth-1);    }}int main(){
       scanf("%d",&n);    for(int i=1; i<=n; ++i)    {
           int id,fa,mo;        char se;        scanf("%d %c %d %d",&id,&se,&fa,&mo);        e[id].push_back(fa);        e[id].push_back(mo);        sex[id]=(se=='M');        if(fa!=-1) sex[fa]=1;        if(mo!=-1) sex[mo]=0;    }    scanf("%d",&m);    while(m--)    {
           int x,y;        scanf("%d%d",&x,&y);        if(sex[x]==sex[y]) puts("Never Mind");        else        {
               ok=1;            memset(visit,0,sizeof(visit));            dfs(x,4);            dfs(y,4);            puts(ok?"Yes":"No");        }    }    return 0;}

L2-018 多项式A除以B (25分) （待补）

L2-028 秀恩爱分得快 (25分) （细节题）

题意：互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？

思路：输入很奇怪用 +、-来表示男女。那么就需要区分是 +0 还是 - 0 了。就这一个点，注意了就好了。需要一个特别的读入方式

#include <bits/stdc++.h>#define fi first#define se second#define ll long longusing namespace std;const int maxn=1010;int n,m,k[maxn],a[maxn][maxn];int sex[maxn];double mp[maxn][maxn];inline int read(){
       char s[10];    scanf("%s",s);    int f=0,t=0;    if(s[0]=='-') f=1;    for(int i=f; i<strlen(s); i++) t=t*10+s[i]-'0';    sex[t]=f;    return t;}inline void print(int x,int y){
       if(sex[x]) putchar('-');    printf("%d ",x);    if(sex[y]) putchar('-');    printf("%d\n",y);}int main(){
       scanf("%d%d",&n,&m);    for(int i=1; i<=m; ++i)    {
           scanf("%d",&k[i]);        for(int j=1; j<=k[i]; ++j) a[i][j]=read();    }    int A,B;    A=read();    B=read();    for(int i=1; i<=m; ++i)    {
           bool f1=0,f2=0;        for(int j=1; j<=k[i]; ++j)        {
               if(a[i][j]==A) f1=1;            if(a[i][j]==B) f2=1;        }        for(int j=1; j<=k[i]; ++j)        {
               if(f1&&sex[A]!=sex[a[i][j]]) mp[A][a[i][j]]+=1.0/k[i];            if(f2&&sex[B]!=sex[a[i][j]]) mp[B][a[i][j]]+=1.0/k[i];        }    }    vector<pair<double,int> > veca,vecb;    for(int i=0; i<=n-1; ++i)        if(sex[A]!=sex[i]) veca.push_back({
   mp[A][i],i});    for(int i=0; i<=n-1; ++i)        if(sex[B]!=sex[i]) vecb.push_back({
   mp[B][i],i});    auto mx1=*max_element(veca.begin(),veca.end());    auto mx2=*max_element(vecb.begin(),vecb.end());    vector<int> ans1,ans2;    for(auto x: veca)        if(x.fi==mx1.fi) ans1.push_back(x.se);    for(auto x: vecb)        if(x.fi==mx2.fi) ans2.push_back(x.se);    bool f1=0,f2=0;    for(auto x: ans1) if(x==B) f1=1;    for(auto x: ans2) if(x==A) f2=1;    if(f1&&f2) print(A,B);    else    {
           for(auto x: ans1) print(A,x);        for(auto x: ans2) print(B,x);    }    return 0;}

L2-029 特立独行的幸福 (25分) （模拟）

题意：对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数，其独立性为 2×4=8。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。
本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。

思路：直接模拟操作。就好了。当初比赛的时候是真的菜，简单模拟就好了。

#include <bits/stdc++.h>#define fi first#define se second#define ll long longusing namespace std;const int maxn=1e4+5;int l,r,visit[maxn];map<int,int> mp;int check(int n){
       if(n==1) return 1;    for(int i=2; i*i<=n; ++i)        if(n%i==0) return 1;    return 2;}int get(int n){
       int res=0;    while(n)    {
           res+=(n%10)*(n%10);        n/=10;    }    return res;}int main(){
       scanf("%d%d",&l,&r);    for(int i=l; i<=r; ++i)    {
           int n=i,cnt=0;        set<int> s;        while(n!=1)        {
               n=get(n);            if(s.count(n)) break;            visit[n]=1;            s.insert(n);            cnt++;        }        if(n==1) mp[i]=cnt;    }    bool ok=0;    for(auto x: mp)    {
           if(visit[x.fi]) continue;        ok=1;        printf("%d %d\n",x.fi,x.se*check(x.fi));    }    if(!ok) puts("SAD");    return 0;}

L2-030 冰岛人 (25分) （简单图）

题意：给定姓名，判断两个人是否在5代以内有关系

思路：细节比较多。

#include <bits/stdc++.h>#define fi first#define se second#define ll long longusing namespace std;const int maxn=1e5+10,inf=2e9;int n,m;string fi,se;unordered_map<string,pair<string,int> > fa;bool check(string a,string b){
       unordered_map<string,int> path;    for(int i=0; a!="null"; i++,a=fa[a].fi) path[a]=i;    for(int i=0; b!="null"; i++,b=fa[b].fi)        if(path.count(b)&&(path[b]<4||i<4)) return false;    return true;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cin>>n;    for(int i=1; i<=n; ++i)    {
           cin>>fi>>se;        int m=se.size();        if(se.substr(m-1)=="m") fa[fi]= {
   "null",0};        else if(se.substr(m-1)=="f") fa[fi]= {
   "null",1};        else if(se.substr(m-1)=="n")        {
               string f=se.substr(0,m-4);            fa[fi]= {
   f,0};        }        else if(se.substr(m-1)=="r")        {
               string f=se.substr(0,m-7);            fa[fi]= {
   f,1};        }    }    cin>>m;    while(m--)    {
           string f1,s1,f2,s2;        cin>>f1>>s1>>f2>>s2;        if(!fa.count(f1)||!fa.count(f2)) puts("NA");        else if(fa[f1].se==fa[f2].se) puts("Whatever");        else puts(check(f1,f2)?"Yes":"No");    }    return 0;}