蓝桥杯每日一真题——[蓝桥杯 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…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法
用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
