互联网排名前十的公司_个人主页生成_电子商务平台_网站备案查询工信部官网

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1735D - Meta-set

---

二、解题报告

1、思路分析

考虑一个五元组<a, b, c, d, e>，最多有几个set?

两个：如果  <a, b, c> 是 set，那么 另一个 set 最多拥有 <a, b, c> 中的一个元素，因为两个元素固定，就会得出另一个

那么我们发现。我们只需枚举两个 set 相交的那个元素 x，假如 x 在 cnt[x] 个set 中出现，那么 x

作为相交元素的贡献就是 (cnt[x] - 1) * cnt[x] / 2

对于 cnt[x] 我们 固定 a, b 就能得出 c，用 map 维护一下暴力预处理即可

2、复杂度

时间复杂度： O(N^2 k log(N^2) k)空间复杂度：O(N^2 k)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {int n, k;std::cin >> n >> k;std::map<std::vector<int>, int> mp;std::map<int, int> f;std::vector<std::vector<int>> c(n, std::vector<int>(k));for (int i = 0; i < n; ++ i) {for (int j = 0; j < k; ++ j) {std::cin >> c[i][j];}}auto get = [&](int i, int j) -> std::vector<int>{std::vector<int> res(k);for (int x = 0; x < k; ++ x) {res[x] = c[i][x] == c[j][x] ? c[i][x] : 3 - c[i][x] - c[j][x];}return res;};for (int i = 0; i < n; ++ i) {for (int j = i + 1; j < n; ++ j) {auto res = get(i, j);if (mp.contains(res)) {++ f[i];++ f[j];++ f[mp[res]];}}mp[c[i]] = i;}i64 ans = 0;for (int i = 0; i < n; ++ i) {ans += (f[i] - 1LL) * f[i] / 2;}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint START = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t --) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - START << '\n';
#endifreturn 0;
}