蓝桥杯每日一真题——[蓝桥杯 2021 省 B] 杨辉三角形(二分+规律)
文章目录
- [蓝桥杯 2021 省 B] 杨辉三角形
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 思路:
- 全部代码:
[蓝桥杯 2021 省 B] 杨辉三角形
题目描述
下面的图形是著名的杨辉三角形:

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…
给定一个正整数 NNN,请你输出数列中第一次出现 NNN 是在第几个数。
输入格式
输入一个整数 NNN 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
6
样例输出 #1
13
提示
对于 20%20 \%20% 的评测用例, 1≤N≤101 \leq N \leq 101≤N≤10;
对于所有评测用例, 1≤N≤1091 \leq N \leq 10^91≤N≤109 。
蓝桥杯 2021 第一轮省赛 B 组 H 题。
思路:
1·以斜着看,首先我们可以从中间把这个三角形劈成两半,因为左右对称,留左半。左半有了肯定就是最先出现的

2.看图,第一行得数都是C(0,N)第二行都是C(1,N)第三行都是C(2,N)以此类推第i行就是C(i,N),也就是说每一行的数都可以用组合数来表示大小,需要有一个求组合数的函数:
//求组合数
long long C(int a, int b)
{long long x = 1, y = 1;for (int i = a, j = b; j >= 1; i--, j--){x = x * i;y = y * j;if (x / y > n){ //如果在这过程中已经大于N了就没必要再继续了return x / y;}}return x / y;
}
2.我们知道了这个数的大小与行和列有关那这就转变为在第i行第j列的数的大小,我们可以发现这个的每一行的第一个数的的组合数下面的那个数都是从2i开始的,所以我们可以用二分法来找L=2i,R=n;
for (int i = 0; i <=14; i++) // 遍历行{long long L = 2 * i, // 为什么是2*iR = n, mid;while (L <= R){mid = (L + R) / 2;if (C(mid, i) > n){R = mid - 1;}else if (C(mid, i) < n){L = mid + 1;}else if (C(mid, i) == n){flag = true;break;}}
3这样我们可以找到这个数的i,和j然后可以发现找到一个数的i和j之后这个数所在的位置就是
所在行-1可以发现是一个等差数列,然后在加上在本行的位置就能得出结果:公式为(j + 1) * j / 2 + i + 1;
if (flag == true){cout << (mid + 1) * mid / 2 + i + 1;break;}
4.在找得时候我们用二分的方法来找!!节省时间!!!
qwq,博主是个大笨蛋找不到规律根本Orz
全部代码:
#include <iostream>
using namespace std;
int n;
long long C(int a, int b)
{long long x = 1, y = 1;for (int i = a, j = b; j >= 1; i--, j--){x = x * i;y = y * j;if (x / y > n){ // 如果在这过程中已经大于N了,就没必要再继续了return x / y;}}return x / y;
}
// 一个十分简单的算组合数的函数
int main()
{cin >> n;bool flag = false;for (int i = 0; i <=14; i++) // 遍历行{long long L = 2 * i, // 为什么是2*iR = n, mid;while (L <= R){mid = (L + R) / 2;if (C(mid, i) > n){R = mid - 1;}else if (C(mid, i) < n){L = mid + 1;}else if (C(mid, i) == n){flag = true;break;}}if (flag == true){cout << (mid + 1) * mid / 2 + i + 1;break;}}system("pause");
}相关文章:
蓝桥杯每日一真题——[蓝桥杯 2021 省 B] 杨辉三角形(二分+规律)
文章目录[蓝桥杯 2021 省 B] 杨辉三角形题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路:全部代码:[蓝桥杯 2021 省 B] 杨辉三角形 题目描述 下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列&…...
<C++> 类和对象(下)
1.const成员函数将const修饰的“成员函数”称之为const成员函数,const修饰类成员函数,实际修饰该成员函数隐含的this指针,表明在该成员函数中不能对类的任何成员进行修改。class A { public:void Print() //这里隐藏了A* this指针{cout <…...
基于Springboot+Vue2前后端分离框架的智慧校园系统源码,智慧学校源码+微信小程序+人脸电子班牌
▶ 智慧校园开发环境: 1、使用springboot框架Javavue2 2、数据库MySQL5.7 3、移动端小程序使用小程序原生语音开发 4、电子班牌固件安卓7.1;使用Java Android原生 5、elmentui ,Quartz,jpa,jwt 智慧校园结构导图▶ 这…...
JavaEE-线程安全问题
1.线程安全的概念 如果多线程环境下代码运行的结果是符合我们预期的,即在单线程环境应该的结果,则说这个程序是线 程安全的. 为啥会出现线程安全问题? 本质原因: 线程在系统中的调度是无序的/随机的 (抢占式执行). 2.开始说明 先看个线程不安全的例子…...
【Node.js】身份认证,Cookie和Session的认证机制,express中使用session认证和JWT认证
Node.jsWeb开发模式如何选择Web开发模式身份认证什么是身份认证为什么要身份认证不同开发模式的身份认证Session认证机制提高身份认证的安全性Session的工作原理Express中使用Session认证Session认证机制的局限性JWT认证机制JWT的工作原理JWT的组成部分Express中使用JWT在登录成…...
Redis删除策略和淘汰策略
一、删除策略 删除策略就是针对已过期数据的处理策略。 针对过期数据要进行删除的时候都有哪些删除策略呢? 1.定时删除2.惰性删除3.定期删除1、立即删除 当key设置有过期时间,且过期时间到达时,由定时器任务立即执行对键的删除操作。 优…...
LFM雷达实现及USRP验证【章节2:LFM雷达测距】
目录 1. 参数设计 几个重要的约束关系 仿真参数设计 2. matlab雷达测距代码 完整源码 代码分析 回顾:LFM的基本原理请详见第一章 本章节将介绍LFM雷达测距的原理及实现 1. 参数设计 几个重要的约束关系 带通采样定理: 因此如果我们B80MHz时&a…...
菜鸟刷题Day5
⭐作者:别动我的饭 ⭐专栏:菜鸟刷题 ⭐标语:悟已往之不谏,知来者之可追 一.一维数组的动态和:1480. 一维数组的动态和 - 力扣(LeetCode) 描述 给你一个数组 nums 。数组「动态和」的计算公式…...
已解决AttributeError:module tensorflow no attribute app异常的正确解决方法,亲测有效!!!
已解决AttributeError:module tensorflow no attribute app异常的正确解决方法,亲测有效!!! 文章目录报错问题解决方法福利报错问题 粉丝群里面的一个小伙伴敲代码时发生了报错(当时他心里瞬间凉了一大截&…...
Hadoop集群环境配置搭建
一、简单介绍 Hadoop最早诞生于Cutting于1998年左右开发的一个全文文本搜索引擎 Lucene,这个搜索引擎在2001年成为Apache基金会的一个子项目,也是 ElasticSearch等重要搜索引擎的底层基础。 项目官方:https://hadoop.apache.org/ 二、Linux环…...
Thread类的基本用法
Thread类的基本用法🔎1.线程创建🌻继承Thread类🌼继承Thread重写run()方法🌼继承Thread匿名内部类🌻实现Runnable接口🌼实现Runnable接口重写run()方法🌼实现Runnable接口匿名内部类ἳ…...
YOLOV8改进:如何增加注意力模块?(以CBAM模块为例)
YOLOV8改进:如何增加注意力模块?(以CBAM模块为例)前言YOLOV8nn文件夹modules.pytask.pymodels文件夹总结前言 因为毕设用到了YOLO,鉴于最近V8刚出,因此考虑将注意力机制加入到v8中。 YOLOV8 代码地址&am…...
Spark Streaming DStream的操作
一、DStream的定义 DStream是离散流,Spark Streaming提供的一种高级抽象,代表了一个持续不断的数据流。DStream可以通过输入数据源来创建,比如Kafka、Flume,也可以通过对其他DStream应用高阶函数来创建,比如map、redu…...
蓝桥杯冲刺 - week1
文章目录💬前言🌲day192. 递归实现指数型枚举843. n-皇后问题🌲day2日志统计1209. 带分数🌲day3844. 走迷宫1101. 献给阿尔吉侬的花束🌲day41113. 红与黑🌲day51236. 递增三元组🌲day63491. 完全…...
Leetcode27. 移除元素
目录一、题目描述:二、解决思路和代码1. 解决思路2. 代码一、题目描述: 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用…...
ViewService——一种保证客户端与服务端同步的方法
简介在分布式系统中,最常见的场景就是主备架构。但是如果主机不幸宕机,如何正确的通知客户端当前后端服务器的状况成为一个值得研究的问题。本文描述了一种简单的模型用于解决此问题。背景以一个分布式的Key-Value数据库为背景。数据库对外提供3个接口Ge…...
使用STM32F103ZE开发贪吃蛇游戏
目录 前言 一、设置FreeROTS用户任务 (1)事件event任务 (2)按键输入方向控制任务 (3)果实食物任务 (4)显示任务函数 (3)开始任务 二、主函数 三、ADC采样…...
如何利用Web3D技术打造在线虚拟展览馆
随着Web3D技术的不断发展,越来越多的企业和组织开始将其应用于虚拟展览馆的建设中。虚拟展览馆可以为观众提供高度沉浸式的展览体验,让观众可以随时随地参观各种展览,同时也为展览组织者提供了更多的展示方式和机会。下面将介绍如何利用Web3D…...
第二十三章 opengl之高级OpenGL(实例化)
OpenGL实例化实例化数组绘制小行星带实例化 综合应用。 如果绘制了很多的模型,但是大部分的模型包含同一组顶点数据,只是不同的世界空间变换。 举例:一个全是草的场景,每根草都是一个包含了几个小三角形的模型。需要绘制很多根草…...
C++ String类总结
头文件 #include <string>构造函数 default (1) basic_string();explicit basic_string (const allocator_type& alloc); copy (2) basic_string (const basic_string& str);basic_string (const basic_string& str, const allocator_type& alloc); su…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...
21-Oracle 23 ai-Automatic SQL Plan Management(SPM)
小伙伴们,有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL, 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始,OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...
