安吉D4-C
766 字
4 分钟
安吉D4-C
- 1安吉D19 T1
- 2安吉D19 T3
- 3安吉D20 模考12总结
- 4安吉D17 T3
- 5安吉D17 T4
- 6安吉D19 模考11总结
- 7安吉D15 A
- 8安吉D16 T4
- 9安吉D17 T1
- 10安吉D17 模考10总结
- 11安吉D16 T3
- 12安吉D16 模考9总结
- 13安吉D13 模考8总结
- 14安吉D13-T2
- 15安吉D13-T3
- 16安吉D12-T3
- 17安吉D11-B
- 18安吉D11-C
- 19安吉D11-D
- 20安吉D12 模考7总结
- 21安吉D12-T2
- 22安吉D11-A
- 23安吉D10 模考6总结
- 24安吉D10-T3
- 25安吉D10-T4
- 26安吉D8-E
- 27安吉D9-T4
- 28安吉D8-A
- 29安吉D8-B
- 30安吉D8-C
- 31安吉D8-D
- 32安吉D9 模考5总结
- 33安吉D9-T2
- 34安吉D9-T3
- 35安吉D6-T4
- 36安吉D4-G
- 37安吉D5-T2
- 38安吉D6 模考4总结
- 39安吉D6-T1
- 40安吉D6-T3
- 41安吉-开营测试 T4
- 42安吉D5 模考3总结
- 43安吉D5-T3
- 44安吉D4-A
- 45安吉D4-B
- 46安吉D4-C本文
- 47安吉D4:容斥原理
- 48安吉Day4-D
- 49安吉D3 模考2总结
- 50安吉D3-T1
- 51安吉D3-T2
- 52安吉D3-T4
- 53安吉D2 模考1总结
- 54安吉D2-T2
- 55安吉D1-G
- 56安吉D1-L
- 57安吉D2-T4
原题呈现
P5123 Cowpatibility G
题目描述
研究证明,有一个因素在两头奶牛能否作为朋友和谐共处这方面比其他任何因素都来得重要——她们是不是喜欢同一种口味的冰激凌!
Farmer John 的 头奶牛()各自列举了她们最喜欢的五种冰激凌口味的清单.为使这个清单更加精炼,每种可能的口味用一个不超过 的正整数 表示.如果两头奶牛的清单上有至少一种共同的冰激凌口味,那么她们可以和谐共处.
请求出不能和谐共处的奶牛的对数.
输入格式
输入的第一行包含 .以下 行每行包含 个整数(各不相同),表示一头奶牛最喜欢的冰激凌口味.
输出格式
输出不能和谐共处的奶牛的对数.
输入输出样例 #1
输入 #1
41 2 3 4 51 2 3 10 810 9 8 7 650 60 70 80 90输出 #1
4说明/提示
在这里,奶牛 不能和奶牛 、、 中的任一头和谐共处,奶牛 和奶牛 也不能和谐共处.
或许直接求不能和谐共处的奶牛数量不好求,但是正难则反,我们可以先求能和谐共处的奶牛数量.
能和谐共处的奶牛数量 ,就是至少有一种共同的冰淇淋的奶牛对数,通过容斥原理,我们在所有的冰淇凌口味,一共 种,钦定 种,一共有 种钦定的方法.对于每一种钦定方案,我们统计所有的奶牛对,满足每一头奶牛的列表上都有钦定的 种冰淇凌,这样的奶牛对数量,记为 ,将 种钦定的方法所得的 取和,将其记为 ,则 和 满足:
在程序中,我们定义 用于记录子集 出现的数量,一开始, 为空,遍历每一头奶牛,让这头奶牛尝试和前面的奶牛在不同钦定方案下组成奶牛对,具体来说,需要做以下事情:
- 遍历当前奶牛清单 的所有非空子集 (即枚举钦定方案为 )
- 将
ans增加 - 将 增加 1
- 将
最终答案就是 .
标程
#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;}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!


