题解

[!NOTE]

参考AC代码为C++代码,对于本次练习基本只有输出输出函数有差别

用到的c++容器和算法可以在下列网站中查询学习,可以用到哪个学习哪个,多练习就能够掌握

【C++】蓝桥杯必备 算法竞赛常用STL万字总结_算法竞赛允许哪些stl-CSDN博客

对于算法基础知识可以在oi-wiki上了解

算法基础简介 - OI Wiki

A

直接判断是否相同即可

AC代码

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

int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a==b&&b==c&c==d)cout<<"NO\n";
        else cout<<"YES\n";
    }
}

B

直接判断大小

AC代码

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

int main(){
    double a,b;
    cin>>a>>b;
    if(a>=b)cout<<"NO";
    else cout<<"YES";
}

C

判断相同的字母数即可,这里用string,替换成字符串数组做法一致

AC代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    if(s[0]==s[1]&&s[1]==s[2]){//全一致
        cout<<0;
    }else if(s[0]==s[1]||s[0]==s[2]||s[1]==s[2]){//有两个一致
        cout<<1;
    }else cout<<2;//全不一致
}

D

显然要用左右柱子最小的那个和中间柱子高度作比较

最终结果就是min(max(0,a-b),max(0,c-b))

[!NOTE]

对于C语言max和min函数自行实现

AC代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(max(0,a-b),max(0,c-b));
}

E

尽量凑能够胜利的情况(例如己方石头和对方剪刀数量取最小值)即可

AC代码

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

int main(){
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    int ans=min(a,e)+min(b,f)+min(c,d);
    cout<<ans;
}

F

显然最佳的送礼方式是形如 1-2-1-2-....

那么可以先判断能够凑出多少个3,即n/3的整数除法,最终剩余(n%3)一定小于3,如果最后剩余为0,则无法再次送礼,否则不论是剩余1还是剩余2,都只够再送一次

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    //每3个本子可以送2次礼物
    if(n%3!=0)cout<<(n/3)*2+1;//最终有剩余
    else cout<<(n/3)*2;//五剩余
}

G

本题有两种做法,一次遍历O(n)/排序贪心O(n*logn)

对于本题显然遍历效率更高

我们这里介绍一次遍历的做法,并附上排序做法代码(用到c++algorithm库中sort函数,亦推荐自行学习快速排序原理)

先考虑我们的首要目标,让尽可能多的巫女开心,那么我们最多可以使多少个巫女开心呢,我们拥有x个金币,所以只要是金币需求小于等于x的巫女我们都可以达到使她开心的金币数,最终剩余即需求最高的巫女和我们所拥有的金币x之间的差值

AC代码

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

int main(){
    int n,x,need,maxx=-1,ans=0;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>need;
        if(need<=x){
            ans++;
            maxx=max(maxx,need);
        }
    }
    cout<<ans<<" "<<x-maxx;
}

排序贪心

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

int main(){
    int n,x;
    cin>>n>>x;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    sort(arr,arr+n);
    int ans=0,res=x;
    for(int i=0;i<n;i++){
        if(x>=arr[i]){
            ans++;
            res=x-arr[i];
        }else break;
    }
    cout<<ans<<" "<<res;
}

H

显然我们要找的正多边形是正三角形(相同边长下周长最小,且需求边数最少)

这里我们使用桶来存放某个长度的边的个数

即定义一个数组len大小为101(长度范围为1-100),对于数组每个位置初始置0,对于某个长度的边在对应的元素上+1,这样最终统计出来的就是某个边的个数,我们挑选最小的满足要求的边即可,如果没有,输出no

AC代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,l;
        cin>>n;
        int len[101];
        memset(len,0,sizeof(len));//置0
        for(int i=0;i<n;i++){
            cin>>l;
            len[l]++;
        }
        int flag=1;
        for(int i=1;i<=100;i++){
            if(len[i]>=3){
                flag=0;
                cout<<"yes\n";
                cout<<i*3<<"\n";
                break;
            }
        }
        if(flag)cout<<"no\n";
    }
}

I

显然两个数a,b的最大公约数小于等于min(a,b),所以只有当子序列中元素都相同时,才是好序列

那么求最终的最长长度转化成了出现次数最多的数出现了几次

很容易联想到和H题一样利用桶来存放元素出现次数

但是对于ai([1,1e9])我们不能直接用数组模拟桶,但是考虑到对于1e5个数最多即1e5种不同的数,则可以考虑离散化,这里使用map进行离散化

[!NOTE]

也可以通过排序(相等的数连续,找最长连续长度即可)

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        mp[num]++;
    }
    int ans=1;
    for(auto [x,y]:mp){//利用auto遍历map,x,y即为键值对
        ans=max(ans,y);
    }
    cout<<ans;
}

J

本题为模拟题,重点就是如何实现要求的功能

AC代码

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

int main(){
    string s;
    cin>>s;
    int sum=0;
    int arr[9]={0,2,3,4,6,7,8,9,10};//预处理需要处理的位置的下标
    for(int i=0;i<9;i++){
        sum+=(s[arr[i]]-'0')*(i+1);//求和
    }
    sum%=11;//对11取余
    if(sum==10&&s[12]=='X'){//判断是否正确
        cout<<"Right";
    }else if(sum==(s[12]-'0')){
        cout<<"Right";
    }else{
        cout<<s.substr(0,12);//输出前12个字符
        if(sum==10)cout<<"X";//纠正
        else cout<<sum;
    }	
}

K

可以想到枚举在前/后分别输出了几个元素,但是对于每种情况,我们需要不遍历就能求出区间和(O1的复杂度),这样就需要前缀和预处理了

[!NOTE]

本题数据范围较小,不使用前缀和可能也可AC

AC代码

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

int main(){
    int n,k;
    cin>>n>>k;
    long long a[n+1],pre[n+1];//区间和可能超出int范围
    memset(pre,0,sizeof(pre));//置0
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    long long ans=-1;
    for(int i=0;i<=k;i++){//枚举前面删除几位
        ans=max(ans,pre[n-k+i]-pre[i]);//取最大的和
    }
    cout<<ans;
}

L

对于此类题目可以先考虑构成解的形式

当a=m,b>a时显然可以满足条件2

​ 此时a+b=n->b=n-m

​ 即n-m>m->n>2*m

综上n>2m时一定有解

又可以证明a%b一定小于等于min(a,b)当且仅当a<b时等于min(a,b)

​ 则当n<=2m时min(a,b)一定小于等于m

​ 且当a<b时,a<m

​ 即此时a%b一定小于m,无解

至此所有情况已经判断完毕

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
    int n,m;
        cin>>n>>m;
        if(n>2*m){
            cout<<m<<" "<<n-m<<endl;
        }else cout<<"-1\n";
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务