视频加载失败

安吉D4-C

766 字
4 分钟
安吉D4-C
原题呈现

P5123 Cowpatibility G#

题目描述#

研究证明,有一个因素在两头奶牛能否作为朋友和谐共处这方面比其他任何因素都来得重要——她们是不是喜欢同一种口味的冰激凌!

Farmer John 的 NN 头奶牛(2N5×1042\le N\le 5\times 10^4)各自列举了她们最喜欢的五种冰激凌口味的清单.为使这个清单更加精炼,每种可能的口味用一个不超过 10610^6 的正整数 ID\texttt{ID} 表示.如果两头奶牛的清单上有至少一种共同的冰激凌口味,那么她们可以和谐共处.

请求出不能和谐共处的奶牛的对数.

输入格式#

输入的第一行包含 NN.以下 NN 行每行包含 55 个整数(各不相同),表示一头奶牛最喜欢的冰激凌口味.

输出格式#

输出不能和谐共处的奶牛的对数.

输入输出样例 #1#

输入 #1#

4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 90

输出 #1#

4

说明/提示#

在这里,奶牛 44 不能和奶牛 112233 中的任一头和谐共处,奶牛 11 和奶牛 33 也不能和谐共处.

或许直接求不能和谐共处的奶牛数量不好求,但是正难则反,我们可以先求能和谐共处的奶牛数量.

能和谐共处的奶牛数量 ansans,就是至少有一种共同的冰淇淋的奶牛对数,通过容斥原理,我们在所有的冰淇凌口味,一共 tottot 种,钦定 ii 种,一共有 (toti)\binom{tot}{i} 种钦定的方法.对于每一种钦定方案,我们统计所有的奶牛对,满足每一头奶牛的列表上都有钦定的 ii 种冰淇凌,这样的奶牛对数量,记为 ff,将 (toti)\binom{tot}{i} 种钦定的方法所得的 ff 取和,将其记为 gig_i,则 ansansgig_i 满足:

ans=g1g2+g3g4+g5ans=g_1-g_2+g_3-g_4+g_5

在程序中,我们定义 cntTcnt_T 用于记录子集 TT 出现的数量,一开始,cntcnt 为空,遍历每一头奶牛,让这头奶牛尝试和前面的奶牛在不同钦定方案下组成奶牛对,具体来说,需要做以下事情:

  • 遍历当前奶牛清单 sis_i 的所有非空子集 TT(即枚举钦定方案为 TT
    • ans 增加 ​​(1)T1cntT​​(-1)^{|T-1|} * cnt_T
    • cntTcnt_T 增加 1

最终答案就是 (n1)×n/2ans(n - 1) \times n / 2 - ans

标程

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 100;
ll ans;
int n;
vector<int> a[N];
map<vector<int>, int> cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 5; j++) {
int x;
cin >> x;
a[i].push_back(x);
}
sort(a[i].begin(), a[i].end());
}
ans = 1ll * (n - 1) * n / 2;
for (int i = 1; i <= n; i++) {
vector<int> vec;
for (int k : a[i])
vec.push_back(k);
for (int st = 1; st <= (1 << 5) - 1; st++) {
vector<int> now;
for (int j = 0; j <= 4; j++) {
if (st & (1 << j))
now.push_back(vec[j]);
}
ans += (now.size() % 2 ? -1 : 1) * cnt[now];
cnt[now]++;
}
}
cout << ans;
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

安吉D4-C
https://blog.jerrylab.top/posts/problem/anji2026/D4/C/
作者
Jerry
发布于
2026-08-04
许可协议
CC BY-NC-SA 4.0
Profile Image of the Author
Jerry
Hello, I'm Jerry.
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
最新动态
站点统计
文章
80
分类
3
标签
35
总字数
89,198
运行时长
0
最后活动
0 天前
站点信息
构建平台
Cloudflare Pages
博客版本
Firefly v6.16.5
文章许可
CC BY-NC-SA 4.0