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

蓝桥杯省赛自测CB 组 - 洛谷 洛谷自测链接(由于数据原因 真实成绩可能与官方成绩有所出入)1.青春常数非常简单的入门题目 一共四年前两年总和要小于后两年 即xy2026202520242023且xy算出x的最大值即可(注意x可以为0 所以最大值还需要1)最后的答案为10131012601210122.双碳战略完全没有思路的一道题 考场上想用dfs暴搜怕电脑炸了 据说答案是7922646703.循环右移也是一道入门的贪心题 题目看起来像数学题 但是仔细一想就知道不管怎么进行循环右移都与原来相同也就是要求每个数字都相同 所以方案数就是范围内的数字个数 不过题目可能会出现xy的情况 要记得特判4.蓝桥竞技其实是一道贪心题 考场上没想出来只用了模拟 洛谷测只过了20%假设sum为所有选手人数max_num为最多人数的选手位置1.每名战队必须有五名队员组成 所有队员又必须恰好分配完 可得知sum%502.假设现在战队全部分配完 那么就是sum/5个战队(选手人数/一个战队的人数)如果现在max_numsum/5也就是说最多人数的选手位置中必定有人去不了任何一个战队(因为每个战队中都已经有这个位置的选手了)那么一定输出F而当max_numsum/5也就是说最多人数的选手位置也能依次塞近每个战队不会出现重复所以不会出现问题当同时满足sum%50且max_numsum/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分左右应该。