📝 题目大意

有 $n$ 个人拍了 $m$ 张合影，每张照片给出了 $n$ 个人的排列顺序。如果两个人从未在任何一张照片中相邻站立，则称他们为一对"不开心的人"。求不开心的人有多少对。

💡 解题思路

1. 题目分析：$n, m \le 50$，数据范围很小，可以直接暴力统计。核心是判断任意两个人 $(x, y)$ 是否在至少一张照片中相邻过。

2. 算法推导：

   • 用一个布尔二维数组 adj[n][n]（邻接矩阵）记录哪些人之间相邻过，初始全为 false。
   • 遍历每张照片的每一对相邻位置 $(j, j+1)$，将 adj[a][b] 和 adj[b][a] 标记为 true（其中 a = photos[i][j]，b = photos[i][j+1]，均为 0-indexed）。
   • 最后枚举所有无序对 $(i, j)$（$i < j$），若 adj[i][j] 为 false，说明这对人从未相邻，计数器 unhappy 加一。
   • 输出 unhappy。

3. 边界与细节：

   • 输入中人的编号从 $1$ 开始，代码中统一减 $1$ 转为 0-indexed，方便用数组下标访问。
   • 相邻关系是无向的，标记时需要同时标记 adj[a][b] 和 adj[b][a]。
   • 统计时只枚举 $i < j$ 的无序对，避免重复计数。
   • 注意 $n$ 最小为 $2$，$m$ 最小为 $1$，保证至少有一张照片可读。

⏱️ 复杂度分析

• 时间复杂度：$O(m \cdot n + n^2)$，由于 $n, m \le 50$，完全可行。
• 空间复杂度：$O(n^2)$，用于存储邻接矩阵。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    // 存储 m 张照片，每张照片有 n 个人的排列
    vector<vector<int>> photos(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> photos[i][j];
            photos[i][j]--; // 转为 0-indexed，方便数组索引
        }
    }
    // adj[x][y] = true 表示 x 和 y 在至少一张照片中相邻过
    vector<vector<bool>> adj(n, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n - 1; j++) {
            int a = photos[i][j];      // 当前照片中第 j 个人
            int b = photos[i][j + 1];  // 当前照片中第 j+1 个人（与 a 相邻）
            adj[a][b] = true;          // 标记相邻关系（无向）
            adj[b][a] = true;
        }
    }
    int unhappy = 0;
    // 枚举所有无序对 (i, j)，i < j
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!adj[i][j]) {  // 从未相邻过 → 不开心
                unhappy++;
            }
        }
    }
    cout << unhappy << endl;
    return 0;
}