第17届蓝桥杯省赛题目及解析【B组】

各个题目地址一.[蓝桥杯 2026 省 B] 青春常数二.[蓝桥杯 2026 省 B] 双碳战略三.[蓝桥杯 2026 省 B] 循环右移四.[蓝桥杯 2026 省 B] 蓝桥竞技五.[蓝桥杯 2026 省 B] LQ 聚合六.[蓝桥杯 2026 省 B] 应急布线七.[蓝桥杯 2026 省 B] 理想温度八.[蓝桥杯 2026 省 B] 足球训练gitee仓库地址【传送门】一. [蓝桥杯 2026 省 B]青春常数题目描述解题思路此题属于送分题因为题目需要xy所以x的取值就只能是0~⌊ N / 2 ⌋ \lfloor N/2 \rfloor⌊N/2⌋所以最后的答案就是⌊ N / 2 ⌋ \lfloor N/2 \rfloor⌊N/2⌋1#includeiostreamusingnamespacestd;intmain(){longlonga2026202520242023;couta/21endl;return0;}其实我刚看到这题的时候不小心灵机一动从0开始遍历到N/2…哈二. [蓝桥杯 2026 省 B]双碳战略题目描述解题思路这一题填空题对于在考场上的我来说算是很难的了基本上就没有什么思路主要刷题的数量和做题的经验还是太少了像遇到这种类型的题目的话因为是填空题所以直接打表找规律这里解释一下打表就是先通过题意用暴力或者其他方法解出一些当数据范围比较小时的答案然后在这些数据范围小的答案里面去找整体的规律就比如这一题题目上说的是找2026个灯的情况我们就可以先找假如只有3盏灯或者4盏灯的情况的所有答案再去找规律首先就遇到了一个问题怎么打表其实只要理解清楚题意就不难想到当数据范围小一些时其实可以使用bfs来搜索出到达所有状态的最少步数所以接下来就应该分析题目所给的条件来确定bfs里面的每一个状态需要如何到达这里需要注意题目中说的主控系统必须严格按照“双向交替”的规则执行操作也就是说假设这一次执行完奇数次操作后后面的灯全部状态反转那下一次的操作就必须是要执行偶数次的操作根据这样的性质我们就可以对于当前的状态枚举所有的路灯以该路灯为要操作的路灯i因为现在要找当前状态的下一步所以就要判断从初始状态到当前状态的步数如果是奇数次那么要找的下一个状态就要执行偶数次状态的操作反转前面灯的状态如果是偶数就执行奇数次的操作反转后面灯的状态bfs代码如下voidbfs(){intn;cinn;//可以自定义一个灯的数量来打表找规律vectorints(2026);//初始状态queuevectorq;mapvectorint,intdist;q.push(s);dist[s]0;while(q.size()){autoaq.front();q.pop();for(inti0;in;i){autotmpa;//判断初始状态到当前状态的步数if(dist[a]%2!0){//为奇数 所以要执行偶数次的操作for(intj0;ji;j)tmp[j]^1;//将每个状态反转}else{for(intji;jn;j)tmp[j]^1;}if(!dist.count(tmp)){dist[tmp]dist[a]1;//第一次到达tmp状态的步数就是最短步数q.push(tmp);}}}//while循环的括号intans0;//到所有状态步数的总和for(autot:dist){autovt.first;autocntt.second;anscnt;for(intn:v){coutn ;}cout步数为cntendl;}coutansendl;}将代码放在一个完整的程序中运行就会发现当n3时步数0 1 3 1 2 2 2 1此时 0有1个 1有3个 2有3个 3有一个 即1 3 3 1当n4时步数0 1 3 1 3 4 3 1 2 2 3 2 2 2 2 1此时 0有1个 1有4个 2有6个 3有4个 4有1个 即1 4 6 4 1我们发现这刚好是杨辉三角形啊所以最后的结果就是∑ i 1 n C 2026 i ∗ i \sum_{i1}^{n} C_{2026}^{i}*i∑i1n​C2026i​∗i这个最后的就交给你们自己去计算啦有代码需要参考的可以看我的gitee仓库【gitee仓库地址】三. [蓝桥杯 2026 省 B] 循环右移题目描述解题思路这题其实有个条件2的限定就很简单了作为第一道大题其实也就是送分题题目中要求对其进行一次循环右移操作得到的新子数组与原数组完全一致其实列举一下就会发现要满足条件二只有当数组全部的元素都相同是才会满足的只要有一个是不同的那么它们循环右移得出来的就一定不会和之前的相同所以对于每一组的数据答案就是y − x 1 0 ? y − x 1 : 0 ; y-x10 ?y-x1:0;y−x10?y−x1:0;因为比较简单就不过多解释代码参考可以看我的gitee仓库【gitee仓库地址】四. [蓝桥杯 2026 省 B] 蓝桥竞技题目描述解题思路题目中说组成战队的条件就是需要有5个职业互不相同的人或许有的人在考场上面第一个想到的是模拟但是我们可以看一下这个数据范围就T*N最大都能到达10^8了所以直接模拟肯定是不行的所以就要有条件判断定义一个sum记录全部人数的总和条件一sum%50因为每次都是选5个人组成一个战队所以要想最后没有剩余的人那么总人数一定要是5的倍数记录所有职业中人数的最大值a条件二s u m / 5 a sum/5asum/5a由sum的定义就可以知道sum/5其实就是能组成战队的数量因为题目说了每个战队一个职业只能有一个人所以要想将人全部分配完肯定是要满足任意一个职业的总人数不能比总战队数量更多所以我们只需要判断职业人数最多的那个不大于总战队数量就可以了代码实现#includeiostream#includequeue#includevectorusingnamespacestd;intmain(){intT;cinT;while(T--){intn;longlongsum0,a0;cinn;for(inti1;in;i){longlongx;cinx;sumx;amax(a,x);}if(sum%5!0){coutFendl;continue;}if(asum/5)coutTendl;elsecoutFendl;}return0;}五. [蓝桥杯 2026 省 B] LQ 聚合题目描述解题思路根据题意需要修改字符串中的’?来使得整个字符串的前’L’后‘Q’的对数最多乘积最大也就是只能改变’?’因为题目要求最大的LQ的对数我们先不考虑’?‘之外的位置假设我现在字符串中有6个’?需要去填为了能保证LQ最大我们是不是至少应该要保证在我能改变的地方L一定要在Q的后面因为L如果在Q的后面了LQ的对数是一定会小于L在Q的前面的以下是证明就以此时红框中的L为例此时它所能匹配到的LQ对数是3对此时我将它和后面任意一个Q来交换位置我们会发现此时不仅原来的L能匹配的LQ对数减少到了1对就连下图中蓝色的L所能匹配的LQ对数也减少了所以假设字符串里面只有6个’?‘那么最优的’?排列结果一定是以下的几种情况Q Q Q Q Q QL Q Q Q Q QL L Q Q Q QL L L Q Q QL L L L Q QL L L L L QL L L L L L所以我们最终的解题思路就是枚举这几种状态求出每种状态的LQ对数取出最大的LQ对数就可以了这里讲一下代码的思路1首先用一个临时变量t将第一种情况中LQ对数记录起来还要赋值给最后的答案ans2用第一种情况创建Q的后缀数组sqsq[ i ]即从最后一个位置到i位置一共出现了多少次Q3遍历整个字符串用变量cur记录已经出现过的L的数量每当遇到一个’?‘我们就可以看成将这个’?改成了L所以此时整个字符串的LQ对数是t − c u r s q [ i 1 ] t-cursq[i1]t−cursq[i1]再拿这个新的LQ对数维护ans的值取最大代码实现注代码中的变量名字不和上面讲解的完全一样#includeiostreamusingnamespacestd;typedeflonglongLL;constintN1e510;intsq[N];///后缀和数组intmain(){intn;string s;cinns;s s;intcntL0;LL cur0;//初始时先把所有的‘’当成Qfor(inti1;in;i){if(s[i]L)cntL;else{curcntL;//先算出所有问号都是Q的情况}}LL retcur;//计算Q字符出现次数的后缀和for(intin;i1;i--){sq[i]sq[i1];if(s[i]!L)sq[i];}cntL0;for(inti1;in;i){if(s[i]L)cntL;elseif(s[i]?){//将原本的Q替换成L 所以需要减去原先Q匹配的前面的Lcur-cntL;cursq[i1];cntL;retmax(ret,cur);}}coutret;return0;}六. [蓝桥杯 2026 省 B] 应急布线【本题链接】题目描述解题思路这题的第一问就是一个最普通的并查集主要的坑点在于第二问但是如果理解了的话第二问也是很简单的这里大概讲一下并查集并查集的作用1查找某个元素在哪个集合中2判断两个元素是否属于同一个集合3将两个元素所在的集合合并成一个集合这里注意是将它们所在的集合合并成一个集合不是将两个元素合并成一个集合并查集的实现并查集的实现原理主要是用树来表示集合使用一个数组就可以存储所有的元素然后存储的方式使用双亲表示法存储每个元素都存储它们的父亲节点还有一点很重要的是并查集中每个集合都是由一个确定的元素代表的因为是树来存储所以自然就是这个树的根节点来代表这个集合以下是并查集的模板#includeiostreamusingnamespacestd;constintN2e510;intfa[N];//初始化voidini(intn){for(inti1;in;i){fa[i]i;}}//查询intfind(intx){if(xfa[x])returnx;returnfa[x]find(fa[x]);}//将x所在集合与y所在集合合并起来voidun(intx,inty){intfxfind(x);intfyfind(y);fa[fx]fy;}//判断两个元素是否属于同一个集合boolissame(intx,inty){returnfind(x)find(y);}注这里还放了一道并查集模板题供给不熟悉并查集的读者练习巩固【模板】并查集题目中无非就是还留有网线相连的两台电脑合并在一个集合里面最后可以得出来一共有多少个集合n那么需要的最少的网线数量就是kn-1题目中说的确保跳线总数最少的前提下单台计算机接入跳线数量最大值的最小可能值这里定义每台电脑所连接的线的数量叫做度我们发现假如要用一条线连接两台电脑是不是代表着这两台电脑的度各自都多了1如果将它们看成一个整体的话就是这个整体的度加了2因为我们上面已经求出来了最少需要的跳线数量k所以如果要加上k根线是不是就代表着这整个大集合的度加了2*k(也可以看成此时就有k * 2个度需要分配给所有的电脑)所以要电脑最大接线数最少其实就是要将这 k * 2 个度平均分配给所有的电脑所以最后的值就是⌈2 * k/n⌉为了不让整篇文章过于的长所以这题的代码就放在我的gtiee仓库里面【gtiee仓库地址】当然如果有任何的建议都欢迎在评论区留言七. [蓝桥杯 2026 省 B] 理想温度题目描述解题思路对于所有评测用例保证1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×105,− 10 9 ≤ A i , B i ≤ 10 9 -10^9 \le A_i, B_i \le 10^9−109≤Ai​,Bi​≤109。首先我这里要给读者提醒千万要想到有些状态是初始时已经到达了理想温度了所以要记得考虑这种情况的限制可能会有的读者在比赛时和我一样没有考虑到有的状态时已经到达了理想的温度了就想到那这题不就是简单的求某个元素的最大的出现次数吗这样就是错的因为可能区间里面有很多的已经达到理想温度的了所以直接这样求就属于是“假贪心”情况没有考虑到位这题应该不难想到可以先预处理一个数组c [ i ] b [ i ] − a [ i ] c[i]b[i]-a[i]c[i]b[i]−a[i],c [ i ] c[i]c[i]代表的就是i ii位置到达理想温度需要的温度,我们要让最多的传感器到理想温度其实就是要在某个区间加上一个k kk值在c数组上选择一个区间[ l e f t , r i g h t ] [left,right][left,right]给区间每个传感器加k kk温度那么在这个区间中c [ i ] ! k 的地方对符合理想温度传感器的总数的贡献为 0 c [ i ] 0 的贡献为 − 1 ; c [ i ] k 的贡献为 1 c[i] ! k的地方对符合理想温度传感器的总数的贡献为0c[i]0的贡献为-1;c[i]k的贡献为1c[i]!k的地方对符合理想温度传感器的总数的贡献为0c[i]0的贡献为−1;c[i]k的贡献为1其实主要的思路就是对于c[i]0的地方它本就已经到达理想温度了现在再加上k会导致符合理想温度的传感器减少1所以它对到达理想温度传感器的总数的贡献就可以看成是-1其他两种情况也是这样理解(本质上就是把它们看成01-1的权值)知道了上面的性质后现在的问题是找到一个温度k kk使得在某个区间加上这个温度k kk可以让到达理想温度的传感器数量最多由上面的性质我们可以根据k kk值将数组转化成只有-101的数组此时这个问题就转化成了找到一个温度k kk使得转化后的数组的最大子段和最大【最大子段和概念】给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大上面转化后的数组代表的是在这个k值下每个位置对到达理想温度传感器总数的贡献但是这个k kk是不确定的所以我们就可以采取枚举数组c中的所有值当作k最终思路枚举所有可能的k值算出每个k值转化后的数组的最大子段和取其中的最大值即可代码实现#includeiostream#includemapusingnamespacestd;constintN2e510;intc[N];intn;intmain(){cinn;for(inti1;in;i)scanf(%d,c[i]);for(inti1;in;i){intb;scanf(%d,b);c[i]b-c[i];}intret0,cur0;//ret是枚举k求最大子段和的最大值 cur当前位置0出现的次数mapint,intmn,cnt;//mn[k]代表的是以k为温度时最小的前缀和 cnt是k温度当前在c数中出现的次数for(inti1;in;i){intkc[i];if(k0)cur;else{if(!cnt.count(k))mn[k]cnt[k]-cur;//k第一次出现的话最小前缀和就是cnt[k] - curelsemn[k]min(mn[k],cnt[k]-cur);//时刻维护最小的前缀和cnt[k];retmax(ret,cnt[k]-cur-mn[k]);//维护结果}}//最后的结果是整个c数组0的总数区间处理后得出来得新的到达理想温度传感器的数量coutcurretendl;return0;}第八题作者自己也不是很会有兴趣得读者可以再取研究一下【第八题题目地址】