【蓝桥杯】杨辉三角形【第十二届】【省赛】

您所在的位置：网站首页 › easyconnect深信服安卓 › 【蓝桥杯】杨辉三角形【第十二届】【省赛】

【蓝桥杯】杨辉三角形【第十二届】【省赛】

2024-03-02 18:07| 来源: 网络整理| 查看: 265

在这里插入图片描述

性质

规定1≤j≤i

第i行共i个数；第i行j列的值为C(i-1,j-1)；第i行的最大值是C(i-1,(i-1)/2)第二列是一个d=1的等差数列，所以一定存在N，且一定是最后出现的N。题解1：DP 分析

用dp做不需要C(n,m)的计算，但需要一个数组保存数据，经过优化后可以是一个一维数组。考虑到：第三列也很容易得到递推公式，第i行第三列的值为ai3 =(i-2)(i-1)/2 ,i≥2 。我们可以计算出ai3第一次大于10亿的i=44723 。

for(long i =3L;;++i){ if((i-1)*(i-2)>2000000000L) { System.out.println(i); break; } }

此时，我们只需要对前44722行进行dp计算，即可找到N。考虑到杨辉三角的递增性质，如果找不到，N一定N+1行的第二个数。 dp优化后，我们只需要一个大小至少为44723的一维long数组。

代码实现 import java.util.Scanner; public class Main { static long[] num = new long[44723]; public static void main(String[] args) { Scanner scan = new Scanner(System.in); long N = scan.nextLong(); if(N == 1) { System.out.println(1); return; } num[1] = 1L; //dp计算 for(int i =2;i=1;--j){ num[j] += num[j-1]; if(num[j] == N){ /*这里容易出错! * 因为是下标从大到小的dp,杨辉三角是对称的，先满足的是对称轴右边的数 * 这里结果res的计算需要做一下对称处理，不是i*(i-1)/2 +j * 实际上是第i行的第i-j+1个数首先满足相等条件*/ long res = (((long) i *((long) i -1))>>1)+i-j+1; System.out.println(res); return; } } } //此时，N一定是第N+1行的第二个数 long res = ((N*(N+1))>>1)+2; System.out.println(res); } } 提交结果

在这里插入图片描述

参考链接

蓝桥杯 PREV-284 杨辉三角形【第十二届】【省赛】

题解2 分析

在这里插入图片描述如图，剔除1后，取奇数行的最大值作为每一“列”的首元素。结合杨辉三角的性质，数N如果出现在多“列”中，在较大“列”中N在杨辉三角中的位置靠前。所以我们要从大到小遍历“列”。

static long N; static long C(long n,long m){ long res = 1L; m = Math.min(m,n-m);//C(n,m)= C(n,n-m) for(int i=0;iN)return res; } return res; } 计算组合数函数 N = 1000000000L;//给一个较大值或者注释if(res>N)return res;语句，否则下面的计算组合数将会出错 for(int i =1;;++i){ //第i行的最大值是C(i-1,(i-1)/2) if(C(i-1,(i-1)>>1) > 1000000000) { System.out.println(i); break; } } 计算最大列计算结果是34，在剔除1后，还剩16"列"，其中第16"列"只存在一个合法元素,即杨辉三角中第33行的最大值C(32,16)= 601080390L。一开始做if判断即可不遍历第16"列"，从第15"列"开始，嫌麻烦也可以直接从第16"列"开始遍历。代码实现 import java.util.Scanner; public class Main { /** * 初等数论：任意n个连续整数之积一定是n的倍数 */ static long N; static long C(long n,long m){ long res = 1L; m = Math.min(m,n-m);//C(n,m)= C(n,n-m) for(int i=0;iN)return res; } return res; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); N = scan.nextLong(); if(N == 1) { System.out.println(1); return; } if(N == 601080390L) {//第16"列"只有一个元素 System.out.println(32*33/2 +17); return; } //对剩下的15"列"进行二分查找 //第i"列"的所有数是杨辉三角中每一行n的第i+1个数，其值为C(n+1,i); for(int i =15;i>=1;--i){ //第i"列"的起点位于杨辉三角的第2i+1行，因次左边界l取2i //第一列的值是d=1的等差数列，至少在r=N处，会满足等于N的条件，所以右边界取N long l = i=N)r = mid; else l = mid+1; } if(C(l,i)==N){ //该点是杨辉三角中第l+1行的第i+1个数 long res = ((l*(l+1))>>1)+i+1; System.out.println(res); return; } } } } 提交结果

在这里插入图片描述

参考链接

蓝桥杯2021年第十二届真题第一场-杨辉三角形

补充

在竞赛过程中一般不会去进行额外计算，所以另一种思路是从小"列"到大“列”扫描，大“列”的上确界给一个较大值（本题中大于等于16即可），然后取这些“列”中N位置的最小值，即为所求。参考：第十二届蓝桥杯B组省赛杨辉三角形题解

备注

本文整理的思路都是答题过程中可以想到的，肯定存在更优的解决思路，但不做讨论。

【本文地址】

【蓝桥杯】杨辉三角形【第十二届】【省赛】

【蓝桥杯】杨辉三角形【第十二届】【省赛】

今日新闻

推荐新闻