第十二届蓝桥杯省赛CC++ 研究生组

十二届省赛题

第十二届蓝桥杯省赛C&C++ 研究生组-卡片
第十二届蓝桥杯省赛C&C++ 研究生组-直线
第十二届蓝桥杯省赛C&C++ 研究生组-货物摆放
第十二届蓝桥杯省赛C&C++ 研究生组-路径
第十二届蓝桥杯省赛C&C++ 研究生组-时间显示
第十二届蓝桥杯省赛C&C++ 研究生组-砝码称重
第十二届蓝桥杯省赛C&C++ 研究生组-异或数列
第十二届蓝桥杯省赛C&C++ 研究生组-双向排序

三年小小结

水过了最新三年的题目,小小复盘一下~

简单模拟

  1. 卡片(填空):从1开始计算每位所用卡片,当某个数字的卡片不足时,则找到能拼到的最大数。注意最后的这个数是拼不出来的第一个数,所以答案记得减一。作为填空题,枚举即可解决,该题目进一步思考的话,一定是卡片1消耗量最大,可转化为1出现2021次的数字

  2. 直线(填空):判断给定范围内的点能组成多少条不同直线,表面考算法,其实是考数学公式~注意分母不为0,直接把平行于y轴的单算即可,记得后续加上。
    在这里插入图片描述

  3. 时间显示:常见的时间处理类问题,小小注意下小时是24小时制。需要显示的时间是时(0-23)分(0-59)秒(0-59),给的输入是从00-00-00开始的毫秒数,则该先除的先除该求余的求余。给的年份就是迷惑性信息了,木用,忽略即可。

  4. 裁纸刀(填空):先裁四下去掉边缘,再把行分开(行数-1),再把列分开((列数-1)*行数)。甚至都没啥小坑,温柔

  5. 灭鼠先锋(填空):手动可以直接模拟~ 再优化一点点的话,对于一行空内容的话,谁先手谁必输,问题等价于谁后把第一行填满,谁就一定能保证自己赢。问题分解的思想很有效,简单分割也许就能大幅简化问题

  6. 与或异或(填空):电路图看起来挺唬人的,但枚举就能解决的纸🐅。本质上就是按照a[i][j] = a[i-1][j] op a[i-1][j+1],其中op可选&、^、|其一,统计结果为1的组合个数。

  7. 翻转:翻转规则为出现010或101就可以把中间的值翻转,借助翻转的情况下是否能把两个串变相同,如果是输出最小翻转次数。虽然题设中有“翻转操作可无限重复”,但其实一次翻转即可,翻完了其实也就不能出现不同了,属于干扰信息。以s串1010101为例,翻转第一次1000101,翻转第二次1000111,搞定。

excel

  1. 工作时长(填空):本质上要求的是两个时间段之差的和。用excel先排序;再选择时间格式[h]:mm:ss,注意小时的选择,以处理超出24小时的情况;计算两个时间段的差,关于求出整列的上下行间的时间差,先手算两个单元格,后续直接下拉即可自动计算;求和

数学问题

质因数

很稳定,每年都考了一个,或直接或加了点马甲

  1. 货物摆放(填空):整数分解问题。n较大直接暴力枚举不可行,考虑当时质因数模块学过整数范围内一定能用十个质因数表示,类推n的约数也不会太多,转化为先求出n的约数(别漏了1和n),再计算相乘为n的组合个数
  2. 质因数个数:给出整数n的质因数个数
sqr = sqrt(1.0*n);
num = 0;
for(int i = 2; i <= sqr; i++){if(n % i == 0){num++;while(n % i == 0) n /= i;}
}
if(n > 1) num++;//别漏了最后这个顽固分子~
  1. 公因数匹配:找到首次出现或同时出现但最短的区间,满足头尾元素有大于1的公因数。直接暴力的话两层的105超时,有了之前的经验,也考虑下先分解看看。分解每个数的所有质因数,如果没出现过,则记录首次出现的位置;如果已经出现过,判断是否需要更新最左位置。判断该数满足的区间是否早于或短于已有的区间,若是则更新。
#include<stdio.h>
#include<math.h>
const int maxn = 1e6 + 10;
int p[maxn] = {0};
int main(){int n, x, l, ansL, ansR = 0, sqr;scanf("%d", &n);ansL = n + 1;for(int i = 1; i <= n; i++){l = n + 1;scanf("%d", &x);sqr = sqrt(1.0 * x);for(int j = 2; j <= sqr; j++){if(x % j == 0){if(!p[j]) p[j] = i;else if(p[j] < l) l = p[j];while(x % j == 0) x /= j;}}if(x > 1){if(!p[x]) p[x] = i;else if(p[x] < l) l = p[x];}if(l < ansL || (ansL == l && ansR > i)){ansL = l;ansR = i;}}printf("%d %d", ansL, ansR);return 0;
} 

说都说了,顺带复习下最小公约数&最大公倍数

int gcd(int a, int b){//辗转相除法求最大公约数,时间复杂度O(logn) if(!b) return a;return gcd(b, a % b);
}最小公倍数为a * b / gcd(a, b) 
  1. 数的拆分:给出整数n,将其拆分为x2* y3(大于2和偶数次幂可以转化为底数先升幂再把幂次调到2,奇数次幂同理,例如x4=x2的平方,y5=y2的平方 *y)的形式则可拆分返回yes,否则返回no。n最大为10e18,开五次方大约是4000,则我们对4000以内的质数打表,分解后的约数就不会太大了。判断是否能够融入我们要求的模式,即能否转化为平方或立方,能则该数可以拆分,否则是个单蹦不能拆分。

进制转换

  1. 异或数列:十进制转二进制。各方初始值为0,给定数列,选数异或,每个数只能选用一次。显然,谁先抢到最高位的“唯一”(1个或奇数的单蹦1)一个1则必胜。问题转化为寻找:
    • 最高位的唯一的一个1
    • 最高位的偶数个1
      • 总的零的数量为偶数个,先手拿到单蹦1则必胜
      • 总的零的数量为奇数个,后手拿到单蹦1则必胜

否则为平局
2.

阶乘特点

  1. 阶乘的和:直接算的话肯定超时,而且仔细想来只是求最大的m,并不需要真的算出和,只是能进行比较即可,算出来也是多余工作。回到问题本身阶乘m!,我们有多个ai!,对于多个阶乘有(m+1)m! = (m+1)!,我们对ai进行排序,顺带统计每个数的出现次数,要有序且有映射关系考虑用map;自底到高统计每位是否能进位,第一个不能进位前的数就是我们要找的m

求余

  1. GCD:考查辗转相除法和求余的简化。思维更简单的解法,观察知最大公约数是abs(a-b),从1开始依次枚举即可,能骗些分数。进一步思考的话,回到问题本身,
    • 找使得gcd(a+k,b+k)最大的k,根据辗转相除算法知,gcd(a+k,b+k)=gcd(b+k,b-a)
    • gcd(b+k,b-a) = b-a(假设已经处理好,能保证b >= a)
    • 转化为找到满足(b+k)%(b-a) == 0的最小值
    • 记g = b- a,则(b+k)%g = (b % g + k % g) % g == 0
      b % g <g, k % g < g,则g - b % g = k
      在这里插入图片描述
#include<iostream>
#include<algorithm>
using namespace std;
int main(){long long a, b, g;scanf("%lld%lld", &a, &b);if(a > b) swap(a, b);g = b - a;printf("%lld", g - b % g);return 0;
} 

观察规律

  1. 全排列的价值:观察给出的样例知,对于1~n, 前后两两价值相加的和都相等,为(n-1)*n/2;那再看可以组数,也就是排列数n!/2(除2是因为两两一组相加才为定值)
    在这里插入图片描述

动态规划

  1. 砝码称重:很经典的一个问题。我们能称出来的最大重量是所有砝码重量之和,最小的可能重量是1,其中题设告诉我们砝码总重范围也是一种暗示了。
    利用dp的话,我们依次计算有1~n个砝码能称出来的重量,首先前i个砝码能称出来的重量,也一定能用前i+1个砝码称出来。对于前i个砝码的判断,之前称不出来的重量m,考虑
    • 第i个砝码重量w[i] == m
    • 已经可以称出来m + w[i]
    • 已经可以称出来abs(m - w[i])
      • m > w[i],能称出来m-w[i],则再加个w[i]
      • w[i] < m,能称出来w[i]-m,则在对面来个w[i]

最后统计用n个砝码所能称出的重量个数即可

int dp[N][maxn] = {0};
count = 0;
for(int i = 1; i <= n; i++){for(int j = 1; j <= sum; j++){dp[i - 1][j] = 1;if(!dp[i][j]){if(w[i] == j || a[i - 1][j + w[i]] || a[i - 1][abs(j - w[i])]) dp[i][j] = 1;}}
}for(int i = 1; i <= sum; i++)count += dp[n][i];

莫队算法

  1. 重复的数:很直给的一个莫队情况,大致思想是首先只适用于可离线的情况,对元素进行分块,对查询区间排序(同块则按照右边界排序,不同块按照块号排序);处理查询

m叉树

  1. 子树的大小:
    • 对于m叉树的第i个结点,第一个结点号为(i - 1) * m + 2
    • 满m叉树时,第i个结点的最右孩子为i*m + 1(这个1是根节点)
    • 总结点数为n的完全m叉树,最后一个分支节点的最右孩子为n

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型

石油炼化5G智能制造工厂数字孪生可视化平台&#xff0c;推进行业数字化转型。在石油炼化行业&#xff0c;5G智能制造工厂数字孪生可视化平台的出现&#xff0c;为行业的数字化转型注入了新的活力。石油炼化行业作为传统工业的重要领域&#xff0c;面临着资源紧张、环境压力、安…

Matlab 双目相机标定(内置函数)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 相机标定的目的就是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数(即相机的内参与外参)。具体过程如下所述: 1、首先我们需要获取一个已知图形的图像(这里我们使用MATLAB所提供的数据)。 2、找到同…

_nodemon自动重启服务器

文章目录 1.安装模块 nodemon1.1安装方式2.jason文件里面可以存储自定义指令 由于每次修改代码都要重启服务器&#xff0c;所以我们希望有一种方式自动监视代码修改&#xff0c;自动启动服务器nodemon模块解决了这个问题 1.安装模块 nodemon 1.1安装方式 全局安装 npm i node…

计算地球圆盘负荷产生的位移

1.研究背景 计算受表面载荷影响的弹性体变形问题有着悠久的历史&#xff0c;涉及到许多著名的数学家和物理学家&#xff08;Boussinesq 1885&#xff1b;Lamb 1901&#xff1b;Love 1911&#xff0c;1929&#xff1b;Shida 1912&#xff1b;Terazawa 1916&#xff1b;Munk &…

TCP | TCP协议格式 | 三次握手

1.TCP协议 为什么需要 TCP 协议 &#xff1f;TCP 工作在哪一层&#xff1f; IP网络层是不可靠的&#xff0c;TCP工作在传输层&#xff0c;保证数据传输的可靠性。 TCP全称为 “传输控制协议&#xff08;Transmission Control Protocol”&#xff09;。 TCP 是面向连接的、可靠…

京东云开发者:DDD 学习与感悟 —— 向屎山冲锋

原文地址:https://mp.weixin.qq.com/s/Hvq1ttBopbxypatVcKcLiA 软件系统是通过软件开发来解决某一个业务领域或问题单元而产生的一个交付物。而通过软件设计可以帮助我们开发出更加健壮的软件系统。因此&#xff0c;软件设计是从业务领域到软件开发之间的桥梁。而DDD是软件设计…

opengl 学习(六)-----坐标系统与摄像机

坐标系统与摄像机 分类引言坐标系统摄像机教程在CMake中使用全局定义预编译宏,来控制是否开启错误检查补充 分类 opengl c 引言 OpenGL希望在每次顶点着色器运行后&#xff0c;我们可见的所有顶点都为标准化设备坐标(Normalized Device Coordinate, NDC)。也就是说&#xff…

OCP NVME SSD规范解读-14.Firmware固件升级要求

4.11节 Firmware Update Requirements 描述了数据中心NVMe SSD固件更新的具体要求&#xff0c;确保固件升级过程既安全又可靠&#xff0c;同时充分考虑了设备在升级过程中的可用性和功能性。 FWUP-1: 设备必须记录每一次固件激活过程。这意味着固件升级过程中&#xff0c;设备会…

【Dynamics 365 FO】在Dynamics 365中建立一个SSRS报表

建立一个SSRS报表主要有以下8个步骤&#xff1a; 目录 1、新建合约类 合约类&#xff08;Contract Class&#xff09;的作用是获取查询数据源所需要的数据&#xff0c;在我们点开报表的时候&#xff0c;系统会弹出一个对话框让我们来选择字段来筛选要查询数据&#xff0c;合…

基于Java的厦门旅游电子商务预订系统(Vue.js+SpringBoot)

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 景点类型模块2.2 景点档案模块2.3 酒店管理模块2.4 美食管理模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 学生表3.2.2 学生表3.2.3 学生表3.2.4 学生表 四、系统展示五、核心代码5.1 新增景点类型5.2 查询推荐的…

CANoe自带的TCP/IP协议中TCP发送时的一个特殊处理(我一定是第一个发现的)

我们知道,CANoe软件中配置以太网通道后,添加的仿真节点可以作为一个主机或者一个应用来实现以太网通信。但不管是作为主机还是应用,仿真节点都需要配置TCP/IP协议栈。 有了TCP/IP协议栈,设置了网卡信息后(IP地址、MAC地址等),仿真节点就可以通过编写CAPL代码的方式发送和…

关于UDP协议

UDP协议是基于非连接的发送数据就是把数据包简单封装一下&#xff0c;然后从网卡发出去就可以&#xff0c;数据包之间没有状态上的联系&#xff0c;UDP处理方式简单&#xff0c;所以性能损耗非常少&#xff0c;对于CPU、内存资源的占用远小于TCP&#xff0c;但是对于网络传输过…

[综述笔记]A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis

论文网址&#xff1a;Frontiers | A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis (frontiersin.org) 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论…

visual studio卸载几种方法

1、控制面板卸载&#xff1b; 2、有时候会发现控制面板卸载会失败&#xff0c;无法卸载&#xff0c;这时候要先把下面目录的关于visual studio的都删除&#xff0c;然后重启电脑后&#xff0c;重新安装vs即可。

java Flink(四十三)Flink Interval Join源码解析以及简单实例

背景 之前我们在一片文章里简单介绍过Flink的多流合并算子 java Flink&#xff08;三十六&#xff09;Flink多流合并算子UNION、CONNECT、CoGroup、Join 今天我们通过Flink 1.14的源码对Flink的Interval Join进行深入的理解。 Interval Join不是两个窗口做关联&#xff0c;…

全流程ArcGIS Pro技术应用

GIS是利用电子计算机及其外部设备&#xff0c;采集、存储、分析和描述整个或部分地球表面与空间信息系统。简单地讲&#xff0c;它是在一定的地域内&#xff0c;将地理空间信息和 一些与该地域地理信息相关的属性信息结合起来&#xff0c;达到对地理和属性信息的综合管理。GIS的…

HQYJ 2024-3-19 作业

TCP通信三次握手和四次挥手&#xff1a; 并行和并发的区别&#xff1a;并发是单核处理器处理多个线程任务&#xff0c;并行是多核处理器同时处理多个线程任务。并发过程中会抢占CPU资源&#xff0c;轮流使用&#xff1b;并行过程不会抢占CPU资源。 阻塞IO和非阻塞IO&#xff…

【系统架构师】-计算机网络

1、网络的划分 网络性能指标&#xff1a;速率、带宽(频带宽度或传送线路速率)、吞吐量、时延、往返时间、利用率。 网络非性能指标&#xff1a;费用、质量、标准化、可靠性、可扩展性、可升级性、易管理性和可维护性。 总线型(利用率低、干扰大、价格低)、 星型(交换机转发形…

Python PyQt5

实现界面开发&#xff0c;与tkinter功能一致&#xff0c;网上已有详细资料&#xff0c;此处仅记录自己的代码&#xff1a; 文章目录 1. 实操1.1 main.py1.2. 窗体模块代码1.3. 页面效果 2. 参考资料2.1. PyQt5 参考资料2.2. tkinter 参考资料 3. 安装注意事项3.1. 下载3.2 Pyc…

解决jenkins运行磁盘满的问题

参考&#xff1a;https://blog.csdn.net/ouyang_peng/article/details/79225993 分配磁盘空间相关操作&#xff1a; https://cloud.tencent.com/developer/article/2230624 登录jenkins相对应的服务或容器中查看磁盘情况&#xff1a; df -h在102挂载服务器上看到是这两个文件…