蓝桥杯练习系统(算法训练)ALGO-980 斐波那契串
资源限制
内存限制:256.0MB C/C++时间限制:10.0s Java时间限制:30.0s Python时间限制:50.0s
问题描述
斐波那契串由下列规则生成:
F[0] = "0";
F[1] = "1";
F[n] = F[n-1] + F[n-2] (n≥2,+表示连接)
给出一个由0和1构成的串S和一个数n,求出F[n]中S出现的次数。
输入格式
第一行一个数n。
第二行一个01串S。
输出格式
答案。
样例输入
96
10110101101101
样例输出
7540113804746346428
数据规模和约定
n≤263-1,子串长≤10000,答案≤263-1。
暴力,特别暴力的方法,显然是不行的,但是为了方便理解:(n<=30还是可以的,但这里n很大)
#include<iostream>
#include<string>
using namespace std;
int main(){long long int n;string s1="0",s2="1",s3,s;scanf("%d",&n);cin>>s;for(int i=2;i<=n;i++){s3=s1+s2;s1=s2;s2=s3;}//求个数long long int cnt=0;for(int j=0;j<s3.length();j++){if(s3.substr(j,s.length())==s){cnt++;}} printf("%lld\n",cnt);return 0;
}
以下是100分的代码:
#include<iostream>
#include<string>
using namespace std;
int flag;
long long int L1,L2,L;//成斐波那契数列的答案,L1为第一个不为0的个数,L2为第2个不为0的个数
long long int x;//第一个不为0的位置
int main(){long long int n;string s1="0",s2="1",s3,s;scanf("%lld",&n);cin>>s;for(int i=2;i<=n;i++){s3=s1+s2;s1=s2;s2=s3;for(int j=0;j<s3.length();j++){if(s3.substr(j,s.length())==s){flag=1;break;}} if(flag==1){x=i; break; }}for(int j=0;j<s3.length();j++){if(s3.substr(j,s.length())==s){L1++;}} s3=s1+s2;s1=s2;s2=s3;for(int j=0;j<s3.length();j++){if(s3.substr(j,s.length())==s){L2++;}}for(int i=x+2;i<=n;i++){L=L1+L2+1;//规律L1=L2;L2=L; }printf("%lld\n",L);return 0;
}
思路:s串的个数成类似于斐波那契数列的规律。
虽然前面提到的暴力方法不能求解n很大的情况,但是前25个绝对没问题,根据暴力方法输出前25个来找规律:
假设串s="10110101101101"
#include<iostream>
#include<string>
using namespace std;
int main(){string s1="0",s2="1",s3,s;int n;scanf("%d",&n);cin>>s;for(int i=2;i<=n;i++){s3=s1+s2;//求个数int cnt=0;for(int j=0;j<s3.length();j++){if(s3.substr(j,s.length())==s){cnt++;}} printf("n=%d:%d个\n",i,cnt);s1=s2;s2=s3;}return 0;
}

可以发现,从含有串s个数不为0的F[n]之后,如F[7],F[8]之后,有以下规律:
因此只需找到第一个含s串的位置x,求出个数L1,然后求出位置x+1的个数L2,之后根据规律即可求出所有。
//但是这个规律好像也不大对,当s=“01”时:

第三个数是前两个数的和,不需要+1了。。这个方法还是不太严谨,虽然它通过了吧。希望可以给你带来一些思路,如果有更好的方法欢迎在评论区留言或私信我。
相关文章:
蓝桥杯练习系统(算法训练)ALGO-980 斐波那契串
资源限制 内存限制:256.0MB C/C时间限制:10.0s Java时间限制:30.0s Python时间限制:50.0s 问题描述 斐波那契串由下列规则生成: F[0] "0"; F[1] "1"; F[n] F[n-1] F[n-2]…...
AHU 数据库 实验五
【实验名称】 实验5 数据库的数据更新与视图管理 【实验目的】 1. 熟悉数据更新操作的概念与操作类型; 2. 熟练掌握INSERT、UPDATE、DELETE语句的基本语法; 3. 熟练运用INSERT、UPDATE、DELETE语句实现数据的插入、修改与删除…...
信号和槽1
信号和槽 Qt信号的三个要素。 信号源:由哪个控件发出的信号。 信号的类型:用户进行不同的操作,就可能触发不同的信号。 信号的处理方式:槽(slot) 差不多等于函数 Qt中可以使用connect这样的函数,把一个信号和一个…...
一个简单的微信小程序表单提交样式模板
没什么东西,只是方便自己直接复制使用 .wxml <view class"box"><form bindsubmit"formSubmit"><view class"form-item"><text class"head">姓名:</text><input class"…...
SpringController返回值和异常自动包装
今天遇到一个需求,在不改动原系统代码的情况下。将Controller的返回值和异常包装到一个统一的返回对象中去。 例如原系统的接口 public String myIp(ApiIgnore HttpServletRequest request);返回的只是一个IP字符串"0:0:0:0:0:0:0:1",目前接口…...
生存预后不显著?最佳阈值来帮你!| 附完整代码 + 注释
大家在进行生存预后分析时发现结果不显著,是不是当头一棒!两眼一黑!难不成这就代表我们的研究没意义吗?NONONO!别慌!说不定还有救!快来看看最佳阈值能不能捞你一把! 对生存分析感兴趣…...
kangle一键安装脚本
Kangle一键脚本,是一款可以一键安装KangleEasypanelMySQLPHP集合的Linux脚本。 脚本本身集成:PHP5.38.2、MYSQL5.68.0,支持极速安装和编译安装2种模式,支持CDN专属安装模式。同时也对Easypanel面板进行了大量优化。 脚本特点 ◎…...
C#写入和调用方法
一、编写方法 在C#中,方法是在类或结构体内部定义的代码块,用于执行特定的操作。方法通常包括以下几个要素: 访问修饰符:指定方法的访问级别,如 public、private、protected 等。返回类型:指定方法返回的…...
Qt的定时器QTimer
定时器Qtimer:用于重复执行或延迟执行函数的类。它可以在一定的时间间隔内发出信号。 使用它,只需要创建一个QTimer类对象,然后调用start()函数开启定时器即可。 定时器的信号 当定时器超时后,就会发出一个timeout的信号函数。 …...
Python 导入Excel三维坐标数据 生成三维曲面地形图(面) 4-4、线条平滑曲面(修改颜色)去除无效点
环境和包: 环境 python:python-3.12.0-amd64包: matplotlib 3.8.2 pandas 2.1.4 openpyxl 3.1.2 scipy 1.12.0 代码: import pandas as pd import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D from scipy.interpolate import griddata fro…...
某小厂java后端初面,记录一下
好吧,,,,,本人很菜,再接再励吧,继续刷。简单记录一下面试题,未亡羊补牢呗。 1.lift join ;inner join ;right join 的区别 2. union 和union all的区别 3.like查询会走索引吗&#x…...
Unity制作马赛克效果
大家好,我是阿赵。 之前在玩怒之铁拳4里面,看到了马赛克场景转换的效果,觉得很有趣,于是也来做一下。 一、2D版本的马赛克转场效果 先看看视频效果: 马赛克转场 这里我是直接写shader实现的,我这里是把…...
【零基础学习04】嵌入式linux驱动中信号量功能基本实现
大家好,为了进一步提升大家对实验的认识程度,每个控制实验将加入详细控制思路与流程,欢迎交流学习。 今天给大家分享一下,linux系统里面信号量操作的具体实现,操作硬件为I.MX6ULL开发板。 第一:信号量基本简介 信号量是同步的一种方式,linux内核也提供了信号量…...
SQL中常见的DDL操作及示例,数据库操作及表操作
目录 一、数据库操作 1、创建数据库 2、查看所有数据库 3、使用数据库 4、删除数据库 二、表操作: 1、创建表 2、查看表结构 3、修改表结构 3.1 添加列 3.2 修改列数据类型 3.3 修改列名 3.4 删除列 3.5 修改表名 3.6 删除表 注意: 在数…...
python 基础练习题
目录 1、定义两个变量,交换两个变量【使用多种方式】 2、给定成绩,判断用户成绩的档次 3. 作业:下列哪一项是“4是奇数或-9为正数”的否定( ) 4. 作业:判断一个整数是奇数还是偶数 5. 求矩形的面积和周…...
前端请求到 SpringMVC 的处理流程
1. 发起请求 客户端通过 HTTP 协议向服务器发起请求。 2. 前端控制器(DispatcherServlet) 这个请求会先到前端控制器 DispatcherServlet,它是整个流程的入口点,负责接收请求并将其分发给相应的处理器。 3. 处理器映射…...
Redis(5.0)
1、什么是Redis Redis是一种开源的、基于内存、支持持久化的高性能Key-Value的NoSQL数据库,它同时也提供了多种数据结构来满足不同场景下的数据存储需求。 2、安装Redis(Linux) 2.1、去官网(http://www.redis.cn/)下…...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的木材表面缺陷检测系统(深度学习+Python代码+UI界面+训练数据集)
摘要:开发高效的木材表面缺陷检测系统对于提升木材加工行业的质量控制和生产效率至关重要。本篇博客详细介绍了如何运用深度学习技术构建一个木材表面缺陷检测系统,并提供了完整的实现代码。该系统采用了强大的YOLOv8算法,并对YOLOv7、YOLOv6…...
Rust 的 into_owned() 方法
into_owned 是 Rust 语言中 std::borrow::Cow 枚举的一个方法。Cow 是一个“克隆在写时”(Copy on Write)的智能指针,它可以包含对数据的引用或数据的实际所有权。这种设计模式在需要避免不必要的数据复制时特别有用,尤其是当数据…...
stimulsoft report for js vue3使用
项目后端使用的java,试验过积木报表(web界面类型的)、JasperReport(.jasper报表文件)、stimulsoft web版本(.mrt报表文件) 我们的项目是前后端分离的,用积木报表(开箱即…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
