蓝桥杯 杨辉三角形【第十二届】【省赛】【C组】H题
题目链接:“蓝桥杯”练习系统
题面:
唠嗑:今天重新打一遍这题,我发现对比去年的自己解题思路上面没有丝毫进步,又被打击了,果然生活很甜应该多吃点苦,去年怎么打今年怎么打,只会跑暴力,只会枚举整个杨辉三角,于是只得了惨惨的30分,自闭
n的最大情况1e9,如果没有推错应该在第1000000001层的第二个,然后杨辉三角的第i层有i个数,枚举就是sum(i * i)(1 - 1000000001)贴t
然后学习一个比较巧妙的方法
我们看杨辉三角的左半边,然后斜线看
可以发现第一斜行是C(0, 0),第二斜行是C(2,1),第i行是C(2 * i, i)
我们可以快速的计算出C(32,16) < 1e9,C(34, 17) > 1e9,那么最大的就在第16斜行,然后从第16斜行遍历到第0斜行,去二分查找n的位置,因为第i斜行的第一个数是C(2 * i, i),第二个是C(2 * i + 1, i),第l个就是C(2 * i + l - 1, i)
二分的右区间是max(n, 2 * i)这个对于输入1的时候至关重要
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
int main(){
int n;
while(~scanf("%d", &n)){
bool f = 0;
for(int i = 16; i >= 0; i--){
int l = i * 2;
int r = max(n, l);
while(l <= r){
ll mid = (l + r) / 2;
ll ans = 1;
for(int x = mid, y = 1; y <= i; y++, x--){
ans *= x;
ans /= y;
if(ans > n){
r = mid - 1;
break;
}
}
if(ans < n){
l = mid + 1;
}else if(ans == n){
printf("%lld\n", mid *(mid + 1) / 2 + i + 1);
f = 1;
break;
}
}
if(f){
break;
}
}
}
return 0;
}