佛山家居企业网站建设火车头wordpress 5.1

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

（二分查找 + 递推）：

解析：

1.杨辉三角具有对称性：

        

2.杨辉三角具有一定规律

 

通过观察发现，第一次出现的地方一定在左部靠右的位置，所以从后往前进行查找

代码：

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;
LL n;
LL C(int a, int b)
{LL res = 1;for (int i = 1, j = a; i <= b; i ++, j --){res = res * j / i;if (res > n)return res;}return res;
}//检查第k斜行
bool check(int k)
{LL l = 2 * k, r = max(n, l);while (l < r){LL mid = (l + r) / 2;if (C(mid, k) >= n) r = mid;else l = mid + 1;} if (C(l, k) != n) return false;else{//k是行数LL res = (l + 1) * l / 2 + k + 1;printf("%lld\n", res);return true;}
}
int main()
{cin >> n;for (int i = 16;; i --)if (check(i))break;return 0;
}

---