ABC254B Practical Computing

题目分析

题目要求我们生成一个二维数表，满足每一行的开头和结尾是 $1$，其他位置由上一行的相邻两个数之和决定。这个结构正是 杨辉三角。

---

解题思路

从第 $1$ 行开始逐行构造。每一行的第一个和最后一个元素固定为 $1$，中间位置由上一个数组对应位置的左右两个值相加得到。

---

实现步骤

• 初始化一个二维数组 int a[35][35]；杨辉三角增长速度块，结合数据范围判定是否需要 long long。
• 遍历行数 $i = 1$ 到 $N$；
• 对每一行的列数 $j = 1$ 到 $i$ 执行如下：
  • 若 $j = 1$ 或 $j = i$，则该位置为 $1$；直接赋值 a[i][j] = 1 即可。
  • 否则该位置为上一行 $j-1$ 和 $j$ 的和；即赋值 a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
• 每构造一行，立即输出结果。

---

复杂度分析

• 时间复杂度：$O(N^2)$，因为要生成 $N$ 行，每行最多 $N$ 项；
• 空间复杂度：$O(N^2)$，若使用二维数组存储所有值；

---

总结

• 本题是一道典型的二维递推问题；
• 规律清晰、边界明确，是非常适合练习基本数组构造的题；
• 利用 每行两边为 $1$，中间为上两数之和 的规则逐行生成即可；
• 数据范围小，直接模拟是最优选择。