题解

[!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";
    }
}