【每日一题】2021年4月26日题目 Cowpatibility

题号 NC24191
名称 Cowpatibility
来源 USACO中文版-2018 December Contest-Gold

题目描述

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

富坚的 头奶牛各自列举了她们最喜欢的五种冰激凌口味的清单。

为使这个清单更加精炼，每种可能的口味用一个不超过 的正整数 ID 表示。

如果两头奶牛的清单上有至少一种共同的冰激凌口味，那么她们可以和谐共处。

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

样例

输入：
4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 90
输出：
4

在这里，奶牛 4 不能和奶牛 1、2、3 中的任一头和谐共处，奶牛 1 和奶牛 3 也不能和谐共处。

算法1

(容斥原理)

分析：

这道题很明显用容斥原理（相同口味的情况较少）

一般我们思考容斥原理都是从全局来思考

但是这道题颜色数量太多，无法实现

所以我们考虑对于每一头单独的牛进行容斥原理（没想到）

容斥原理：

首先记录总对数

对于第头牛我们计算前面有多少头牛和他有一种口味，两种口味相同……

由于每一头牛只有5种颜色所以总的情况数为

定义为敌头牛与前面的牛有种口味相同的对数（由于这个关系是双向的所以我们规定一个方向就不会计算两次了）

总答案就是

技巧：

我们将每头牛的口味排序（与排列无关只与元素有关）然后做成字符串保存在map中

记录这个拥有组合的口味的牛的数量有多少

时间复杂度

参考文献

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <bitset>

using namespace std;
typedef pair<string,int> PII;
typedef long long LL;
const int N = 500010;
char a[10];
string ice[10];
map<string,int> ham;
int n;

int main()
{
    scanf("%d",&n);
    LL res = 1ll * n * (n - 1) / 2;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 0;j < 5;j ++)
        {
            scanf("%s",&a);
            ice[j] = a;
        }
        sort(ice,ice + 5);
        for(int j = 1;j < 32;j ++)
        {
            int cnt = 0;
            string s = "";
            for(int k = 0;k < 5;k ++)
                if((j >> k) & 1)
                {
                    s += '#' + ice[k];
                    cnt ++;
                }
            if(cnt & 1) res -= ham[s] ++;
            else res += ham[s] ++;
        }
    }
    printf("%lld\n",res);
    return 0;
}

算法2

(bitset)

一直没怎么用过bitset所以记录一下

用记录拥有某种口味的牛的编号（bitset第位为1表示第头牛喜欢这种口味）

用一个每次暴力记录前面与当前牛口味相同的牛是哪些（进行或操作）

答案

tmp.count();//返回bitset中1的个数

时间复杂度,

参考文献

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <bitset>

using namespace std;
typedef pair<string,int> PII;
typedef long long LL;
const int N = 50010;
// char a[10];
// string ice[10];
//map<string,int> ham;
int ice[10];
unordered_map<int,bitset<N>> ham;
bitset<N> tmp;
int n;

int main()
{
    scanf("%d",&n);
    LL res = 1ll * n * (n - 1) / 2;
    for(int i = 1;i <= n;i ++)
    {
        tmp.reset();
        for(int j = 0;j < 5;j ++)
        {
            scanf("%d",&ice[j]);
            tmp |= ham[ice[j]];
        }
        res -= tmp.count();
        for(int j = 0;j < 5;j ++)
            ham[ice[j]].set(i);
    }
    printf("%lld\n",res);
    return 0;
}