蓝桥杯刷题第十四天

第二题:不同子串

题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如,字符串aaab 有非空子串 a, b, aa, ab, aaa, aab, aaab,一共 7 个。注意在计算时,只算本质不同的串的个数。
请问,字符串 0100110001010001 有多少个不同的非空子串?
运行限制
最大运行时间:1s
最大运行内存: 256M

字符串问题应该考虑到的函数:substr, find,字符串拼接+

找子串,就是substr,每个子串放进set,去重

#include<iostream>
#include<set>
using namespace std;

int main(){
  string str = "0100110001010001";

  set<string> hash;
  int n = str.size();
  for(int i = 0; i < n; i++){
    for(int j = 1; j + i <= n; j++){
      string t = str.substr(i, j);
      hash.insert(t);
    }
  }

  cout<<hash.size()<<endl;
  return 0;
}

第三题:等差数列

题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。
现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项?
输入描述
输入的第一行包含一个整数 N
第二行包含 N 个整数 A 1 ,A 2 ,⋅⋅⋅,A N 。(注意 A 1 A N 并不一定是按等差数列中的顺序给出)
其中,2≤N≤10 5 ,0≤A i ≤10 9
输出描述
输出一个整数表示答案。
输入输出样例
样例说明: 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
运行限制
最大运行时间:1s
最大运行内存: 256M
输入
5
2 6 4 10 20
输出
10

找到数列各项差值的最大公约数,即是要的等差数列的d

如果最大数和最小数相等,即数列d = 0

否则就可以用公式来求

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
int n, a[N];

int gcd(int a, int b){
  return b ? gcd(b, a % b) : a;
}

int main(){
  scanf("%d", &n);

  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

  sort(a + 1, a + 1 + n);
  int t = a[2] - a[1];
  for(int i = 3; i <= n; i++)
    t = gcd(t, a[i] - a[i-1]);
  
  if(a[n] == a[1]) cout<<n<<endl;
  else
    cout<<(a[n] - a[1]) / t + 1 <<endl;

  return 0;
}

第四题:波动数列

题目描述
观察这个数列:
1 3 0 2 −1 1 −2 ⋯
这个数列中后一项总是比前一项增加 2 或者减少 3。
栋栋对这种数列很好奇,他想知道长度为 n, 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢?
输入描述
输入的第一行包含四个整数 n,s,a,b,含义如前面说述。
其中,1≤n≤1000,−109 s≤109 ,1≤a,b≤106
输出描述
输出一行,包含一个整数,表示满足条件的方案数。由于这个数很大,请输出方案数除以 108 +7的余数。
输入输出样例
输入
4 10 2 3
输出
2

动态规划,需要很多数学思考

可以取负数,因此在判断的时候,需要取该值的正整数,(a%b+b)%b

接下来就是背包问题

#include<iostream>
using namespace std;

const int N = 1010, M = 1e9 + 10, mod = 1e8 + 7;
int n, s, a, b;
int f[N][N];

int get_mod(int a, int b){
  return (a % b + b) % b;
}

int main(){
  scanf("%d%d%d%d", &n, &s, &a, &b);

  f[0][0] = 1;
  for(int i = 1; i < n; i++)
    for(int j = 0; j < n ; j++)
      f[i][j] = (f[i-1][get_mod(j - a*(n-i), n)] + f[i-1][get_mod(j + b*(n-i), n)]) % mod;

  cout<<f[n-1][get_mod(s, n)]<<endl;
  return 0;
}

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

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

相关文章

STL库中list的迭代器实现痛点分析

前文本篇文章准备换个模式&#xff0c;之前都是先详解模拟实现&#xff0c;但是模拟实现的基本逻辑大多数老铁都是明白的&#xff0c;所以我们这次主要讲解STL库中list的独特性&#xff0c;也就是模拟实现中的重难点文末有模拟实现的源码一&#xff0c;list实现的特殊类list实现…

【pytorch】使用deepsort算法进行目标跟踪,原理+pytorch实现

目录deepsort流程一、匈牙利算法二、卡尔曼滤波车速预测例子动态模型的概念卡尔曼滤波在deepsort中的动态模型三、预测值及测量值的含义deepsort在pytorch中的运行deepsort流程 DeepSORT是一种常用的目标跟踪算法&#xff0c;它结合了深度学习和传统的目标跟踪方法。DeepSORT的…

WireShark如何抓包,各种协议(HTTP、ARP、ICMP)的过滤或分析,用WireShark实现TCP三次握手和四次挥手

WireShark一、开启WireShark的大门二、如何抓包 搜索关键字2.1 协议过滤2.2 IP过滤2.3 过滤端口2.4 过滤MAC地址2.5 过滤包长度2.6 HTTP模式过滤三、ARP协议分析四、WireShark之ICMP协议五、TCP三次握手与四次挥手5.1 TCP三次握手实验5.2 可视化看TCP三次握手5.3 TCP四次挥手5.…

PCL 使用ICP点云拼接

一、简介 ICP算法详解——我见过最清晰的解释_负壹的博客-CSDN博客 两个点集&#xff0c;source和target&#xff0c;target不变&#xff0c;source经过旋转&#xff08;Rotation&#xff09;和平移&#xff08;Translation&#xff09;甚至加上尺度&#xff08;Scale&#x…

大聪明教你学Java | 深入浅出聊 SpringBoot 中的 starter 机制

前言 &#x1f34a;作者简介&#xff1a; 不肯过江东丶&#xff0c;一个来自二线城市的程序员&#xff0c;致力于用“猥琐”办法解决繁琐问题&#xff0c;让复杂的问题变得通俗易懂。 &#x1f34a;支持作者&#xff1a; 点赞&#x1f44d;、关注&#x1f496;、留言&#x1f4…

网络安全横向移动指南

在网络安全方面&#xff0c;了解威胁参与者的工具、技术和思维过程非常重要。 一旦对手获得对网络的初始访问权限&#xff0c;横向移动允许他们通过破坏目标组织网络中的其他主机来扩展访问权限并保持持久性。 威胁行为者可以收集有关公司用户活动和凭据、重要数据位置的信息…

Spark - 继承 FileOutputFormat 实现向 HDFS 地址追加文件

目录 一.引言 二.源码浅析 1.RDD.saveAsTextFile 2.TextOutputFormat 3.FileOutputFormat 三.源码修改 1.修改文件生成逻辑 - getRecordWriter 2.允许目录存在 - checkoutputSpecs 3.全部代码 - TextOutputFormatV2 四.追加存储代码实战 五.总结 一.引言 Output d…

关于STM32用DMA传输UART空闲中断中接收的数据时无法接收数据问题以及解决办法

一、stm32 cube ide 配置 1、DMA串口接收数据的ide配置如下图所示 串口1相关的设置及printf函数的使用&#xff0c;这里没放&#xff0c;建议先实现串口打印功能 2、相关的知识点 普通模式和循环模式的区别在于&#xff0c;普通模式下&#xff0c;DMA只会接收一次数据&#x…

微前端(无界)

前言&#xff1a;微前端已经是一个非常成熟的领域了&#xff0c;但开发者不管采用哪个现有方案&#xff0c;在适配成本、样式隔离、运行性能、页面白屏、子应用通信、子应用保活、多应用激活、vite 框架支持、应用共享等用户核心诉求都或存在问题&#xff0c;或无法提供支持。本…

DS18B20温度传感器简介和1-Wire驱动程序

目录DS18B20简介DS18B20的两种供电方式64位ROM温度传感器1-Wire Bus简介DS18B20通信时序初始化ROM相关命令(后续包含任何数据交换的操作)功能相关命令(后续包含任何数据交换的操作)单个DS18B20读取温度值驱动多个DS18B20读取温度值驱动DS18B20简介 DS18B20数字温度计提供9位到…

学习系统编程No.7【进程替换】

引言&#xff1a; 北京时间&#xff1a;2023/3/21/7:17&#xff0c;这篇博客本来昨天晚上就能开始写的&#xff0c;但是由于笔试强训的原因&#xff0c;导致时间用在了做题上&#xff0c;通过快2个小时的垂死挣扎&#xff0c;我充分意识到了自己做题能力的缺陷和运用新知识的缺…

致远OA敏感信息泄露漏洞合集(含批量检测POC)

文章目录前言敏感信息泄露A6 status.jsp 信息泄露漏洞漏洞描述漏洞影响网络测绘漏洞复现POC 批量检测getSessionList.jsp Session泄漏漏洞漏洞描述网络测绘批量检测POC致远OA 帆软组件 ReportServer 目录遍历漏洞漏洞描述漏洞影响网络测绘POC(批量检测)A6 createMysql.jsp 数据…

Java stream性能比较

环境 Ubuntu 22.04IntelliJ IDEA 2022.1.3JDK 17CPU&#xff1a;8核 ➜ ~ cat /proc/cpuinfo | egrep -ie physical id|cpu cores physical id : 0 cpu cores : 1 physical id : 2 cpu cores : 1 physical id : 4 cpu cores : 1 physical id : 6 cpu cores : 1 physical id …

浏览器工作原理

一、JavaScript 的历史 JavaScript&#xff08;简称JS&#xff09;Web前端开发的脚本语言。 它诞生1995年&#xff0c;由网景公司的 Brendan Eich 开发。最初&#xff0c;JavaScript 被设计用于在网页上嵌入动态内容和交互式功能。 1996年&#xff0c;JavaScript 1.1 成为国…

C++虚函数与多态

C虚函数与多态虚函数抽象类纯虚函数虚析构函数多态虚函数的几个问题纯虚函数和ADT虚函数 virtual修饰的成员函数就是虚函数&#xff0c; 1.虚函数对类的内存影响&#xff1a;增加一个指针类型大小&#xff08;32位和64位&#xff09; 2.无论有多少个虚函数&#xff0c;只增加一…

【ansible】模块介绍超详解(下)

目录 六&#xff0c;软件包管理 1&#xff0c;yum_repository模块 &#xff08;1&#xff09;yum_repository模块常用选项 &#xff08;2&#xff09;yum_repository模块案例 2&#xff0c;mount模块 &#xff08;1&#xff09;mount模块选项 &#xff08;2&#xff09;mount模…

大数据简介

大数据概论和职业规划Linux服务器系统Hadoop概论HDFS分布式文件系统Hive数据仓库SparSQL指令Zepplin框架Sqoop框架Superset数据可视化大数据数仓实战-didi出行大数据概念大数据特点大数据应用场景大数据分析业务步骤大数据职业规划大数据学习路线。大数据概念数据&#xff1a;世…

基于YOLOv5的舰船检测与识别系统(Python+清新界面+数据集)

摘要&#xff1a;基于YOLOv5的舰船检测与识别系统用于识别包括渔船、游轮等多种海上船只类型&#xff0c;检测船舰目标并进行识别计数&#xff0c;以提供海洋船只的自动化监测和管理。本文详细介绍船舰类型识别系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实…

【系统开发】WebSocket + SpringBoot + Vue 搭建简易网页聊天室

文章目录一、数据库搭建二、后端搭建2.1 引入关键依赖2.2 WebSocket配置类2.3 配置跨域2.4 发送消息的控制类三、前端搭建3.1 自定义文件websocket.js3.2 main.js中全局引入websocket3.3 App.vue中声明websocket对象3.4 聊天室界面.vue3.5 最终效果一、数据库搭建 很简单的一个…

数据结构与算法——二叉树+带你实现表达式树(附源码)

&#x1f4d6;作者介绍&#xff1a;22级树莓人&#xff08;计算机专业&#xff09;&#xff0c;热爱编程&#xff1c;目前在c&#xff0b;&#xff0b;阶段&#xff0c;因为最近参加新星计划算法赛道(白佬)&#xff0c;所以加快了脚步&#xff0c;果然急迫感会增加动力>——…
最新文章