[藍(lán)橋杯 2021 省 B] 楊輝三角形

題目描述

下面的圖形是著名的楊輝三角形:

如果我們按從上到下、從左到右的順序把所有數(shù)排成一列，可以得到如下數(shù)列：

$1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,\dots$

給定一個正整數(shù) $N$，請你輸出數(shù)列中第一次出現(xiàn) $N$ 是在第幾個數(shù)。

輸入格式

輸入一個整數(shù) $N$ 。

輸出格式

輸出一個整數(shù)代表答案。

樣例 #1

樣例輸入 #1

6

樣例輸出 #1

13

提示

對于 $20\%$ 的評測用例, $1\le N\le 10$;

對于所有評測用例, $1\le N\le 10^9$ 。

藍(lán)橋杯 2021 第一輪省賽 B 組 H 題。

思路：

1·以斜著看，首先我們可以從中間把這個三角形劈成兩半，因為左右對稱，留左半。左半有了肯定就是最先出現(xiàn)的

2.看圖，第一行得數(shù)都是C(0,N)第二行都是C(1,N)第三行都是C(2,N)以此類推第i行就是C(i,N)，也就是說每一行的數(shù)都可以用組合數(shù)來表示大小，需要有一個求組合數(shù)的函數(shù)：

//求組合數(shù)
long long C(int a, int b)
{long long x = 1, y = 1;for (int i = a, j = b; j >= 1; i--, j--){x = x * i;y = y * j;if (x / y > n){ //如果在這過程中已經(jīng)大于N了就沒必要再繼續(xù)了return x / y;}}return x / y;
}

2.我們知道了這個數(shù)的大小與行和列有關(guān)那這就轉(zhuǎn)變?yōu)樵诘趇行第j列的數(shù)的大小,我們可以發(fā)現(xiàn)這個的每一行的第一個數(shù)的的組合數(shù)下面的那個數(shù)都是從2i開始的，所以我們可以用二分法來找L=2i，R=n；

for (int i = 0; i <=14; i++) // 遍歷行{long long L = 2 * i, // 為什么是2*iR = n, mid;while (L <= R){mid = (L + R) / 2;if (C(mid, i) > n){R = mid - 1;}else if (C(mid, i) < n){L = mid + 1;}else if (C(mid, i) == n){flag = true;break;}}

3這樣我們可以找到這個數(shù)的i，和j然后可以發(fā)現(xiàn)找到一個數(shù)的i和j之后這個數(shù)所在的位置就是
所在行-1可以發(fā)現(xiàn)是一個等差數(shù)列，然后在加上在本行的位置就能得出結(jié)果：公式為(j + 1) * j / 2 + i + 1;

if (flag == true){cout << (mid + 1) * mid / 2 + i + 1;break;}

4.在找得時候我們用二分的方法來找！！節(jié)省時間！！！

---

qwq,博主是個大笨蛋找不到規(guī)律根本Orz

全部代碼：

#include <iostream>
using namespace std;
int 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 = x * i;y = y * j;if (x / y > n){ // 如果在這過程中已經(jīng)大于N了，就沒必要再繼續(xù)了return x / y;}}return x / y;
}
// 一個十分簡單的算組合數(shù)的函數(shù)
int main()
{cin >> n;bool flag = false;for (int i = 0; i <=14; i++) // 遍歷行{long long L = 2 * i, // 為什么是2*iR = n, mid;while (L <= R){mid = (L + R) / 2;if (C(mid, i) > n){R = mid - 1;}else if (C(mid, i) < n){L = mid + 1;}else if (C(mid, i) == n){flag = true;break;}}if (flag == true){cout << (mid + 1) * mid / 2 + i + 1;break;}}system("pause");
}