题解 P6565 【[NOI Online #3 入门组]最急救助（民间数据）】

· · 题解

这是 NOI Online这么多场比赛中最良心的一道题，没有之一

更好的阅读体验？

题目大意就是给你一堆字符串，然后让你找出哪个字符串中包含的子串 sos 最多。

所以，我们要做的事情有：

  1. 在一个字符串中寻找子串 sos 的数量；
  2. 以子串 sos 的数量为第一优先级，输入顺序为第二优先级排序；
  3. 输出所有子串 sos 最多的字符串。

接下来，让我们一步一步切掉这道题吧QwQ！

前置：存储每个人的信息

这里定义一个结构体即可。

struct node{
    string name,help;
    int s,num;
    //name 是求助者的名字
    //help 是求助者的求助信息
    //s 是求助信息中子串 sos 的数量
    //num 是求助者的顺序
}str[105];

第一步：在一个字符串中寻找子串 sos 的数量

这部分是最简单的，直接从头到尾暴力枚举即可。

代码如下：

int find(string qwq){                   //寻找子串 sos 的数量
    int len=qwq.size();                 //提取出这个字符串的长度，STL 大法好！QwQ
    int anss=0;                         //子串 sos 的数量
    for(int i=0;i<len-2;i++){           //从头到尾枚举
        if(qwq[i]=='s'&&qwq[i+1]=='o'&&qwq[i+2]=='s'){  //如果这里有一个 sos
            anss++;                     //子串 sos 的数量+1
        }
    }
    return anss;                        //返回子串 sos 的数量
}

第二步：以子串 sos 的数量为第一优先级，输入顺序为第二优先级排序；

这里也可以利用 STL 中的 sort 函数，手写一个 cmp 比较函数即可。

首先是比较函数 cmp ：

bool cmp(node p,node q){                //比较函数 cmp
    if(p.s==q.s){                       //如果两个求助信息中的子串 sos 的数量都相同
        return p.num<q.num;             //按照输入顺序排序
    }
    return p.s>q.s;                     //否则按照求助信息中的子串 sos 的数量排序
}

然后，排序部分只有一行：

sort(str+1,str+n+1,cmp);            //STL 大法好！QWQ

第三步：输出

为了确保输出每一个子串 sos 最多的字符串，我们可以定义变量 tmp 来表示子串 sos 最多有多少个，然后一个一个输出。

一旦出现子串 sos 少于 tmp 的情况，立刻退出循环，停止输出。

最后，输出 tmp 。（因为题目中还说让输出最紧急求救者的求救信号中包含有多少个 sos 子串）

代码如下:

int tmp=str[1].s;                   //排序之后，最前面的那个自然就是子串 sos 最多的啦QwQ，直接记录即可。
for(int i=1;i<=n;i++){
    if(str[i].s!=tmp){              //如果子串 sos 的数量少于 tmp
        break;                      //立刻退出循环停止输出
    }
    cout<<str[i].name<<" ";
}
cout<<endl<<tmp;                    //别忘了换行哦

最后，完整代码：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    string name,help;
    int s,num;
    //name 是求助者的名字
    //help 是求助者的求助信息
    //s 是求助信息中子串 sos 的数量
    //num 是求助者的顺序
}str[105];
int find(string qwq){                   //寻找子串 sos 的数量
    int len=qwq.size();                 //提取出这个字符串的长度，STL 大法好！QwQ
    int anss=0;                         //子串 sos 的数量
    for(int i=0;i<len-2;i++){           //从头到尾枚举
        if(qwq[i]=='s'&&qwq[i+1]=='o'&&qwq[i+2]=='s'){  //如果这里有一个 sos
            anss++;                     //子串 sos 的数量+1
        }
    }
    return anss;                        //返回子串 sos 的数量
}
bool cmp(node p,node q){                //比较函数 cmp
    if(p.s==q.s){                       //如果两个求助信息中的子串 sos 的数量都相同
        return p.num<q.num;             //按照输入顺序排序
    }
    return p.s>q.s;                     //否则按照求助信息中的子串 sos 的数量排序
}
int main(){
    //freopen("save.in","r",stdin);
    //freopen("save.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);                        //黑科技cin,cout加速
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>str[i].name>>str[i].help;
        str[i].s=find(str[i].help);     
        str[i].num=i;
    }
    sort(str+1,str+n+1,cmp);            //STL 大法好！QWQ
    int tmp=str[1].s;                   //排序之后，最前面的那个自然就是子串 sos 最多的啦QwQ，直接记录即可。
    for(int i=1;i<=n;i++){
        if(str[i].s!=tmp){              //如果子串 sos 的数量少于 tmp
            break;                      //立刻退出循环停止输出
        }
        cout<<str[i].name<<" ";
    }
    cout<<endl<<tmp;                    //别忘了换行哦
    return 0;
}

最后，祝大家：

struct node{
    int RP;
}NOI_Online_3rd;
NOI_Online_3rd.RP++;