第I题 杨辉三角形

题目大意：

解法一：（得20%）

思路：

当指考虑小范围的值时，我们可以直接根据杨辉三角形的规律：第i行第j列的值=第i-1行第j列的值+第i-1行第j-11列的值，来把前50个杨辉三角形的数存入数组中，最后通过一个循环来查找就可以得到20%的分数。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10100;
LL dp[N][N];//用来存入杨辉三角形的每一个数
LL sk[N];//记入每个数是第几个数
int s = 1;
int n;
int main() {
    cin >> n;
    dp[0][0] = 1;
    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];//杨辉三角形的规律
            sk[s++] = dp[i][j];
        }
    }
    for (int i = 1; i <= 10000; i++) {
        if (sk[i] == n) {//第一次相等即为该数第一次出现的位置
            cout << i;
            break;
        }
    }
    return 0;
}

解法二：（得全部分）

思路：

 对杨辉三角形进行仔细观察可知道，其中有很多数是重复的，因此我们只需要记录其有效部分。具体规律如下图所示：

还可以发现，对于同一行，列数越大对应的数值也越大。而且某一行的某一列的值为x，在列数不变的情况下，无论行数怎么变大都不会再出现比x小的数；同理再行数不变的情况下列数怎么变大也不会出现比x小的数。并且得知n小于等于10的0次方时，有效列数为0-16列。因此我们可以一列一列的考虑，由于随着行号的变大，数值时单调递增的，其知道了行号、列号对应的数值也就知道了，于是便可以二分行号，使用二分查找的方法来计算本题。

代码如下：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll N;
ll C(int a, int b)//求第i行第j列的值
{
	ll res = 1;
	for (ll i = a, j = 1; j <= b; i--, j++)
	{
		res = res * i / j;
		if (res > N)//如果中间结果超过N就直接返回
			return res;
	}
	return res;
}
int main()
{
	cin >> N;
	for (int k = 16; k >= 0; k--)//一列一列的找
	{
		ll l = 2 * k, r = max(N, l), mid;
		while (l <= r) {//对第k列二分查找行
			mid = l + (r - l) / 2;//二分行
			ll CC = C(mid, k);
			if (CC == N)
				break;
			else if (CC > N)
				r = mid - 1;
			else
				l = mid + 1;
		}
		if (C(mid, k) == N)
		{//第mid行、第k列的数就是N
			cout << (mid + 1) * mid / 2 + k + 1 << endl;
			//杨辉三角形的行数符号公差为1的等差数列，故用等差数列求和公式
			//加上第几列再加上1（因为列从0开始）即可得出该数的位置
			break;
		}
	}
	return 0;
}

大数据201 liyang