https://ac.nowcoder.com/acm/contest/87255#question

G
题目要求其军队所成为一个点后最小步数，军队分散在各处，也就是求其联通成为一个点后最小步数，也就是最小生成树对于每一个军队 用bfs求出每个军队之间的距离然后做一遍最小生成树。注意如若某次bfs发现搜到的军队小于原数，则说明存在无法到达的军队直接输出NO

# include <bits/stdc++.h>
using namespace std;
# define int long long
# define x first
# define y second
const int N=1e3+10;
char c[N][N];
int a[N][N],g[N][N];
int d[N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n,m;
int ans=1,res,num;
bool st[N];
void bfs(int i,int j)
{
int d[N][N]={0};
    ans=1;
memset(d,-1,sizeof d);
d[i][j]=0;
queue<pair<int,int>>q;
q.push({i,j});
while(q.size())
{
auto t=q.front();
    q.pop();
    if(a[t.x][t.y])
    {
    g[a[i][j]][a[t.x][t.y]]=d[t.x][t.y];
    //cout<<d[t.x][t.y]<<" ";
    }

    for(int i=0;i<4;i++)
    {
    int l=t.x+dx[i],r=t.y+dy[i];
    if(l>=1&&l<=n&&r>=1&&r<=m&&c[l][r]!='#'&&d[l][r]==-1)
    {
    d[l][r]=d[t.x][t.y]+1;
    q.push({l,r});
    if(a[l][r])
    ans++;
    }
    }
}
}
int prim()
{
memset(d,0x3f,sizeof d);
d[1]=0;
for(int i=1;i<=num;i++)
{
int t=-1;
for(int j=1;j<=num;j++)
{
if(!st[j]&&(t==-1||d[t]>d[j]))
t=j;
}
if(i!=1)
res+=d[t];
st[t]=1;
for(int j=1;j<=num;j++)
{
d[j]=min(d[j],g[t][j]);
}

}
    return res;    
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=m;j++)
    {
        cin>>c[i][j];
        if(c[i][j]=='*')
        a[i][j]=++num;
    }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j])
            {
            bfs(i,j);
            if(ans<num)
            {
            cout<<"No";
            return 0;
            }
            }
        }
    }
    cout<<prim();

}

H 复杂模拟题 考察stl与字符串匹配 模拟即可

#include<bits/stdc++.h>
using namespace std;

const int N = 210,M = 100;
int n;
struct node
{
    int m,mm;  //分别是去重和舍去后缀前后的信息条数  
    string s[N];
    bool vis[N];
}name[M];
int idx=1;
int main()
{
    map<string,int>ma;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string id;
        int op;
        cin>>id>>op;
      if(!ma[id])
      {
         ma[id]=idx;
         idx++;
      }
        int l=name[ma[id]].m;
        string s1;
        for(int j=0;j<op;j++)
        {
        cin>>s1;
        name[ma[id]].s[l++]=s1;
        }
        name[ma[id]].m=l;
    }
    for(int i=1;i<idx;i++)
    {
    for(int j=0;j<name[i].m;j++)
    {
    for(int k=j+1;k<name[i].m;k++)
    {
    string  a=name[i].s[j],b=name[i].s[k];
    int len1=a.size(),len2=b.size();
    if(len1>len2)
    {
    a = a.substr(a.size() - b.size() ,b.size());
    if(a == b) name[i].vis[k] = 1;
    }
    else 
    {
    b= b.substr(b.size() - a.size() ,a.size());
    if(a == b) name[i].vis[j] = 1;
    }
    }
    }
    int mm=0;
    for(int j=0;j<name[i].m;j++)
    {
    string s1=name[i].s[j];
    if(name[i].vis[j]==0)
    name[i].s[mm++]=s1;
    }
    name[i].mm=mm;
    sort(name[i].s,name[i].s+mm);
    }

    cout << ma.size()<<"\n";
    for(auto i : ma)
    {
        cout << i.first << " "<< name[i.second].mm << " ";
        for(int j = 0; j < name[i.second].mm; j++)
        {
            cout << name[i.second].s[j] << " ";
        }
        cout << "\n";
    }
    return 0;

}