锐客网

  1. 首页 > it技术 > >

算法|第十三届蓝桥杯省赛C++ B组比赛有感

算法蓝桥杯

第十三届蓝桥杯省赛C++ B组比赛有感 个人感悟 ? 从高一开始接触计算机竞赛，非常喜欢这种编写代码的感觉，当一道道题目被AC的时候，那种喜悦的情感可能是非IOer不能感受的吧，六年的竞赛经历真的是跌宕起伏啊，从最开始初赛被刷到复赛爆零，到校内选拔赛逆袭同一学期拿下省一，准备高考，到自招改革，大一疫情，大二连打两场蓝桥杯最后是大三下的这一场比赛，也是这六年竞赛生涯的最后一场比赛了吧，希望能够光荣退役，结果什么已经无所谓了，可能唯一的遗憾是没能参加ACM比赛。
? 后面的话就全力准备考研跟找工作了，u1s1考研的话我对自己比较没有信心，毕竟作为一个英语学渣，考研英语给我带来的压力不是一般的大，不过我相信，一切总会变好的，加油！！！！我们终将上岸，拥有一个更美好的未来。
个人答案（写的不好勿喷，欢迎讨论） 代码就是考场写的代码
试题 A: 九进制转十进制 基础知识
【问题描述】
九进制正整数 ( 2022 ) 9 (2022)_9 (2022)9? 转换成十进制等于多少？
经典送分题，只要知识点你没忘，基本不会错
答案：
1478
试题 B: 顺子日期 模拟+生活常识
【问题描述】
? 小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日
期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺
子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；
而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022
年份中，一共有多少个顺子日期。
u1s1没有太看懂题干，012这样的算不算？
经典错误：日期天数1-99
本题的坑就是数据是要符合日期的，所有不符合的数据都不可以作为候选项
【算法|第十三届蓝桥杯省赛C++ B组比赛有感】答案：14（不知道对不对）或者4？
试题 C: 刷题统计 模拟
【问题描述】
? 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天
做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在
第几天实现做题数大于等于 n 题？
经典模拟题，n整除 5 ? a + 2 ? b 5*a+2*b 5?a+2?b得到几周，然后再对n取模，记得数据是1e18用long long
剩下的依次计算就好了

#include #include #include #include #define ll long long using namespace std; ll a,b,n; int main(){ cin>>a>>b>>n; ll sum=5*a+2*b; ll ans =(n/sum)*7; n=n%sum; int s1=0,s2=0; while(n>0&&s1<5){ n-=a; ans++; s1++; } while(n>0&&s2<2){ n-=b; ans++; s2++; } cout<

试题 D: 修剪灌木 找规律，数论，模拟
【问题描述】
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
解题思路：经典找规律，模拟
最长的情况肯定是当你刚剪完，到下次过来的时候的最长时间间隔，所以
m a x ( n o w ? l , r ? n o w ) ? 2 ; max(now-l,r-now)*2; max(now?l,r?now)?2;
当前位置到最左端和最右端的最大值的二倍
别问为啥用函数，问就是考试的时候 脑瘫了
#include #include #include #include using namespace std; int n; int ans(int l,int r,int now){ return max(now-l,r-now)*2; } int main(){ cin>>n; for(int i=1; i<=n; i++){ cout<

试题 E: X 进制减法 模拟
【问题描述】
进制规定了数字在数位上逢几进一。X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某
种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X 进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A ? B 的结果最小可能是多少。
请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。
本题坑点：仔细看看样例说明，A和B是怎么算出来的，其次如果当前i位做差出现负数该怎么选择进制
【样例输入】 11 3 10 4 0 3 1 2 0 【样例输出】 94

解题思路：
通过详读样例说明，我们可以知道第i位转化为十进制的方法是，第i位的值与前面i-1位的进制相乘，也就是说
A = 10 ? 5 ? 2 ? 1 + 4 ? 2 ? 1 + 0 ? 1 A=10*5*2*1+4*2*1+0*1 A=10?5?2?1+4?2?1+0?1
那么如果让差值最小，我们应当选择
当前第i位A和B中最大的数值+1,这里需要特殊处理0，因为最低2进制
这个时候 你肯定还会想之前的负数怎么办，如果我让负数的位置的进制为N是不是最小，聪明的同学应该发现了，负数不影响这个操作，如果修改进制为N，那么会导致这一位前面的所以数都要乘N，反而会变大。
所以这个程序的思路是，让每一位的进制为A和B中当前位最大的数值+1，就可以了，也就是让乘数尽可能的小，记得取模运算哦，多取几次不影响时间的，当然也别太多。
#include #include #include #include #define ll long long using namespace std; const int MAXSize = 100000+7; const ll mod = 1000000007; ll ans=0; ll a[MAXSize]={0},b[MAXSize]={0}; ll max(ll a,ll b){ if(a<=1&&b<=1){ return 2; } else{ return (a>b?a:b)+1; } } int main(){ ll n,m1,m2; ll s=1; cin>>n; cin>>m1; for(int i=m1-1; i>=0; i--){ cin>>a[i]; } cin>>m2; for(int i=m2-1; i>=0; i--){ cin>>b[i]; } int m = m1>m2?m1:m2; for(int i=0; i
试题 F: 统计子矩阵 模拟+数论（个人意见）
【问题描述】
给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
19
【评测用例规模与约定】
对于 30% 的数据，N, M ≤ 20.
对于 70% 的数据，N, M ≤ 100.
对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ A**i j ≤ 1000; 1 ≤ K ≤ 250000000.
解题思路：
四重for循环直接干他，优化思路，前缀和加数论（别看代码了，没写优化思路，没找到数论结果），数论应该是从最大的size矩阵找，然后满足条件的话那他的所以子矩阵都可以，但是要注意去重。要会用容斥原理
#include #include #include #include #define ll long long using namespace std; const int MAXsize = 507; ll A[MAXsize][MAXsize]; ll sum[MAXsize][MAXsize]; ll k; ll n,m; ll cal(int x,int y){ int tot=0; for(int i=n; i>=x; i--){ for(int j=m; j>=y; j--){ ll c = sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1]; if(c<=k){ tot++; } } } return tot; } int main(){ cin>>n>>m>>k; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ cin>>A[i][j]; sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+A[i][j]; } } ll ans=0; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ ans = ans + cal(i,j); } } cout<

试题 G: 积木画 数论（不是数论我把我头拧下来）
【问题描述】
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2个单位面积）和 L 型（大小为 3 个单位面积）：
算法|第十三届蓝桥杯省赛C++ B组比赛有感
文章图片

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？积木可以任意旋转，且画布的方向固定。
【输入格式】
输入一个整数 N，表示画布大小。
【输出格式】
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值
【评测用例规模与约定】
对于所有测试用例，1 ≤ N ≤ 10000000.
解题思路
做过一个跟这个题很像的，用的分治，不过那个是个N*M然后用L填充的，就清华大学算法分析与设计那本绿色的书上的题目，这个题，应该就是数论，毕竟数据范围摆在这里。
没做，数论直接放弃找规律 先写下面的暴力了。
试题 H: 扫雷 40% 改为图论 然后bfs
【问题描述】
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第 i 个炸雷( x i , y i , r i ) (x_i,y_i,r_i) (xi?,yi?,ri?) 表示在坐标 ( x i , y i ) (x_i,y_i) (xi?,yi?) 处存在一个炸雷，它的爆炸范围是以半径为r i r_i ri? 的一个圆。为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭表 ( x j , y j , r j ) (x_j,y_j,r_j) (xj?,yj?,rj?)表示这个排雷火箭将会在 处爆炸， ( x j , y j , r j ) (x_j,y_j,r_j) (xj?,yj?,rj?)它的爆炸范围是以半径为 r**j 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
算法|第十三届蓝桥杯省赛C++ B组比赛有感
文章图片

【样例输入】
2 1
2 2 4
4 4 2
0 0 5
【样例输出】
2
【样例说明】
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆
盖了炸雷 2，所以炸雷 2 也被排除
算法|第十三届蓝桥杯省赛C++ B组比赛有感
文章图片

【评测用例规模与约定】
对于 40% 的评测用例：0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 10^3, 1 ≤ r ≤ 10.
对于 100% 的评测用例：0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 5 × 10^4, 1 ≤ r ≤ 10.
一开始想的并查集，但是发现不管怎样都是N方的算法，就直接改建图加广搜了，并查集那么麻烦的。。。
#include #include #include #include #include using namespace std; struct edge{ int x,y,r; }; int n,m; const int MAXN = 1e4+7; bool fan[5*MAXN]={0}; edge D[5*MAXN]; queueq; vectorEdge[5*MAXN]; bool check(edge a,edge b){ return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))<=a.r*a.r; } int main(){ cin>>n>>m; for(int i=1; i<=n; i++){ fan[i]=true; cin>>D[i].x>>D[i].y>>D[i].r; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(check(D[i],D[j])){ Edge[i].push_back(j); } } } int tot=0; for(int i=1; i<=m; i++){ edge s; cin>>s.x>>s.y>>s.r; for(int j=1; j<=n; j++){ if(fan[j]==1&&check(s,D[j])){ q.push(j); tot++; fan[j]=0; while(!q.empty()){ int now = q.front(); q.pop(); for(int l=0; l

试题 I: 李白打酒加强版 40%dfs 100%数论
【问题描述】
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。
【输入格式】
第一行包含两个整数 N 和 M.
【输出格式】
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。
【样例输入】
5 10
【样例输出】
14
【样例说明】
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
【评测用例规模与约定】
对于 40% 的评测用例：1 ≤ N, M ≤ 10。
对于 100% 的评测用例：1 ≤ N, M ≤ 100。
解题思路：40%DFS+剪枝，100%的话应该会跟组合数啥的有关系
#include #include #include #include #include #include using namespace std; #define ll long long ll ans=0; ll mod=1000000007; int N,M; void dfs(int n,int m,int now){ if(now==0&&m==0&&n==0){ ans=(ans+1)%mod; return; } else{ if(now-1>=0&&m-1>=0) dfs(n,m-1,now-1); if(n-1>=0&&m>0) dfs(n-1,m,now*2); } } int main(){ cin>>N>>M; dfs(N,M,2); cout<

试题 J: 砍竹子 20%暴力 100%预处理+模拟
【问题描述】
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 h i h_i hi?.他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为$ ? \sqrt{? \frac{H}{2} ? + 1}?$，其中 ?x? 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。
【输入格式】
第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 h i h_i hi?，表示每棵竹子的高度。
【输出格式】
一个整数表示答案。
【样例输入】
6
2 1 4 2 6 7
【样例输出】
5
解题思路：
首先我们需要利用好题目给我们的公式，反向算出那些区间的数字会在经过一次魔法之后变为相同的数字，我们进行一下预处理
void cal(ll h){ ll s=2; c[0]=0; c[1]=1; tot++; while(s<=h&&s>0){ c[++tot]=s; s=(s*s-1)*2; } c[++tot]=s; }

tot是第几个区间也就是他如果降为0需要施法几次，然后我们从2开始反向计算，因为h最大1e18所以 肯定会炸精度，所以循环的时候带上s要大于0
之后我们对这个数组顺序访问，当第a[i]>a[i-1]时就需要对a[i]施展魔法将他降到a[i-1]那个区间的高度，如果a[i]与a[i-1]同属于一个魔法区间高度，那么我们需要对他进行至少一次魔法
所以代码如下：
#include #include #include #include #define ll long long using namespace std; const int MAXN=2e5+7; ll a[MAXN]; ll c[MAXN]; int tot=0; int n; void cal(ll h){ ll s=2; c[0]=0; c[1]=1; tot++; while(s<=h&&s>0){ c[++tot]=s; s=(s*s-1)*2; } c[++tot]=s; } int main(){ cin>>n; ll ans=0; ll h=0; for(int i=1; i<=n; i++){ cin>>a[i]; h= a[i]>h?a[i]:h; } cal(h); for(int i=1; i<=n; i++){ if(a[i]>a[i-1]){ int x=-1,y=-1; for(int j=1; j<=tot; j++){ if(a[i]>=c[j-1]&&a[i]=c[j-1]&&a[i-1]
总结 总体来说本次的蓝桥杯省赛没有去年的难，但是这个数据量确实很大，需要进行一些处理，比较麻烦，还有就是蓝桥每年都会有一两个题的描述不清楚，总是不知道他的意思，样例给的还不包含那种情况 就很苟。

    推荐阅读


    上一篇：题解|第十三届蓝桥杯大赛软件赛省赛B组(个人思路)

    下一篇：2021年质量员-市政方向-通用基础(质量员)免费试题及质量员-市政方向-通用基础(质量员)考试技巧