蓝桥杯每日一真题——[蓝桥杯 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…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
