Acwing-3418 杨辉三角形

关于杨辉三角形的一些规律(更详细地去看参考):

下面这些图都来自其他人所做图片

因为杨辉三角形是对称的,并且与二项式有关:

左半部分(左半部分的编号肯定比右半部分小,不考虑右半部分)一个斜行,一个斜行地去看,会发现同一斜行中,越往左下,数越大,同一行中,越往右数越大。所以从最里面的斜行往外找,比如要找20第一次出现在第3斜行的开头,位置在第6行(都从第0算起)),则其他斜行中要出现20,那编号一定比第3斜行的编号大。

而对称轴,即每个斜行开头(右上角)的数字的规律是:比如第K斜行,则为C_{2k}^{k}

而每个斜行末尾的数字规律是:比如第k斜行,则为C_{n}^{k},为什么会有出现n呢?因为第n行的第1个(从第0开始算)数字必定是n,且该数在第n行为最后一次出现。并且第k斜行中,每个数都是所在行的第k个位置。

题目: 

我的代码: 

关于组合函数为何这样写,看这里:排列函数与组合函数-CSDN博客

#include <iostream>
#include <vector>
using namespace std;
long long n;
long long CC(int a, int b)
{			//组合数公式 a为C的下标,b为C的上标:C=a!/((a-b)!*b!)
	long long  result = 1;
	for (int i = a, j = 1; j <= b; i--, j++)
	{
		result = result * i / j;
		if (result > n)	return result;	//当该组合数还没有算完就发现已经大于n,则在往下算已经没有意义。直接跳出
	}
	return result;
}
bool check(int k)
{
	//利用二分查找,去找等于n的数
	long long L = k * 2;		//每个斜行的下届(开头)是2k,
	long long R = n;			//每个斜行的上界(末尾)是n,也就是第n行,因为第n行的第2个数必定会出现n
	if (L > R)	return false;	//因为n肯定会在第n行出现且最后一次出现,而第k斜行的开头数所在的行数为2k,
							//如果斜行开头数所在行数比第n行还大,则肯定无法在该第2k行找到等于n的数
	while (L < R)      //这里的条件得是<,等循环结束时,R=L,在后续的if语句判断相不相等
	{
		long long mid = L + R >> 1;		//将L+R的数右移1位,相当于(L+R)/2;
		if (CC(mid, k) >= n)	R = mid;   //如果在mid中点找到,则R会一直为该次的mid位置,只剩下L在移动
		else L = mid + 1;
	}
	if (CC(R, k) != n)	return false;		//等二分结束发现不等于,则返回0

	cout << R * (R + 1) / 2 + k + 1 << endl;	//第R行前面有R行,数字之和为等差数列(1+2+3+...),在第R行中,第k位置数字是改行从0开始算,所以k+1
	return true;

}
int main()
{

	cin >> n;
	for (int k = 16; ; k--)
	{
		if (check(k))			//如果找到后则跳出for循环
			break;
	}
	return 0;
}

二分查找的另一种写法:

bool check(int k)
{
	//利用二分查找,去找等于n的数
	long long L = k * 2;		//每个斜行的下届(开头)是2k,
	long long R = n;			//每个斜行的上界(末尾)是n,也就是第n行,因为第n行的第2个数必定会出现n
	if (L > R)	return false;	//因为n肯定会在第n行出现且最后一次出现,而第k斜行的开头数所在的行数为2k,
	//如果斜行开头数所在行数比第n行还大,则肯定无法在该第2k行找到等于n的数
	while (L <= R)		//这里的条件得是<=,因为最后一次循环时,R=L。要去看该位置是否为要找的。
	{
		long long mid = L + R >> 1;		//将L+R的数右移1位,相当于(L+R)/2;
		if (CC(mid, k) == n)
		{
			cout << mid * (mid + 1) / 2 + k + 1 << endl;	//第mid行前面有R行,数字之和为等差数列(1+2+3+...),在第mid行中,第k位置数字是改行从0开始算,所以k+1
			return true;
		}
		if (CC(mid, k) > n)	R = mid-1;			
		else L = mid + 1;
	}
	return false;		//等二分结束发现不等于,则返回0

}

 参考:

【算法竞赛】杨辉三角 | 杨辉三角与组合数的关系 | 杨辉三角的算法应用 | c++代码实现公式获取杨辉三角位置的值_利用杨辉三角计算组合数-CSDN博客

 AcWing 3418. 杨辉三角形 - AcWing

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

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

相关文章

如何区分相对路径 与 绝对路径?

在网页中有很多需要使用我们URL路径的场景&#xff0c;包括a标签的href、link标签的href、script标签的src、imag标签的src、form中的action、ajax请求的url等等等等。它们都可以使用相对路径和绝对路径来引入文件&#xff0c;那么&#xff0c;我们如何区分相对路径与绝对路径呢…

MATLAB | 绘图复刻(十六) | 弦图2.1.0版本更新——弦末端弧形块颜色单独设置

Hey, 本人自主开发的弦图绘制工具迎来2.1.0版本了&#xff1a;起因是有粉丝问我前两天发布的文章中这张图咋画&#xff1a; 我本来一想我开发的工具画弦图还是很简单的哇&#xff08;下面文章中有基本用法&#xff09; https://slandarer.blog.csdn.net/article/details/126458…

Vue tree自定义滚动条位置

贴一张效果图&#xff0c;我的效果不方便贴出来 实现支持&#xff1a; 1、懒加载 2、普通加载 下面贴关键思想&#xff1a; document有一个获取element元素的方法。 let element document.getElementById(tree); let arr document.querySelectorAll(".nodelModel&quo…

编曲知识15:重复段落编写 尾奏编写 家庭工作室搭建 硬件设备使用常识

15 重复段落编写 尾奏编写 家庭工作室搭建 硬件设备使用常识小鹅通-专注内容付费的技术服务商https://app8epdhy0u9502.pc.xiaoe-tech.com/live_pc/l_6602a586e4b0694cc051476b?course_id=course_2XLKtQnQx9GrQHac7OPmHD9tqbv 重复段落设计 第二段落指代间奏过后的段落 第二…

uniapp 小程序发布体验版 http://198.18.0.1:7001 不在以下 request 合法域名列表中(踩坑记录二)

问题一&#xff1a; 小程序发布体验版时出现报错信息&#xff1a; http://198.18.0.1:7001 不在以下 request 合法域名列表中无法连接uniCloud本地调试服务&#xff0c;请检查当前客户端是否与主机在同一局域网下 解决方案&#xff1a; 请务必在HBuilderX内使用【发行】菜单打…

上位机图像处理和嵌入式模块部署(qmacvisual寻找圆和寻找直线)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面有几篇文章&#xff0c;我们谈到过直线拟合、圆拟合和椭圆拟合。当时&#xff0c;我们的做法是&#xff0c;先找到了轮廓&#xff0c;接着找到…

C++多线程:单例模式与共享数据安全(七)

1、单例设计模式 单例设计模式&#xff0c;使用的频率比较高&#xff0c;整个项目中某个特殊的类对象只能创建一个 并且该类只对外暴露一个public方法用来获得这个对象。 单例设计模式又分懒汉式和饿汉式&#xff0c;同时对于懒汉式在多线程并发的情况下存在线程安全问题 饿汉…

稀碎从零算法笔记Day35-LeetCode:字典序的第K小数字

要考虑完结《稀碎从零》系列了哈哈哈 这道题和【LC.42 接雨水】&#xff0c;我愿称之为【笔试界的颜良&文丑】 题型&#xff1a;字典树、前缀获取、数组、树的先序遍历 链接&#xff1a;440. 字典序的第K小数字 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1…

el-upload上传图片图片、el-load默认图片重新上传、el-upload初始化图片、el-upload编辑时回显图片

问题 我用el-upload上传图片&#xff0c;再上一篇文章已经解决了&#xff0c;el-upload上传图片给SpringBoot后端,但是又发现了新的问题&#xff0c;果然bug是一个个的冒出来的。新的问题是el-upload编辑时回显图片的保存。 问题描述&#xff1a;回显图片需要将默认的 file-lis…

从0配置React

在本地安装和配置React项目&#xff0c;您可以使用create-react-app这个官方推荐的脚手架工具。以下是安装React的步骤&#xff0c;包括安装Node.js、使用create-react-app创建React应用&#xff0c;以及启动开发服务器。 下载安装node.js运行以下命令&#xff0c;验证Node.js…

施耐德 Unity Pro PLC 编程软件介绍

Unity Pro 软件基本介绍 Unity Pro 是施耐德中大型 PLC 的编程软件&#xff08;<–> 对应西门子 Step7&#xff09; 支持的 PLC&#xff1a;施耐德中大型 PLC 中型 PLC&#xff1a;Premium、M340&#xff08;<–> 对应西门子 S7-300、S7-1200&#xff09;大型 PL…

精读 Generating Mammography Reports from Multi-view Mammograms with BERT

精读&#xff08;非常推荐&#xff09; Generating Mammography Reports from Multi-view Mammograms with BERT&#xff08;上&#xff09; 这里的作者有个叫 Ilya 的吓坏我了 1. Abstract Writing mammography reports can be errorprone and time-consuming for radiolog…

C++项目——集群聊天服务器项目(十)点对点聊天业务

本节来实现C集群聊天服务器项目中的点对点聊天业务&#xff0c;一起来试试吧 一、点对点聊天业务 聊天服务器中一个重要的功能就是实现点对点聊天&#xff0c;客户端发送的信息包含聊天业务msgid、自身 的id和姓名、聊天对象的id号以及聊天信息&#xff0c;例如&#xff1a; …

uniapp uni.scss中使用@mixin混入,在文件引入@include 样式不生效 Error: Undefined mixin.(踩坑记录一)

问题&#xff1a; 在uni.scss文件定义mixin 2. 在vue文件引入: 3. 出现报错信息: 4. 问题思考&#xff1a; 是不是需要引入uni.scss &#xff1f; 答案不需要 uni.scss是一个特殊文件&#xff0c;在代码中无需 import 这个文件即可在scss代码中使用这里的样式变量。uni-app的…

ubuntu23.10配置RUST开发环境

系统版本: gcc版本 下载rustup安装脚本: curl --proto https --tlsv1.2 https://sh.rustup.rs -sSf | sh下载完成后会自动执行 选择默认安装选项 添加cargo安装目录到环境变量 vim ~/.bashrc 默认已添加 使用环境变量立即生效 source ~/.bashrc 执行rust开发环境,在终端输入…

Vitepress部署到GitHub Pages,工作流

效果&#xff1a; 第一步&#xff1a; 部署 VitePress 站点 | VitePress 执行 npm run docs:build&#xff0c;npm run docs:preview&#xff0c;生成dist文件 第二步&#xff1a; 手动创建.gitignore文件&#xff1a; node_modules .DS_Store dist-ssr cache .cache .temp *…

KMP哈希算法

KMP算法 KMP算法是一种字符串匹配算法&#xff0c;用于匹配模式串P在文本串S中出现的所有位置。 例如S“ababac”,P"aba",那么出现的所有位置是1 3 KMP算法将原本O&#xff08;n^2&#xff09;的字符串匹配算法优化到了O&#xff08;n&#xff09;&#xff0c;其精…

MySQL使用C语言连接

要使用C语言连接mysql&#xff0c;需要使用mysql官网提供的库&#xff0c;大家可以去MySQL官网下载。 1.引入库 1.选择Download Archivs 因为我们要连接的是C语言&#xff0c;所以选择Connector/C。 选择合适的版本下载&#xff0c;我这里 下载完之后&#xff0c;我们使用rz命…

AtCoder Beginner Contest 347 (ABCDEF题)视频讲解

A - Divisible Problem Statement You are given positive integers N N N and K K K, and a sequence of length N N N, A ( A 1 , A 2 , … , A N ) A(A_1,A_2,\ldots,A_N) A(A1​,A2​,…,AN​). Extract all elements of A A A that are multiples of K K K, divi…

鸿蒙HarmonyOS应用开发之HID DDK开发指导

场景介绍 HID DDK&#xff08;HID Driver Develop Kit&#xff09;是为开发者提供的HID设备驱动程序开发套件&#xff0c;支持开发者基于用户态&#xff0c;在应用层开发HID设备驱动。提供了一系列主机侧访问设备的接口&#xff0c;包括创建设备、向设备发送事件、销毁设备。 …