您现在的位置是:首页 >技术教程 >牛客小白月赛65网站首页技术教程

牛客小白月赛65

晓觉儿 2024-06-17 11:26:43
简介牛客小白月赛65

题目链接

A-牛牛去购物(枚举)

题目描述

牛牛带着 n n n元钱去超市买东西,超市一共只有两款商品,价格为 a a a元的篮球和价格为 b b b元的足球,牛牛想把手里的钱尽可能花光,请问牛牛最少能剩多少钱?

输入描述:

输入一行,三个正整数 n , a , b ( 1 ≤ n , a , b ≤ 1000 ) n,a,b (1 leq n,a,b leq 1000) n,a,b(1n,a,b1000), n n n表示牛牛现有的钱数, a a a表示一个篮球的单价, b b b 表示一个足球的单价。

输出描述:

输出一行一个整数,代表牛牛最少能剩下的钱数。

题解:

枚举每种情况取剩下的最下钱数即可

#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    int ans=n;
    for(int i=0;i<=n/a;i++){
        for(int j=0;j<=n/b;j++){
            int x=n-a*i-b*j;
            if(x>=0){
                ans=min(ans,x);
            }
        }
    }
    cout<<ans;
}

signed main(void){
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

当然也可以简化代码
直接遍历花钱数从买0个篮球遍历到买n/a个篮球即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,big=200000;
    cin>>n>>a>>b;
    for(int i=0;i<=n;i+=a)
    big=min(big,(n-i)%b);
    cout<<big;
    return 0;
}

B-牛牛写情书(字符串)

在这里插入图片描述
在这里插入图片描述
题解:

遍历选取出原字符串中所有小写字母,然后再直接找字串即可
如果没找到输出NO

#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
void solve(){
    int n,m;cin>>n>>m;
    string k,s;
    cin>>s>>k;
    string ss;
    for(int i=0;i<s.size();i++)
        if(s[i]>='a'&&s[i]<='z')
            ss+=s[i];
    if(ss.find(k)==string::npos)cout<<"NO";
    else cout<<"YES";
}

signed main(void){
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

C-牛牛排队伍(模拟)

在这里插入图片描述
示例1
输入

5 4
2 1
1 3
2 5
2 4

输出

0
4
2

题解:

其实就是一个队伍或者是队列。
那么叫走一个就要改变当前队列后一个的前者。
但因为叫走顺序不定,所以我们不仅要记录当前队列每位的前一位是谁,还要记住后一位是谁。
如果单纯用bool数组去记录当前位走没走,后续遍历很耗时间,直接TLE
其实就是双链表

#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
inline int read(){
    int ans=0;
    int f=1;char ch;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')f=-1;
    do ans=(ans<<3)+(ans<<1)+(ch^48); while((ch=getchar())>='0'&&ch<='9');
    return f*ans;
}
const int N = 1e6+10;
int b[N];
int a[N];
void init(int n){
    for(int i=1;i<=n;i++){
        a[i]=i-1;
        b[i]=i+1;
    }
        
}
void solve(){
    int n=read(),k=read();
    init(n);
    while(k--){
        int chose=read(),x=read();
        if(chose==1){
            a[b[x]]=a[x];
            b[a[x]]=b[x];
            
        }
        else if(chose==2){
            printf("%d
",a[x]);
        }
    }
}

signed main(void){
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

D-牛牛取石子(博弈)

在这里插入图片描述
示例1
输入

2
1 2
3 3
输出

niuniu
niumei

题解:

一开始看这道题,想着直接博弈,打一个巴什游戏的输赢条件即可。
后面想着又没那么简单,有两堆,其实决定胜负的是少石头的那一堆。
就加了一个判断和交换。
后面还是错的
这题的特例就是两堆石头相同的情况

下面是特例考虑:

考虑4和4:先手操作后,得到3和2,后手拿1和2,剩下2和0,先手败。
其实上面的分析默认了一个条件:针对最小堆进行策略操作后不会改变原来两堆的相对大小,而当两堆相等时:

模3得1时:还是上面的例子,4和4,令另第一个4为较小值,先手要将其变为3的倍数,选择操作1,变为的3和2改变了一开始的“大小关系”,这时不是第一堆最小了,而是第二堆的2,2模3不为0,这对后手而言是“必胜态”。
模3得2时:例如5和5,令第一个5为较小值,进行操作2,变为3和4,仍是第一堆较小,未改变大小关系,先手赢。

#include <iostream>
#define int long long
using namespace std;
void solve(){
    int a,b;cin>>a>>b;
    if(a>b)swap(a,b);
    if(a%3==0||(a==b&&a%3==1))cout<<"niumei
";
    else cout<<"niuniu
";
}

signed main(void){
    int _=1;
    cin>>_;
    while(_--)solve();
    return 0;
}

E-牛牛的构造(构造,思维)

在这里插入图片描述
题解:

注:以下出现运算全都向下取整
如果考虑最大全排列,如果一个数 x x x放在前面,那么后面就有 x − 1 x-1 x1个比他小的数,那么该数字能到达 k k k提供 l o g 2 ( i ) log_2(i) log2(i)个值,直接从大到小遍历,如果最大全排列无法满足 k k k就输出-1
如果能满足,例如需要 l o g 2 ( x ) log_2(x) log2(x)个贡献,那么就把 x x x放在 0 到 ( x − 1 ) 0到(x-1) 0(x1)的前面,使得式子可以成立, x x x可以做出 l o g 2 ( x ) log_2(x) log2(x),如果贡献值刚好到了 k k k,那么这个数组就是存在的,因为考虑贡献是从最大的开始,那么队列就是从最大的开始放,最后放入数组的时候直接放就可以了,就可以保证小于其值的数字都在后面,当然,我们仅仅需要队列里面的值提供贡献,那么就表明如果没有进队列的值贡献一定为 0 0 0,那么最后就正向遍历没有出现过的即可,这样出来的剩余值,小的在前面大的在后面,通过题目式子运算,一定为负数,不可能有贡献!!!

#include <iostream>
#include <queue>
#include<vector>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6+10;
//int a[N];
vector<int>a;
queue<int >q;
bool b[N];
void init (int n);
void Print(int n){
    int flag=1;
    for(int i=0;i<a.size();i++){
        if(flag)cout<<a[i];
        else cout<<' '<<a[i];
        flag=0;
    }
}
void solve(){
    int n,k;
    cin>>n>>k;
    //init(n);
//     if(k>(n-1)*n/2){
//         cout<<-1;return ;
//     }
    for(int i=n;i>=1;i--){
        if(k>=log2(i)){
            q.push(i);
            k-=log2(i);
        }
        if(k==0)break;
    }
    if(k>0){cout<<-1;return ;}
    while(!q.empty()){
        int x=q.front();
        b[x]=true;
        a.push_back(x);
        q.pop();
    }
    
    for(int i=1;i<=n;i++){
        if(b[i]==false)a.push_back(i);
    }
    Print(n);
}
void init (int n){
//     for(int i=n;i>=1;i++){
//         a[i]=i;
//     }
    a.resize(n+1);
}
signed main(void){
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。