[洛谷 P8749][蓝桥杯 2021省 B] Yang Hui Trigonometry Problem Solving (Dynamic Programming + Combinatorial Math + Rolling Arrays)
最编程
2024-04-01 22:53:14
...
[蓝桥杯 2021 省 B] 杨辉三角形
题目描述
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
给定一个正整数 ,请你输出数列中第一次出现 是在第几个数。
输入格式
输入一个整数 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
6
样例输出 #1
13
提示
对于 的评测用例, ;
对于所有评测用例, 。
蓝桥杯 2021 第一轮省赛 B 组 H 题。
思路
首先,从输入中读取一个整数n。如果n等于1,直接输出1并结束程序。
然后,进入一个最大迭代次数为1e5的循环,每次循环的索引为i。在每次循环中,首先计算一个变量t,它等于i模2的结果,用于实现动态规划数组的滚动更新。
接下来,初始化动态规划二维数组dp的当前行的第一个元素为1。然后,进入一个最大迭代次数为i的循环,每次循环的索引为j。在这个循环中,更新dp数组的当前行的第j个元素,它等于上一行的第j-1个元素和第j个元素之和,这就是杨辉三角形的特性。
如果计算出的组合数大于10的9次方,就跳出内部循环,因为题目中给出的n的最大值是10的9次方。
如果n等于dp数组的当前行的第j个元素,那么就找到了n在杨辉三角形中的位置。此时,计算出n的位置,使用的是等差数列求和的公式。然后,输出结果并结束程序。
如果在所有的循环中都没有找到n,那么最后,再次使用等差数列求和的公式,计算出n的位置,然后输出结果。
注意
- 在计算位置时,要将乘法结果强制转换为 long long 类型,否则无法通过部分测试点。
- 动态规划的
j
是从1开始的,会把数字的判断漏掉。数字第一次在数列中出现的位置一定是1。如果n等于1,直接输出1并结束程序。if (n == 1) { cout << 1 << "\n"; return 0; }
AC代码
#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
int n;
ll dp[2][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
if (n == 1) {
cout << 1 << "\n";
return 0;
}
for (int i = 1; i <= 1e5; i++) {
int t = i & 1;
dp[t][0] = 1;
for (int j = 1; j <= i; j++) {
// 求组合数
dp[t][j] = dp[t ^ 1][j - 1] + dp[t ^ 1][j];
if (dp[t][j] > 1e9) {
break;
}
if (n == dp[t][j]) {
// 等差数列求和
cout << ((1ll * i * (i - 1) / 2) + j + 1) << "\n";
return 0;
}
}
}
// 等差数列求和
cout << (1ll * n * (n + 1) / 2 + 2) << "\n";
return 0;
}
上一篇: 算法 TS 递归和迭代
下一篇: vim c++ google style