第十五(15)届蓝桥杯模拟赛题解+AC代码(第一期)
励志短句:纵使长夜难明,亦会有人为你燃灯
提醒:篇幅较长,大家可以结合目录查看想要的内容
第一题:
题面:
思路:
1.从2023开始枚举每一个数并检查是否合法,一但枚举到合法的数,直接输出答案结束程序即可
2.怎么检查一个数是否合法呢?可以直接转化16进制后放到数组中,再遍历数组判断是否有小于10的数,没有的话就是合法的,有一个数小于10就是不满足条件的,直接返回false
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
bool check(int x,vector<int> &nums){
while(x) {
nums.push_back(x%16);
x/=16;
}
for(int i=0;i<nums.size();i++)
if(nums[i]<10) return false;
return true;
}
void solve(){
for(int i=2023;;i++){
vector<int>nums;
if(check(i,nums)){
cout<<i<<"\n";
return;
}
}
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
注意这题是直接输出答案:2730
但是这里还是贴上一个代码
第二题:
题面:
思路:
1.一个字母时为A~Z,有26个字母,两个字母时AA~ZZ,共有26*26=676,当有三个字母时AAA~ZZZ,共有26*26*26=17576个字母,因为2022在[676,17576]之间,故2022一定是有三个字母的。
2.此时可以用3个for循环,3个for循环依次对应第几位填那个字母,从A到Z枚举,并用一个计数器记录枚举到了那个数字,枚举到了2022就直接输出答案
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
int const mod=998244353; //1e9+7
int const N=2e5+7;
int const INF=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
int T;
int n,m;
int a[N];
LL ans;
void solve()
{
int cnt=26*26+26; //1个字符,2个字符的所有组合情况
for(char i='A';i<='Z';i++)
for(char j='A';j<='Z';j++)
for(char k='A';k<='Z';k++){
cnt++;
if(cnt==2022){ //到了2022直接输出答案
cout<<i<<" "<<j<<" "<<k<<" ";
return;
}
}
}
int main()
{
T=1;
// scanf("%d",&T);
while(T--){
ans=0;
solve();
}
return 0;
}
注意这题是直接输出答案:BYT
但是这里还是贴上一个代码
第三题:
题面:
思路:
1.关于日期的问题,这里有一个通解,难就难在check函数,就是给你一个8位数的十进制数,如何判断它是一个合法的日期
2.这里可以按年,月,日,拆出来,可以直接让前4位数为年份,第5 6位为月份,最后两位数为日,然后特判月份与日为0的情况,还有月份大于12的情况,最后根据月份直接判断日期是否合法就行,但是还要注意一个平闰年的情况(闰年29天,平年28天,判断闰年的方法是:能被400整除一定为闰年,还有能被4整除但是不能被100整除一定是闰年)
3.关于本题:可以直接从19000101枚举到99991231,在用check函数判断每一个数是否为合法日期,是合法日期答案++。(check函数具体细节看代码)
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
int const mod=998244353; //1e9+7
int const N=2e5+7;
int const INF=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
int T;
int n,m;
int months[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int data){
int year=data/10000;
int month=data/100%100;
int day=data%100;
if(month==0||month>12||day>31||day==0) return false;
if(month==2){
bool flag=year%400==0||(year%4==0&&year%100!=0);
if(day>flag+28) return false;
}
else if(day>months[month]) return false;
//上面这段代码,可以背过,
//以后遇到关于日期的问题,可以直接当公式套用
//检查年份数位和是否等于月+日的数位和
int temp=year;
int a=0,b=month%10+month/10%10+day/10%10+day%10;
while(temp) a+=temp%10,temp/=10;
if(a!=b) return false; //年份数位和不等于月+日的数位和
return true; //上面条件都满足才返回true
}
void solve()
{
int ans=0;
for(int i=19000101;i<=99991231;i++)
if(check(i)) ans++;
cout<<ans<<endl;
}
int main()
{
T=1;
// scanf("%d",&T);
while(T--){
//ans=0;
solve();
}
return 0;
}
注意这题是直接输出答案:70910
但是这里还是贴上一个代码
第四题:
题面:
intput:
99 22 51 63 72 61 20 88 40 21 63 30 11 18 99 12 93 16 7 53 64 9 28 84 34 96 52 82 51 77
思路:
1.可以直接两重for循环枚举两个数,第一个for枚举第一个数,第二个for枚举第二个数,满足乘积大于等于2022答案++
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
int const mod=998244353; //1e9+7
int const N=2e5+7;
int const INF=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
int T;
int n,m;
int a[N];
LL ans;
void solve()
{
n=30;
for(int i=0;i<n;i++) scanf("%d, ",&a[i]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(a[i]*a[j]>=2022) ans++;
cout<<ans<<endl;
}
int main()
{
T=1;
// scanf("%d",&T);
while(T--){
ans=0;
solve();
}
return 0;
}
注意这题是直接输出答案:189
但是这里还是贴上一个代码
第五题:
题面:
input:
110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101
思路:
1.连通块问题,可以直接bfs,dfs都可以解决,具体细节看代码
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
int const mod=998244353; //1e9+7
int const N=37,M=67;
int const INF=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
int T;
int n,m;
char s[N][M];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int dfs(int x,int y){
int res=1;
for(int i=0;i<4;i++){
int bx=dx[i]+x,by=dy[i]+y;
if(bx<0||by<0||bx>=n||by>=m) continue;
if(s[bx][by]!='1') continue;
s[bx][by]='2'; //遍历过改为字符2
res+=dfs(bx,by);
}
return res;
}
int bfs(int x,int y){
queue<PII>q;
q.push({x,y});
int res=0;
while(q.size()){
PII temp=q.front(); q.pop();
res++; //联通个数++
for(int i=0;i<4;i++){
int bx=dx[i]+temp.x,by=dy[i]+temp.y;
if(bx<0||by<0||bx>=n||by>=m) continue;
if(s[bx][by]!='1') continue;
s[bx][by]='2'; //遍历过改为字符2
q.push({bx,by});
}
}
return res;
}
void solve()
{
n=30,m=60;
for(int i=0;i<n;i++) scanf("%s",s[i]);
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(s[i][j]=='1'){
//记得起点也要更改,此语句是后面加上的,
//149并非正确答案,正确答案为148
s[i][j]='2';
ans=max(ans,dfs(i,j)); //dfs
//ans=max(ans,bfs(i,j)); //bfs
}
}
cout<<ans<<endl;
}
int main()
{
T=1;
// scanf("%d",&T);
while(T--){
//ans=0;
solve();
}
return 0;
}
注意这题是直接输出答案:148
但是这里还是贴上一个代码
第六题:
题面:
思路:
简述题意:给你一周中的一天w,问过了n天后是星期几?
1.过了n天后是第几天,n为7的倍数不影响答案,故可以直接对n取模,再累加到w中
2.注意这里取模ans可能等于0的情况,此时要更改ans=7
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int w,n,m;
int a[N];
void solve(){
cin>>w>>n;
int ans=(w+n%7)%7;
if(ans==0) ans=7;
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第七题:
题面:
思路:
简述题意:给定一个矩形区域,和n个半径为R的圆心,问矩形中有多少个点被圆所包含?
1.数据范围较小,可以直接枚举每个点,看是否被某个圆所包含,包含直接答案++
时间复杂度 o(WHn) 1e6
AC_Code:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=107;
int const INF=0x3f3f3f3f;
int T;
int W,H,n,R;
PII a[N];
void solve(){
scanf("%d%d%d%d",&W,&H,&n,&R);
for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
int ans=0;
for(int i=0;i<=W;i++)
for(int j=0;j<=H;j++){
for(int k=0;k<n;k++){
//点到圆心的距离
double dist=(i-a[k].x)*(i-a[k].x)+(j-a[k].y)*(j-a[k].y);
if(dist<=R*R){ //圆心的半径更大,那么当前点一定再圆内
ans++; //等于的话就是再圆上
break;
}
}
}
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第八题:
题面:
思路:
1.对于每一次清理次数,可以直接遍历矩阵进行标记代表被清理过,最后统计没有被标记的格子数即可
2.如果数据范围大一点的话,可以考虑差分写,
时间复杂度 o(n*m*q) 最坏跑1e6
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=107;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
int vis[N][N]; //标记当前格子是否被清理过
void solve(){
scanf("%d%d",&n,&m);
int q; scanf("%d",&q);
while(q--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
vis[i][j]=1; //被清理过就标记为1
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!vis[i][j]) ans++;
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第九题:
题面:
思路1:朴素dfs
1.数据范围较小,可以直接dfs求答案
2.但是矩阵呈回子型,或者呈s型递增递减,最坏情况时间复杂度为o(n^4),这里就可能会超时
TLE_Code:C++(这里可能会超时,最坏1e8)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=307;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int dfs(int x,int y){
int res=1;
for(int i=0;i<4;i++){
int bx=dx[i]+x,by=dy[i]+y;
if(bx<1||by<1||bx>n||by>m) continue; //没有出界
if(a[x][y]>a[bx][by]) //当前值更大,就递归下一个坐标
res=max(res,dfs(bx,by)+1);
}
return res;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
//这里直接对每一个点dfs一遍,求最大值
int ans=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ans=max(ans,dfs(i,j));
}
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
思路2:记忆化搜索
1.可以再第一步的基础上,加上一个数组,记录答案,优化搜索次数,此时的时间复杂度会将为o(n^2)
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=307;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N][N];
int f[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int dfs(int x,int y){
int &res=f[x][y]; //用的引用,直接记录答案
if(res!=-1) return res; //记忆化·
res=1; //包括本身这个数
for(int i=0;i<4;i++){
int bx=dx[i]+x,by=dy[i]+y;
if(bx<1||by<1||bx>n||by>m) continue;
if(a[x][y]>a[bx][by])
res=max(res,dfs(bx,by)+1);
}
return res;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
memset(f,-1,sizeof f); //初始化为-1
int ans=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ans=max(ans,dfs(i,j));
}
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第十题:
题面:
思路:线段树
1.对每一个下标索引i,枚举一遍区间[i-k,i+k],时间复杂度是会超时的,故考虑优化
2.题目是区间查询最小值,很容易想到线段树,对每一个数区间查询最小值即可,这题算是线段树的最基本操作,大家务必掌握哈,
时间复杂度:o(nlogn)
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=1e6+7;
int const INF=0x3f3f3f3f;
int T;
int n,m,k;
int w[N];
struct Node{
int l,r,val;
}tr[N<<2];
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,w[r]};
else{
tr[u].l=l; tr[u].r=r; //记录区间
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
tr[u].val=min(tr[ls].val,tr[rs].val);
}
}
int query(int u,int l,int r){
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].val;
int res=1e9; //为了不影响答案更新,取一个INF
int mid=(tr[u].l+tr[u].r)>>1;
if(mid>=l) res=query(ls,l,r);
if(r>mid) res=min(res,query(rs,l,r));
return res;
}
void solve(){
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d",w+i);
build(1,1,n); //建树
scanf("%d",&k);
for(int i=1;i<=n;i++){ //对每个区间直接查询最小值
//这里要注意查询的区间,不然容易tle
int l=max(1,i-k),r=min(n,i+k); //左右区间
printf("%d ",query(1,l,r));
}
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第十一题:
题面:
思路:
1.直接模拟,大于1就折半(除2),并记录除2的次数
很奇怪,竟然不止10题,但是这题较为简单
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
void solve(){
double n; cin>>n;
int ans=0;
while(n>1) ans++,n/=2;
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
第十二题:
题面:
思路:单调栈
1.字典序最小最大问题,可以用单调栈解决
2.本题是删除k个字符使字典序最小,遍历字符串,维护一个单调不下降栈,若当前遍历的字符比栈顶元素更小则弹出栈顶元素,代表删除了一个字符,直到删除到k个字符(具体细节看代码)
3.如果到最后都没有删除k个字符,则从单调不下降栈中的栈顶位置开始删除,直到删除到k个字符,最后直接输出栈中元素就是答案
本题为最后一题,加油把这些题都给Ac了
AC_Code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
string s;
//再字符串s中,删除k个字符,是字典序最小
string get(string s,int k){
string st; //这里用string模拟栈
for(int i=0;i<n;i++){
while(st.size()&&s[i]<st.back()&&k){
st.pop_back(); //弹出栈顶元素
k--; //删除字符--
}
st.push_back(s[i]);
}
while(k--) st.pop_back(); //没有删除k个字符,则从栈顶往前删除
return st;
}
void solve(){
cin>>n>>m>>s;
cout<<get(s,m);
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}
苏格拉底曾说,世界上最快乐的事,莫过于为了梦想而奋斗
欢迎大家关注,点赞,收藏。
如有问题,欢迎大家指正
更多推荐
所有评论(0)