第十七届蓝桥杯省赛c++b组题解

蓝桥杯省赛自测（CB 组） - 洛谷 洛谷自测链接(由于数据原因 真实成绩可能与官方成绩有所出入)

1.青春常数

非常简单的入门题目 一共四年，前两年总和要小于后两年 即x+y=2026202520242023且x<y算出x的最大值即可(注意！x可以为0 所以最大值还需要+1)

最后的答案为1013101260121012

2.双碳战略

完全没有思路的一道题 考场上想用dfs暴搜怕电脑炸了 据说答案是792264670

3.循环右移

也是一道入门的贪心题 题目看起来像数学题 但是仔细一想就知道不管怎么进行循环右移都与原来相同，也就是要求每个数字都相同 所以方案数就是范围内的数字个数 不过题目可能会出现x>y的情况 要记得特判

4.蓝桥竞技

其实是一道贪心题 考场上没想出来只用了模拟 洛谷测只过了20%

假设sum为所有选手人数

max_num为最多人数的选手位置

1.每名战队必须有五名队员组成 所有队员又必须恰好分配完 可得知sum%5==0

2.假设现在战队全部分配完 那么就是sum/5个战队(选手人数/一个战队的人数)

如果现在max_num>sum/5，也就是说最多人数的选手位置中必定有人去不了任何一个战队(因为每个战队中都已经有这个位置的选手了)那么一定输出'F'而当max_num<=sum/5，也就是说最多人数的选手位置也能依次塞近每个战队，不会出现重复，所以不会出现问题

当同时满足sum%5==0且max_num<=sum/5时就输出‘T’反之输出‘F’

5.LQ聚合

考场上冥冥之中感觉像是贪心 但不知道怎么证明 无奈只好dfs暴搜

我们需要最优的改变？来获取最大值

可以发现

一个 L 能产生贡献，取决于它后面有多少个 Q

一个 Q 能产生贡献，取决于它前面有多少个 L

所以我们可以很明显的看出我们希望左边的L越多越好 右边的Q越多越好 但是我们怎么找这个分界点呢？

这时候就需要遍历找分界点，先遍历一次统计尚未遇到的Q和？将其值存下 初始化L为0；

然后我们该怎么找到最优解呢？
我们从左向右扫描 遇到L时贡献不变L++ 遇到Q时贡献+L,Q--;

关键是遇到？怎么办

有两种情况 一种是选择变L，另一种是选择变Q。该怎么判断应该选择哪个呢？

如果变成L，那么未来最多能贡献当前？后的？和Q的数量的值

如果变成R，那么目前能贡献L值

只需要比较两者的大小即可知道该选择哪一个

为什么这样一定是正确的呢？因为一个位置的贡献只可能来自于左边(作为Q)或者右边(作为L) 不会同时影响到两边 继续遍历下去的决策也不会影响到当前的决策 所以局部最优=全局最优

代码可去上方链接对应题目找题解

6.应急布线

很容易看出来是并查集板子(赛后诸葛亮)

只需要掌握并查集即可做出

比赛的时候没想到并查集，傻傻的数身上一条跳线都没有的电脑，殊不知身上有跳线的电脑跟其他电脑形成一个块，这个块和其他块也是有可能没有跳线的

78理想温度和足球训练

碍于实力问题 理想温度连题解都读不懂(这真是普及/提高−难度???)考场上的作者只会傻傻的模拟建议大家自行去题目链接阅读题解 足球训练作者也是只会dfs暴搜/(ㄒoㄒ)/~~

关于多少分能拿省三省二省一问题

今年难度略低于去年 但是估计分数也不会差太多 作者是弱省 去年只拿了10分就上省二了 今年估计弱省17左右省二吧 30左右省一 省三五分估计就有 强省的话自行相应的添加5分即可

4.27号更新

省赛成绩出来了，作者拿了省一，排名大概是省一中下吧，洛谷估分大概是29分左右，所以弱省省一分数线大约为25分，强省30分左右应该。