天梯赛 L2 练习题

习题

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

题意：按题意处理字符串

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

#include <bits/stdc++.h>
#define ll long long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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;
}

习题

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

L2-001 紧急救援 (25分)

L2-002 链表去重 (25分)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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