📝 题目大意

有 $N$ 种元素，第 $i$ 种元素有 $i$ 个，编号为 $A_{i,1} \sim A_{i,i}$。两个元素 $i$ 和 $j$ 合成时，若 $i \ge j$ 则结果为 $A_{i,j}$，否则结果为 $A_{j,i}$（即合成规则对称）。从元素 $1$ 开始，依次与元素 $1, 2, \dots, N$ 合成，输出最终得到的元素编号。

💡 解题思路

1. 题目分析：$N \le 100$，数据范围很小，直接模拟即可。合成规则的关键在于对称性：无论 $i$ 和 $j$ 的大小关系如何，合成结果只取决于 $(i,j)$ 这一对编号，且总是取较大索引作为行、较小索引作为列去查 $A$。

2. 算法推导：

   • 定义 $a[i][j]$ 表示元素 $i$ 与元素 $j$ 合成的结果（其中 $i \ge j$）。
   • 输入时只给出 $i \ge j$ 的情况（即三角矩阵），std.cpp 在读取时同时赋值 a[j][i] = a[i][j]，将矩阵补全为对称矩阵，这样后续查询时不用关心下标大小。
   • 设当前元素为 ans，初始为 $1$（因为从元素 $1$ 开始）。
   • 依次遍历 $i = 1 \to N$，每次将当前元素 ans 与元素 $i$ 合成：ans = a[ans][i]。由于矩阵已对称，无论 ans 与 $i$ 谁大谁小，a[ans][i] 都能正确返回合成结果。
   • 最终 ans 即为答案。

3. 边界与细节：

   • 注意输入格式为三角形，第 $i$ 行有 $i$ 个数，读取时用双重循环 j=1 到 i。
   • 矩阵下标从 $1$ 开始，建议数组开 $N+5$ 大小避免越界。
   • 合成序列中第一个元素既是 $1$ 也是 $1$ 号元素与自身的合成，即 ans = a[1][1]，这自然包含在循环中。

⏱️ 复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N \le 100$，输入读取为 $O(N^2)$，模拟过程为 $O(N)$。
• 空间复杂度：$O(N^2)$，用于存储对称矩阵 $a$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N];  // 对称矩阵，a[i][j] 表示元素 i 与 j 合成的结果

int main() {
    int n;
    scanf("%d", &n);
    // 读入三角矩阵并补全为对称矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            scanf("%d", &a[i][j]);
            a[j][i] = a[i][j];  // 利用对称性补全，使 a[x][y] 在任意 x,y 下都合法
        }

    int ans = 1;  // 初始元素为 1
    // 依次与元素 1, 2, ..., n 合成
    for (int i = 1; i <= n; i++)
        ans = a[ans][i];  // 当前元素与元素 i 合成

    printf("%d\n", ans);
    return 0;
}