Lucky Substring（CodeForces - 122B）

Input
047
Output
4
Input
16
Output
-1
Input
472747
Output
7

题意：给出的字符串的子串满足下面3个条件，输出字典序最小的那个。（1）只含有4或7（2）子串中个数多的优先（3）不能有前导0

思路：因为n<50,所以可以先找出所有字串，然后排序，之后输出满足条件的第一个。关键就是如何存储那里，我是先用S数组存出所有字串，顺带写个map标记一下个数，最后就是cmp排序函数了。

#include <iostream>
#include<cstring>
#include<stdio.h>
#include<algorithm>
#include <vector>
#include<iomanip>
#include <queue>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<stddef.h>
using namespace std;
string S[101010];
map<string,int> ma;
bool cmp(string p,string q){
if(ma[p]==ma[q])
return p < q;
return ma[p]>ma[q];
}
int main()
{
string s;
cin>>s;
int n=0;
for(int i=0;i<s.size();i++){
for(int j=1;i+j<=s.size();j++){
S[n++]=s.substr(i,j);
ma[s.substr(i,j)]++;
}
}
sort(S,S+n,cmp);
int flag=0;
int i,j;
string ans;
for(int i=0;i<n;i++){
// cout<<S[i]<<endl;
for(j=0;j<S[i].size();j++){
if(S[i][j]!='4'&&S[i][j]!='7')
break;
if(S[i][0]=='0')
break;
}
if(j>=S[i].size()){
flag=1;
//cout<<"***"<<endl;
ans=S[i];
break;
}
}
if(flag==1)
cout<<ans<<endl;
else
cout<<"-1"<<endl;
return 0;
}

最后

以上就是优雅羽毛为你收集整理的Lucky Substring（CodeForces - 122B）的全部内容，希望文章能够帮你解决Lucky Substring（CodeForces - 122B）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。