牛客oj 小白月赛41题解

发布于 2021-12-05  109 次阅读


1 小红的签到题

这道题真的签到,只需要过题总数除题目数就可得到最多ak人数。

#include<iostream>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	int ans=c/a;
	cout<<ans<<"\n";
return 0;
}

2 小红的abc

这道题是寻找所给的字符串里面最短的回文子串,如果存在两个一样的那么最短的就一定是这两个一样的,不管如何最短都是2,但是如果没有两个一样的但是有a[i]==a[i+2]这种类型的回文子串,那么最短一定是三,所以我们只需要判断这其中有没这两类就可了;

#include<iostream>
#include<string.h>
using namespace std;
char s[1000];
int main()
{
	cin>>s;
	int ans=0;
	for(int i=0;i<strlen(s);i++)
	{
		if(s[i]==s[i+1]){
			ans=2;
			break;
		}
		if(s[i]==s[i+2])
		{
			ans=3;
		}
	}
	if(ans)cout<<ans<<"\n";
	else cout<<"-1\n";
	return 0;
}

3 小红的口罩

这道题就是贪心,很简单的每次都选择当前最不适度最低的口罩。这道题我使用的是优先队列,直接跑一遍就可以了。

#include<iostream>
#include<queue>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
int a[100009];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		int num;
		cin>>num;
		q.push(num);
	}
	int ans=0,cnt=0,mid;
	while(ans<k)
	{
		ans+=q.top();
		mid=q.top()*2;
		q.push(mid);
		q.pop();
		if(ans<k)
		{
			cnt++;
		}
	} 
	cout<<cnt<<"\n";
	return 0;
}

4 小红的数组

这道题挺暴力的,直接从0-n-1每个数都进行一遍处理,寻找达到这三种情况的区间范围。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[400009];
int main()
{
	ll n,k;
	ll ans1=0,ans2=0,ans3=0;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n-1;i++)
	{
		 if(a[i]*a[i+1]>k)ans1+=n-i-1;
        else if(a[i]*a[n-1]<k)ans3+=n-i-1;
        else{
//这里的i1,i2是用来寻找相等的区间,也就是等于k的情况,第一个大于他的数的位置减去第一个他的位置就是他的个数。
            int i1=lower_bound(a+i+1,a+n,k/a[i])-a;    //要注意二分的边界
            int i2=upper_bound(a+i+1,a+n,k/a[i])-a;
            if(k%a[i]!=0){
                ans3+=i2-i-1;
                ans1+=n-i2;
            }
            else{
                ans3+=i1-i-1;
                ans1+=n-i2;
                ans2+=i2-i1;
            }
        }
	}
	
	cout<<ans1<<" "<<ans2<<" "<<ans3<<"\n";
 } 

5 小红的rpg

#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,h,minn=0x3f3f3f3f;
int xx[5]={0,0,1,-1};
int xy[5]={1,-1,0,0};
char map[105][105];
int dis[105][105];
void dfs(int x,int y,int cnt,int h){
	if(x==n&&y==m){
		if(cnt<minn)minn=cnt;
	}
	else{
		for(int i=0;i<4;i++){
			int	nx=x+xx[i];
			int	ny=y+xy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[nx][ny]!='*'&&!dis[nx][ny]){
				if(map[nx][ny]>='0'&&map[nx][ny]<='9'){
					if(h>map[nx][ny]-'0'){
						dis[nx][ny]=1;
						dfs(nx,ny,cnt+1,h-(map[nx][ny]-'0'));
						dis[nx][ny]=0;
					}
					else continue;
				}
				else{
					dis[nx][ny]=1;
					dfs(nx,ny,cnt+1,h);
					dis[nx][ny]=0;
				}
			}
		}
		
	}
	
}
int main(){

	cin>>n>>m>>h;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
		{
			scanf(" %c",&map[i][j]);
		}
	}
	dis[1][1]=1;
	dfs(1,1,0,h);
	if(minn!=0x3f3f3f3f)cout<<minn;
	else cout<<"-1";
    return 0;
}