首页 > 代码库 > CodeForces Gym 101063C 二进制压缩
CodeForces Gym 101063C 二进制压缩
http://codeforces.com/gym/101063/problem/C
给n个人,m样物品,每个人可以从物品中选择几样。两人选择物品的交集元素个数比上并集元素个数如果大于某个比例即可将两人配对。求配对数。
n的范围是1e5,直接比较所有人的选择会TLE,应该将所有选择物品的情况用二进制压缩,m最大是10,情况数目小于2048,可以接受。注意配对总数范围应为long long。
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int people[2048], m; int count(int a); int main() { int n, i, j, num, item, temp, and, or ; long long pair = 0; double rate; scanf("%d %d", &n, &m); for (i = 0; i < n; i++) { scanf("%d", &num); temp = 0; for (j = 0; j < num; j++) { scanf("%d", &item); temp += 1 << (item - 1); } people[temp]++; } scanf("%lf", &rate); for (i = 1; i < (1 << m); i++) { for (j = i; j < (1 << m); j++) { and = count(i & j); or = count(i | j); if (((float) and / (float) or ) >= rate) { if (i == j) pair += (long long int)people[i] * (long long int)(people[i] - 1) / 2; else pair += (long long int)people[i] * (long long int)people[j]; } } } printf("%lld", pair); return 0; } int count(int a) { int num = 0, i; for (i = 0; i < m; i++) { num += (1 & (a >> i & 1)); } return num; }
值得纪念的一道题!
CodeForces Gym 101063C 二进制压缩
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。