【2021年省赛B组】试题H: 杨辉三角形

题解

🚀️ 通过观察，杨辉三角形显示是对称的，所以如果$n$在右边出现了，那也必然在左边出现过。而数列构造顺序是从左到右，所以我们只需看左半部分即可。

🎉️ 上图并不是我们喜欢的杨辉三角形式，让我们再进一步转换：

😄 通过以上形式，我们可以用两个数组维护上一状态和这一状态的数，然后在快速判断这个数第一次是否只出现在$n$行的第二个数即可。

👍 我们进一步考虑最高循环次数，我们通过观察不难发现，如果某一行的第二个数是$n$， 那么第三个数绝对是$n (n - 1) / 2$， 因此，当$n = 50000$的时候，第三个数的绝对值是$(50000 \times 50000) / 2 = 1250000000 > 10亿$，第三个数都大于十亿了， 杨辉三角形除了第二个数外其他都是递增的，说明小于10亿的前面都已经算了，以后除了每行的第二个数，都不需要计算了。

提交代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
void solve()
{
	int n; cin >> n;
	if(n == 1) 
	{
		cout << 1 << "\n";
		return;
	}
	vector<int> a(N + 1);
	a[0] =  1;
	for(int i = 3; i < N; i++)
	{
		for(int j = i / 2; j > 0; j--)
		{
			if(j == i / 2 && i & 1)
			{
				a[j] = a[j - 1] * 2;
			}
			else a[j] += a[j - 1];
			
			if(a[j] == n)
			{
				cout << i * (i - 1) / 2 + j + 1 << "\n";
				return;
			}
		}
	}
	
	cout << n * (n + 1) / 2 + 2 << "\n";
}
signed main()
{
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1; 
	while(t--) solve();
	return 0;
}