定兴网站建设公司,外包做的网站 需要要源代码吗,手机版网站 html5,网站源码大全 最新PREV-282 杨辉三角形【第十二届】【蓝桥杯省赛】【B组】 #xff08;二分查找 递推#xff09;#xff1a;
解析#xff1a;
1.杨辉三角具有对称性#xff1a; 2.杨辉三角具有一定规律 通过观察发现#xff0c;第一次出现的地方一定在左部靠右的位置#xff0c;所以从…PREV-282 杨辉三角形【第十二届】【蓝桥杯省赛】【B组】 二分查找 递推
解析
1.杨辉三角具有对称性 2.杨辉三角具有一定规律 通过观察发现第一次出现的地方一定在左部靠右的位置所以从后往前进行查找
代码
#include iostream
#include algorithmusing 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;
}
