蓝桥杯2021届C++B组省赛真题 杨辉三角形

1. 首先他要我们找第一次出现N的位置，我们可以发现杨辉三角是两边完全对称的，在右边出现的在左边一定先出现过，所以N只可能出现在左半边，我们将右半边删去

2. 这道题的数据规模特别大，那么我们是不是到某一行就可以停止搜索？

根据上图我们可以发现，在对称线上的数都有一个规律，他们都等于

由 = 可得，，所以我们可以用计算器算一下， 

，所以我们只需要在0~16行内搜索即可

3. 由杨辉三角的一个性质：

我们发现，在杨辉三角上的每一个数都满足：N = （i是行号，j是列号)；例：第0行第0列=，第3行第1列=

第i行第j列对应着一维数组的是：

所以我们的目的就变成了找 i , j

由上图我们还可以发现：

因为每一斜行都是单调递增的关系，所以可以用二分搜索可以节约大量时间

二分搜索行区间：

left = 2*i（这里的i对应着横着看的第i行），right = INF 

#include
#include
using namespace std;
const long long INF = 1e9;
long long 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 *= i;
		y *= j;
		if(x/y > N){//如果在这过程中已经大于N了，就没必要再继续了
			return x/y;
		}
	}
	return x/y;
}
int main(){
	cin >> N;
	bool flag = false;
	for(int i = 16;i >= 0;i--){//只需遍历0~16行即可 
		long long l = 2*i,r = INF,mid;
		while(l <= r){
			mid = (l+r)/2;
			long long k = C(mid,i);
			if(k == N){
				flag = true;
				break;
			}else if(k < N){
				l = mid + 1;
			}else{
				r = mid - 1;
			}
		}
		if(flag){//找到N，打印并跳出循环
			cout << (mid+1)*mid/2 + i + 1;
			break;
		}
	}
	return 0;
}