识别符号格: 题解¶
思路与贡献¶
标准程序保留出题人的反身性、传递性及逐对检查上确界和下确界的方法。Codex（GPT-6）整理 C++17 实现，用转置矩阵复用上下界检查，并补全符号别名与候选扫描的证明。程序见 std.cpp。出题人的另一种判据见所有上确界加最小元。
不能直接要求符号关系反对称：不同符号可以表示同一元素。首先检查 \(A_{i,i}=1\) ，以及对于所有三元组，若 \(A_{i,j}=A_{j,k}=1\) ，则 \(A_{i,k}=1\) .这是反身性与传递性。
为什么可以不显式合并符号¶
对满足以上两条的关系，定义 \(i\sim j\) 当且仅当 \(A_{i,j}=A_{j,i}=1\) .这是等价关系。传递性保证等价符号对所有其他符号的入关系和出关系一致，因此等价类上的关系有良好定义，并且满足反对称性，构成偏序。
任何合法表示都必须把互相关联的两个符号映射为同一元素；映射为同一元素的两个符号也必定互相关联。因此这些等价类正好就是所需元素。可以直接在符号矩阵上检查界，不必显式建立商集。一个上确界可能有多个符号代表，这不影响元素意义上的唯一性。
对一对符号寻找上确界¶
固定 \(i,j\) ，扫描所有共同上界 \(k\) ，即 \(A_{i,k}=A_{j,k}=1\) .维护候选 \(c\) ：没有候选时取 \(k\) ；若 \(A_{k,c}=1\) ，就把候选改为 \(k\) .
如果上确界 \(u\) 存在，扫描到它时，它不大于当前候选，所以会成为候选。此后能替换它的共同上界只能与它等价。因此最后的候选一定代表上确界。
但在没有上确界时，扫描仍可能留下一个候选，所以必须再次扫描并检查 \(A_{c,k}=1\) 对每个共同上界 \(k\) 都成立。若没有共同上界，或者这个检查失败，就判为非法。若检查通过，候选本身是共同上界并且不大于所有共同上界，恰好满足定义。
下确界完全对偶。将矩阵转置后，用同一个函数检查所有上确界，相当于检查原偏序的所有下确界。两种界都存在才输出 Y .
复杂度¶
反身性检查 \(O(n)\) ，传递性检查 \(O(n^3)\) ；每对符号用两次线性扫描检查上确界，下确界同理，因此总时间 \(O(n^3)\) 、空间 \(O(n^2)\) .多组总时间为 \(O(T+\sum n^3)\) .全一矩阵会被正确识别为只有一个元素的格。