2025蓝桥杯省赛C/C++研究生组游记

前言

至少半年没写算法题了,手生了不少,由于python写太多导致行末老是忘记打分号,printf老是忘记写f,for和if的括号也老是忘写,差点连&&和||都忘记了。

题目都是回忆版本,可能有不准确的地方。

代码如果有机会能拿到的话,会补充的。

A

统计1~202504之间每个数字各数位上的数之和被5整除的个数。

直接循环统计就完事了。

B

统计所有IPv6地址的最短形式的长度之和。

缩写规则为,每个四位十六进制数的前导零可以省略,除此之外可以省掉一串连续的0000。

注意,当省略的0000序列在序列两端时,会变成::

例如0234:0000:0000:0000:000f:1f1f:00ab:0000,可以缩写为

234::f:1f1f:ab:0,长度就是3+2+1+1+4+1+2+1+1=16

但0000:0000:0000:000f:1f1f:00ab:0234:0000,应该缩写为

::f:1f1f:ab:234:0,长度就是2+1+1+4+1+2+1+3+1+1=17

题解

这题很有意思,陷阱很多。(复盘的时候发现自己错了)

首先显然一个非0的四位十六进制数去除前导零的长度总和为sumlen=(15*1+15*16*2+15*16*16*3+15*16*16*16*4)

一个非0的四位十六进制数有sumcnt=(15+15*16+15*16*16+15*16*16*16)种

两个四位十六进制数长度总和需要求卷积,而不是直接相加或者相乘。

当然也可以一个一个数计算贡献,也就是sumlen*[sumcnt^(n-1)]*n种(可证明和卷积是等价的)

然后就是最短形式,如果有多串长度相同的连续的0地址,应该优先省去中间的0串。

枚举最长的0串区间求解的话,会有很多问题,例如去重、合法串的限制。

所以枚举八个四位十六进制数分别为0的所有组合,时间复杂度为2^8

然后根据枚举的情况来求应该省去的0串的位置,计算所有0地址提供冒号和0的长度。

最后计算非0地址贡献的长度总和sum,然后用sumcnt^(非0地址个数)*(所有0地址提供的冒号和0的长度)计算所有0地址的贡献,最后加起来就可以了。

写完之后就9:40多了。

C

一个序列ai长度为n,m次操作,一次操作把序列中每个数变成ai*bitcount(ai),求m次操作后的序列。

n<=1000,m<=5,ai<=1000。

直接模拟即可。

D

最大数字

输入n,将1~n的每个数字转换为二进制,拼接成一个长二进制串,再转换回十进制,要求最终的十进制数最大。

n<=10000

题解

把每个数字的二进制放入结构体,重载小于符号为

a拼接b > b拼接a

(可恶,我连这个都忘记了,直接按字典序排了,太久不做题导致的)

然后排完序之后用原数据值进行高精度计算(用二进制串直接计算会超时),最后用longlong压8位,勉强能在1秒内出结果。

(我这个SB题还写了一个小时,我真是服了)

E

冷热数据队列

q1队列长度为n1,q2队列长度为n2,访问一个数据x

四条规则

若x不在q1、q2中,则将x加入q2头部

若x在q2或q2中,则将x提到q1头部

若q1或q2超过各自的长度限制时,剔除尾端的数据

若q1超过限制但q2还有空位时,则将q1尾部数据放到q2头部。

题解(非正解)

考场上直接用deque模拟了,两个队列各自维护一个vis数组,快速判断哪些数据在队列中

但第二条规则需要把deque里面的倒出来在压回去

不过根据数据范围来看,应该直接暴力就有80分。

正解?我也不知道

F

01串(又是01串)

把0、1、2、3、……所有数的二进制表示排成一排,求前x个数有多少个1

序列的大致形式就是0;1;1、0;1、1;1、0、0;1、0、1;……

x<=10^18

题解

倍增查询恰好超过x时,一个数的二进制有多少位,记n为该值减一

设f[i]表示二进制位数小于等于i的所有数的累积,f[i]=f[i-1]*2+2^(i-1),

可以先将f[n]添加入答案,减掉x用掉的位数。

接下来就确定了x所在的数的二进制位数。

用x的剩余位数除以n,对得到的二进制进行分治:(类似二分查找)

只需要在选择右子树的时候统计答案,并只需要添加左子树的累和即可。

最后算完之后,我们已经确定了x最终位于的十进制数,如果x还有剩余,则可以从高位到低位以此枚举最终的十进制数的二进制,加入答案即可。

G

甘蔗

给出n个甘蔗高度ai,m个限制bj。

当每个甘蔗与相邻甘蔗高度差都在集合b中,则序列合法。

求最少砍多少个甘蔗才能让序列合法。

题解(非正解)

考场上直接暴力dp了

f[i][j]表示第i棵甘蔗高度为j时,前i棵甘蔗的序列合法的最少代价。

当j==a[i]时,则f[i][j]=min(f[i-1][j±b[k]])(1<=k<=m,0<=j±b[k]<=a[i-1])

当j!=a[i]时,在上式子后+1即可。

O(n^2*m)的复杂度,没法过完所有数据,可能有优化之类的吧。

H

n个厂房,所有厂房都在x正方向,坐标为ci,原料单价为ai,库存为bi,原料需求为m个单位,每走一个单位的代价为o。

求满足原料需求的最少代价。

n<=100000,保证ci递增

题解(个人猜测)

前面耽误时间太多了,再加上手比较生了,写到最后一题只剩20分钟了,最后直接没交。

模拟费用流贪心。

维护两个集合S(空流边)、T(已流边),按照原料单价排序

依次加入工厂,加入到S集合中,按照费用排序。

若当前m个单位有剩余,则在S集合中选择费用最低的工厂<cost,cap>,流过min(m,cap),总代价ans+=cost*min(m,cap)

在T集合中添加工厂<-cost,min(m,cap)>,或者在已有的-cost元素上添加min(m,cap)的容量

若cap已空,则在S集合中删除该工厂。

完成上述更新之后,还需要维护S、T的流量平衡。

若当前S集合首元素cost与T集合首元素cost之和为负数,则说明代价还可以减少(也就是更换工厂后会更优),则需要将min(cap_S_begin,cap_T_begin)的货物从T换到S集合中,与此同时还需要更新S和T集合。

完成所有更新之后,取所有(总代价+ci)的最小值就是最终的代价。

后记

感觉考得好差,太多失误了,而且最近赶毕设鸭梨山大,生活状态也不好,希望一切能好起来吧。

这次CDF三道二进制,ABCDF都是数位相关问题,题目比重真的很奇怪。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/67.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

巧用递归算法:破解编程难题的“秘密武器”

专栏&#xff1a;算法的魔法世界 个人主页&#xff1a;手握风云 目录 一、递归 二、例题讲解 2.1. 汉诺塔问题 2.2. 合并两个有序链表 2.3. 反转链表 2.4. 两两交换链表中的节点 2.5. Pow(x, n) 三、总结 一、递归 递归的概念 一个方法在执行过程中调用自身, 就称为递…

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 一、斐波那契数 相关题目&#xff1a;Leetcode509 文档讲解&#xff1a;Leetcode509 视频讲解&#xff1a;Leetcode509 1. Leetcode509. 斐波那契数 斐波那契数 &#xff08;通常…

CAD导入arcgis中保持面积不变的方法

1、加载CAD数据&#xff0c;选择面数据&#xff0c;如下&#xff1a; 2、加载进来后&#xff0c;右键导出数据&#xff0c;导出成面shp数据&#xff0c;如下&#xff1a; 3、选择存储路径&#xff0c;导出面后计算面积&#xff0c;如下&#xff1a; 4、与CAD中的闭合线面积核对…

备赛蓝桥杯-Python-考前突击

额&#xff0c;&#xff0c;离蓝桥杯开赛还有十个小时&#xff0c;最近因为考研复习节奏的问题&#xff0c;把蓝桥杯的优先级后置了&#xff0c;突然才想起来还有一个蓝桥杯呢。。 到目前为止python基本语法熟练了&#xff0c;再补充一些常用函数供明天考前再背背&#xff0c;算…

Matlab 汽车ABS的bangbang控制和模糊PID控制

1、内容简介 Matlab 197-汽车ABS的bangbang控制和模糊PID控制 可以交流、咨询、答疑 2、内容说明 略 摘要&#xff1a;本文旨在设计一种利用模糊控制理论优化的pid控制器&#xff0c;控制abs系统&#xff0c;达到对滑移率最佳控制范围的要求 &#xff0c;所提出的方案采用级联…

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模(C/C++/Java组)

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模&#xff08;C/C/Java组&#xff09; 时间限制: 3s 内存限制: 512MB 提交: 6633 解决: 1263 题目描述 给定 n, m &#xff0c;问是否存在两个不同的数 x, y 使得 1 ≤ x < y ≤ m 且 n mod x n mod y 。 输入格式 输入包含多…

蓝桥杯C/C++省赛/国赛注意事项及运行环境配置

大佬的蓝桥杯考前急救指南 对拍&#xff08;手动生成测试数据&#xff09;代码&#xff1a; #include <bits/stdc.h> // 包含所有标准库的头文件 using namespace std; // 使用标准命名空间int main() {srand(time(0)); // 设置随机数种子为当前时间&#xff0c;确保每次…

13、nRF52xx蓝牙学习(GPIOTE组件方式的任务配置)

下面再来探讨下驱动库如何实现任务的配置&#xff0c;驱动库的实现步骤应该和寄存器方式对应&#xff0c;关 键点就是如何调用驱动库的函数。 本例里同样的对比寄存器方式编写两路的 GPOITE 任务输出&#xff0c;一路配置为输出翻转&#xff0c;一路设 置为输出低电平。和 …

使用Apache POI(Java)创建docx文档和表格

1、引入poi 依赖组件 <dependency><groupId>org.apache.poi</groupId><artifactId>poi-scratchpad</artifactId><version>4.0.0</version> </dependency> <dependency><groupId>org.apache.poi</groupId>&…

利用 RNN 预测股票价格:从数据处理到可视化实战

在金融领域&#xff0c;预测股票价格走势一直是众多投资者和研究者关注的焦点。今天&#xff0c;我们将利用深度学习中的循环神经网络&#xff08;RNN&#xff09;来构建一个简单的股票价格预测模型&#xff0c;并详细介绍从数据加载、预处理、模型搭建、训练到最终结果可视化的…

华为RH2288H V3服务器极速重装:从RedHat到openEuler 24超详细重装指南

1 登录iBMC口 2 配置启动项 点击&#xff1a;配置&#xff0c;点击&#xff1a;系统启动项 点击&#xff1a;单次有效&#xff0c;选择&#xff1a;光驱&#xff0c;点击&#xff1a;保存 3 进Remote Contro 点击&#xff1a;远程控制&#xff0c;进入如下界面 点击&#xff1…

+++++背到厌倦。持续更新

Spring IoC 的工作流程: 读取 BeanDefinition: Spring 容器启动时&#xff0c;会读取 Bean 的配置信息 (例如 XML 配置文件、注解或 Java 代码)&#xff0c;并将这些配置信息转换为 BeanDefinition 对象。创建 Bean 实例: 根据 BeanDefinition 中的信息&#xff0c;Spring 容器…