第十二届蓝桥杯省赛 C++ B组 - 杨辉三角形

问题描述

下面的图形是著名的杨辉三角形： 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, … 给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？ 输入格式 输入一个整数 N。 输出格式 输出一个整数代表答案。 数据范围 对于 20% 的评测用例，1≤N≤10； 对于所有评测用例，1≤N≤109 输入样例： 6 输出样例： 13

思路

这道题如果想要得满分，需要一点小技巧，详细步骤： （1）我们先把杨辉三角形平均分成两半，因为在右半边的内容一定也会出现在左半边，所以我们只用看左半边，然后找规律即可。 （2）通过上图可以发现每个斜行从右上到左下都是递增的，并且每行从左到右也是递增的。故每个斜行的第一个元素一定是该元素出现的第一个位置，只要从最下面的那个斜行开始枚举，就能找到目标元素。 （3）那么我们接下来要找到前多少个斜行能够包含到最大值 109，通过计算 C1734 要大于 109，并且 C1632 要小于 109 。所以我们只用从第 16 斜行开始往下枚举即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;

//求组合数
LL C(LL a, int b)
{
          
   
	LL res = 1;
	for (int i = a, j = 1; j <= b; i--, j++)
	{
          
   
		res = res * i / j;
		if (res > n)	return res;
	}
	return res;
}

bool check(int k)
{
          
   
	//下限是2*k，上限最差是n，当k=1时，C(n,1)=n
	LL l = 2 * k, r = max(n, l);
	while (l < r)
	{
          
   
		LL mid = l + r >> 1;
		if (C(mid, k) >= n)	r = mid;
		else l = mid + 1;
	}
	if (C(r, k) != n)	return false;
	//下标为r的位置前面有r+1行（等差公式得r*(r+1)/2）
	cout << (LL)r * (r + 1) / 2 + k + 1 << endl;
	return true;
}

int main()
{
          
   
	cin >> n;
	//从最大的斜行往前枚举
	for (int k = 16;; k--)
		if (check(k))
			break;
	return 0;
}