蓝桥杯刷题周计划（第四周)

前言

大家好！我是 EnigmaCoder。

• 本文是我蓝桥杯刷题计划的第四周。附：蓝桥杯刷题周计划（第三周)
• 本文含有16题，每道题分为题目、代码、题解分析三部分，且附有原题链接。
• 希望能帮助到大家！

题目一

原题链接：lanqiao19723

题目

问题描述
小蓝最近学习了一种神奇的队列： 分布式队列。简单来说，分布式队列包含 N 个节点（编号为 0 至 N−1，其中 0 号为主节点），其中只有一个主节点，其余为副节点。

主/副节点中都各自维护着一个队列，当往分布式队列中添加元素时，都是由主节点完成的（每次都会添加元素到主节点对应的队列的尾部）；副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组，下标为0,1,2,3…，同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。给出一个分布式队列的运行状态，所有的操作都按输入顺序执行。你需要回答在某个时刻，队列中有多少个元素具有可见性。

输入格式
第一行包含一个整数 N，表示节点个数。

接下来包含多行输入，每一行包含一个操作，操作类型共有以下三种： add、sync 和 query，各自的输入格式如下addelement： 表示这是一个添加操作，将元素 element 添加到队列中;syncfollower id： 表示这是一个同步操作，follower id 号副节点会从主节点中同步下一个自己缺失的元素;query： 查询操作，询问当前分布式队列中有多少个元素具有可见性。

输出格式
对于每一个 query 操作，输出一行，包含一个整数表示答案。

样例输入
3
add 1
add 2
query
add 1
sync 1
sync 1
sync 2
query
sync 1
query
sync 2
sync 2
sync 1
query

样例输出

0
1
1
3

代码

#include <bits/stdc++.h>
using namespace std;
const int N=15;
int a[N];int main()
{int n;cin>>n;string s;while(cin>>s){if(s=="add"){int t;cin>>t;a[0]++;}else if(s=="sync"){int t;cin>>t;a[t]=min(a[t]+1,a[0]);}else{cout<< *min_element(a+1,a+n)<<endl;}}return 0;
}

题解分析

• 数组a：a[0]记录主节点添加的总元素数，a[1..n-1]记录各副节点已同步的元素数。
• add操作：增加主节点的元素计数。
• sync操作：更新对应副节点的同步进度，确保不超过主节点的当前总数。
• query操作：计算所有副节点同步进度的最小值，即为可见元素的数量。

题目二

原题链接：lanqiao2271

题目

问题描述
小蓝每周六、周日都晨跑，每月的 1、11、21、31日也晨跑。其它时间不晨跑。

已知 2022 年 1 月 1 日是周六，请问小蓝整个 2022 年晨跑多少天？

代码

#include <iostream>
using namespace std;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};bool is_leap(int y){if(y%4==0&&y%100!=0||y%400==0)return true;return false;
}
int main()
{int ans=0,day=0;if(is_leap(2022))month[2]=29;for(int m=1;m<=12;m++){day+=month[m-1];for(int d=1;d<=month[m];d++){if((day+d)%7==1||(day+d)%7==2||d==1||d==11||d==21||d==31)ans++;}}cout<<ans;return 0;
}

题解分析

本题是日期模拟题。

题目三

原题链接：lanqiao1135

题目

问题描述

蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。

小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：

小明会用红绳连接两名学生，被连中的两个学生将成为朋友。

小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。

输入描述

第 11 行包含两个正整数 N,M，其中 NN 表示蓝桥幼儿园的学生数量，学生的编号分别为 1∼N。

之后的第 2∼M+1 行每行输入三个整数，op,x,y：

• 如果 op=1，表示小明用红绳连接了学生 xx 和学生 y 。
• 如果 op=2，请你回答小明学生 x和 学生 y是否为朋友。

1≤N,M≤2×10⁵，1≤x,y≤N。

输出描述

对于每个 op=2的输入，如果 x和 y是朋友，则输出一行 YES，否则输出一行 NO。

输入输出样例

示例 1

输入

5 5 
2 1 2
1 1 3
2 1 3
1 2 3 
2 1 2

输出

NO
YES
YES

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int root(int x){return a[x]=(a[x]==x?x:root(a[x]));
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)a[i]=i;while(m--){int op,x,y;cin>>op>>x>>y;if(op==1){a[root(x)]=root(y);}else{cout<<(root(x)==root(y)?"YES":"NO")<<endl;}}return 0;
}

题解分析

本题考察并查集。

• 初始化：数组 a 表示每个节点的父节点，初始时每个节点的父节点指向自己（a[i] = i）。

• 合并操作（op=1）：将节点x和 y 所在的集合合并。通过找到它们的根节点，将其中一个根节点的父节点指向另一个根节点，实现集合的合并。

• 查询操作（op=2）：检查节点 x 和y是否属于同一集合，即它们的根节点是否相同。

题目四

原题链接：lanqiao6267

题目

问题描述
有的数转换为二进制之后，正好有3 个数位为 1 。例如 7 转换为二进制为 111，有 3 个数位为 1 ；又如 11 转换为二进制为 1011，有 3 个数位为 1。满足条件的前几个数依次为：7, 11, 13, 14, 19, 21， ……请问，第 23 个满足条件的数是多少？

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码

#include <iostream>
using namespace std;
int main()
{int num=0,i;for(i=1;i<=100000;i++){int t=i,w=0;while(t){if(t&1)w++;t>>=1;}if(w==3)num++;if(num==23)break;}cout<<i;return 0;
}

题解分析

本题是位运算题。

• t&1可以判断低位是否为1。
• t>>=1表示t的二进制位向右移1位。

题目五

原题链接：lanqiao12468

题目

问题描述
小蓝刚学习完二进制知识，所以现在他对任何数字的二进制都特别感兴趣。恰好即将迎来
2024 年，他想知道 2024 的二进制中有几个 1？

请你帮忙解决这个问题

输入格式
本题为填空题，无输入。

输出格式
输出一个整数表示答案。

代码

#include <iostream>
using namespace std;
int main()
{int t=2024;int ans=0;while(t){if(t&1)ans++;t>>=1;}cout<<ans;return 0;
}

题解分析

本题同样为位运算题。

题目六

原题链接：lanqiao18165

题目

代码

#include <iostream>
using namespace std;
using ll=long long;ll fun(ll x){if(x<=10)return ((x%998244353)*((x-1)%998244353))%998244353;else return ((2*x)%998244353*(fun(x-6)%998244353))%998244353;
}
int main()
{ll x;cin>>x;cout<<fun(x);return 0;
}

题解分析

本题为递归和模运算的结合。

• 按题递归即可。
• 使用乘法模运算规则。

题目七

原题链接：lanqiao2122

题目

问题描述
小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6, 小于 409 的数位 之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数 n,m, 请问对 1 到 n 采用这种方法排序时, 排在第 m 个的元 素是多少?

输入格式
输入第一行包含一个正整数 n 。

第二行包含一个正整数 m 。

输出格式
输出一行包含一个整数, 表示答案。

样例输入
13
5
样例输出
3
样例说明

1 到 13 的排序为: 1,102,11,3,12,4,13,5,6,7,8,9 。第 5 个数为 3 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];int num(int x){int sum=0;while(x){sum+=x%10;x/=10;}return sum;}bool compare(int a,int b){int x1=num(a);int x2=num(b);if(x1==x2)return a<b;else return x1<x2;}int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)a[i]=i;sort(a+1,a+1+n,compare);cout<<a[m];return 0;
}

题解分析

本题是自定义排序题。

• num函数来计算数位之和。
• compare函数根据题意制定排序规则。

题目八

原题链接：lanqiao19733

题目

问题描述

在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字 1、2、3、5、7 都没有形成封闭图形，而数字 0、4、6、9 分别形成了 1个封闭图形，数字 8则形成了 2个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 68，由于 6 形成了 1 个封闭图形，而 8 形成了 2个，所以 68 形成的封闭图形的个数总共为 3。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 4141 和数字 1818，它们对应的封闭图形的个数分别为 1 和 2，因此数字 41 小于数字 18。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 14和数字 41，它们的封闭图形的个数都是 11，但 14<41，所以数字 14小于数字 41。 如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 n个数 a1,a2,…,an，请你按照蓝桥王国的数字大小规则，将这 nn 数从小到大排序，并输出排序后结果。

输入格式

第一行包含一个整数 n，表示给定的数字个数。

第二行包含 n个整数 a1,a2,…,an，表示待排序的数字。

输出格式

输出一行，包含 n个整数，表示按照蓝桥王国的数字大小规则从小到大排序后的结果，每两个数字之间用一个空格分隔。

样例输入

3
18 29 6

样例输出

6 29 18

样例说明

对于给定的数字序列 [18,29,6]，数字 18的封闭图形个数为 2，数字 29 的封闭图形个数为 1，数字 6 的封闭图形个数为 1。按照封闭图形个数从小到大排序后，得到 [29,6,18]。

由于数字 2929 和数字 66 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 [6,29,18]。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
using ll=long long;
ll a[N];ll num(ll x){ll sum=0;while(x){if(x%10==8)sum+=2;else if(x%10==0||x%10==4||x%10==6||x%10==9)sum+=1;x/=10;}return sum;
}bool compare(ll x,ll y){ll sum1=num(x),sum2=num(y);if(sum1==sum2)return x<y;else return sum1<sum2;
}int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1,compare);for(int i=1;i<=n;i++)cout<<a[i]<<' ';return 0;
}

题解分析

本题仍然为自定义排序题。

题目九

原题链接：lanqiao1264

题目

题目描述

给定一个长度为 n的数组 a 。

给定一个长度为 mm 的互不相同的数组 p , 意味着你可以交换 a[pi]和 a[pi+1]任意次。

请确定是否可以用仅允许的交换方式使得 aa 数组非严格递减。

输入描述

第一行输入一个 n和 m。

第二行输入 n个整数 a1,a2,…,an 。

第三行输入 m个整数 p1,p2,p3,…,pm

1≤m<n≤10³,1≤ai≤n,1≤pi<n

输出描述

如果可以输出 YES ，否则输出 NO 。

输入输出样例

示例 1

输入

3 2
3 2 1
1 2

输出

YES

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N],p[N];int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];while(m--){int x;cin>>x;p[x]=p[x+1]=1;}for(int i=1;i<n;i++){for(int j=1;j<n-i;j++){if(p[j]==1&&p[j+1]==1){if(a[j]>=a[j+1])swap(a[j],a[j+1]);}else {cout<<"NO";return 0;}}}cout<<"YES";return 0;
}

题解分析

本题为冒泡排序的变式题。

题目十

原题链接：lanqiao1514

题目

题目描述

输入 b，p，k 的值，求 b^pmod k 的值。其中 2≤b,p,k≤10⁹ 。

输入描述

三个整数 b,p,kb,p,k。

输出描述

输出 b^pmod k=s，s 为运算结果。

输入输出样例

示例

输入

2 10 9

输出

7

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll qmi(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p,b>>=1;}return res;
} 
int main()
{ll b,p,k;cin>>b>>p>>k;cout<<qmi(b,p,k);return 0;
}

题解分析

本题为快速幂的模版题，注意两次取模。
2&tag_relation=union)

题目

题目描述

输入 b，p，k 的值，求 b^pmod k 的值。其中 2≤b,p,k≤10⁹ 。

输入描述

三个整数 b,p,kb,p,k。

输出描述

输出 b^pmod k=s，s 为运算结果。

输入输出样例

示例

输入

2 10 9

输出

7

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll qmi(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p,b>>=1;}return res;
} 
int main()
{ll b,p,k;cin>>b>>p>>k;cout<<qmi(b,p,k);return 0;
}

题解分析

本题为快速幂的模版题，注意两次取模。

题目十一

原题链接：lanqiao18440

题目

问题描述
给定一个 n×m 大小的矩阵 A。

给定 q 组操作，每次操作为给定 5 个正整数 x,1,x2,y2,x 1 ,y 1 ,x ,y 2,d，Ax1,y1A x 1 ,y 1 是子矩阵左上角端点，Ax2,y2A x ,y 2是子矩阵右下角端点，你需要给其中每个元素都增加 d。输出操作结束后的矩阵 A。

输入格式

第一行输入 3 个正整数 n,m q。（1≤n,m≤103,1≤q≤105 ）

接下来 n 行每行输入 m 个整数，表示 Ai,j A ,j 。(−103≤i,j≤13,1≤i≤n,1≤j≤m)

接下来 q 行，每行输入 5 个正整数 x1,y1,x2,y2,dx 1 。(1≤x1≤x2≤n,1≤y1≤y2≤m,−103≤d≤103)

输出
输出 n 行 m 个整数，表示操作结束后的矩阵 A。

样例输入
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
样例输出
2 3 4 1
4 3 4 1
2 2 2 2

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N];
int b[N][N];
int main()
{int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];b[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1];}}while(q--){int x1,x2,y1,y2,d;cin>>x1>>y1>>x2>>y2>>d;b[x1][y1]+=d;b[x1][y2+1]-=d;b[x2+1][y1]-=d;b[x2+1][y2+1]+=d;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=b[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];cout<<a[i][j]<<" ";}cout<<endl;} return 0;
}

题解分析

本题是二维差分的模板题，使用模板解题即可。

题目十二

原题链接：lanqiao4169

题目

问题描述

鸡哥在“无尽的夏日”购物节上看中了一系列的商品，这些商品的价格各不相同。然而，鸡哥的购物车有一条特殊的规则：购物车中的商品数量必须是偶数个。

鸡哥希望在满足购物车规则的前提下，选择总价值最高的商品。他将商品的价格列表给了你，希望你能帮他计算出他能购买到的商品的最高总价值是多少。

输入格式

第一行包含一个整数 N（2≤N≤105），表示商品的数量。

第二行包含 N个整数，表示每个商品的价格 Ai（−109≤Ai≤109）。

输出格式

输出一行，表示鸡哥能购买到的商品的最高总价值。

样例输入

5
1 2 3 4 5

样例输出

14

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using ll=long long;
ll a[N];
int main()
{ll n;cin>>n; ll sum=0,count=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>=0){sum+=a[i];count++;}}sort(a+1,a+1+n,greater<ll>());if(count%2==0){cout<<sum;}else if(count==0){cout<<a[1]+a[2];}else{cout<<max(sum-a[count],sum+a[count+1]);}return 0;
}

题解分析

本题是一道贪心题。

• 首先进行降序排序，正数商品个数为偶数就全买。
• 如果是奇数个，就在舍弃正数最小值和加上负数最大值间，取两者的最大值。
• 如果没有非负数，则取最大的两个负数。

题目十三

原题链接：lanqiao19695

题目

问题描述
小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 7 个人，这 7 人彼此之间没有进行握手 (但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?

注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码

#include <iostream>
using namespace std;
int main()
{int sum=0;for(int i=49;i>=7;i--)sum+=i;cout<<sum;return 0;
}

题解分析

由题意可知，每个人都要与除自己以外的其他所有人进行一次握手 ，所以第50名的人握手49次，49名握手48次……第8名握手7次，将他们累加即可。

题目一

原题链接：lanqiao19709

题目

问题描述
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯ ) 上的数字是偶数，我们就称之为 “好数”。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

输入格式
一个整数 N。

输出格式
一个整数代表答案。

样例输入1
24
样例输出 1
7
样例输入 2
2024
样例输出 2
150
样例说明
对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

代码

#include <iostream>
using namespace std;
const int N=10;
int a[N];int main()
{int n,sum=0;cin>>n;for(int i=1;i<=n;i++){int t=i,k=1;while(t){int e=t%10;a[k++]=e;t/=10;}int j;for(j=1;j<k;j++){if((j%2==1&&a[j]%2!=1)||(j%2==0&&a[j]%2!=0))break;}if(j==k)sum++;}cout<<sum;return 0;
}

题解分析

本题暴力解题即可。

题目二

原题链接：lanqiao673

题目

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

有些人很迷信数字，比如带 “4”
的数字，认为和“死”谐音，就觉得不吉利。 虽然这些说法纯属无稽之谈，但有时还要迎合大众的需求。某抽奖活动的奖券号码是 5 位数（10000−99999），要求其中不要出现带 “4” 的号码。

主办单位请你计算一下，如果任何两张奖券不重号，最多可发出奖券多少张。

代码

#include <iostream>
using namespace std;
int main()
{int sum=99999-10000;for(int i=10000;i<=99999;i++){int t=i;while(t){if(t%10==4){sum--;break;}t/=10;}}cout<<sum+1;return 0;
}

题解分析

本题仍然使用暴力解题。

题目三

原题链接：lanqiao4050

题目

问题描述
在烬寂海中居住着某种智慧生物。它们的文明发展程度相当于地球上的中世纪，但是它们拥有强大的科技与魔法。

一天，王国的法师得到了一段古老的魔法咒文，咒文中似乎隐藏着巨大的能量，但是咒文中有很多相似的字符串片段，法师们相信这些片段与魔法的启动有关。

现在，国王决定招募聪明的你，使用你的技术能力来帮助法师们解开这个谜团。

现在给你一个字符串S（主串），还有若干个模式串 P。你需要统计每一个模式串在主串中出现的次数。

输入格式
第一行：一个字符串 S，表示主串，只包含小写英文字母。

第二行：一个整数 n，表示有 n 个模式串。

接下来的 n 行：每行一个字符串，代表一个模式串 P，只包含小写英文字母。

输出格式
n 行，每行一个整数，表示对应模式串在主串中出现的次数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1010;
char s[N],p[M];
int nex[M];int KMP(int n,int m){int sum=0;for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;} for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])j=nex[j];if(s[i]==p[j+1])j++;if(j==m)sum++;}return sum;
}int main()
{cin>>s+1;int k;cin>>k;int n=strlen(s+1);while(k--){cin>>p+1;int m=strlen(p+1);cout<<KMP(n,m)<<endl;}return 0;
}

题解分析

本题使用KMP模板解题。