题解
[!NOTE]
参考AC代码为C++代码,对于本次练习基本只有输出输出函数有差别
用到的c++容器和算法可以在下列网站中查询学习,可以用到哪个学习哪个,多练习就能够掌握
【C++】蓝桥杯必备 算法竞赛常用STL万字总结_算法竞赛允许哪些stl-CSDN博客
对于算法基础知识可以在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"; } }