蓝桥杯2021年第十二届真题第一场-杨辉三角形

题目

题目链接

题解

思维。

杨辉三角对称，所以我们只看左半边（含中间列）。

将全部的1忽略掉，中间列具有特点， C 2 1 C_2^1 C21​、 C 4 2 C_4^2 C42​、 C 6 3 C_6^3 C63​、……、 C 2 x x C_{2x}^x C2xx​；

每个中间列的元素都可以视为一条斜线的一端，如上图的黄线，写线上的元素也具有特点，自右上角至左下角 C 2 x x C_{2x}^x C2xx​、 C 2 x + 1 x C_{2x+1}^x C2x+1x​、……、 C 2 x + i x C_{2x+i}^x C2x+ix​，且这些数是满足单调递增的。

如果一个数字能出现在靠下的黄线中，那么它出现的一定是最早的，也就是说如果一个数出现在多条黄线中，那么最靠下的一条黄线中的该数对应的位置一定是最小的。（证明不会，但是直观上去理解还是可以明白的）

从 x x x大的斜行开始枚举，对于每个斜行，我们去判断输入的数是否在该斜线中，如果在，我们需要知道该数在这条斜线的位置，即自右上往左下数第几个，知道位置就可以，也知道当前枚举到的是第几条斜线，就可以直接算出其前面的数的个数了（本质上我们知道的并不是“自右上往左下数第几个”，而是其他信息，但是都可以求出最终答案，之所以这样说，是先让你有个整体思路而已）

如果再一个个去枚举每条斜线上的元素，时间复杂度就太大了，因为每条斜线都具有单调递增的特性（ C 2 x + i x < C 2 x + i + 1 x C_{2x+i}^x < C_{2x+i+1}^x C2x+ix​ 1; if (C (mid, x) >= n) r = mid; else l = mid + 1; } if (C (l, x) == n) { cout