[USACO18DEC]Cowpatibility


题面

思路:
正解做法:考虑容斥。

不能和谐的奶牛的对数等于总对数-和谐的奶牛数。
我们可以统计出与当前的奶牛口味有1个相同的奶牛数,有2个相同的……
根据容斥,奇数加,偶数减。我们就可以在$O(2^5N)$的时间复杂度内完成了。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define re register
const int maxn = 5e4 + 10;
inline long long read()
{
long long out = 0;bool flag = 0;char ch = getchar();
while(!isdigit(ch)){flag = (ch == '-');ch = getchar();}
while(isdigit(ch)){out = (out << 1) + (out << 3) + ch - '0';ch = getchar();}
return flag?-out:out;
}
struct ice
{
int x[6];
ice(){x[1] = x[2] = x[3] = x[4] = x[5] = -1;}//构造函数,此处需赋值为-1,因为我们是按照^来比较大小的,不能赋值为0;
}a[maxn];
inline bool operator < (const ice &q,const ice &p){//重载<号比较大小
for(int i = 1 ; i <= 5 ; ++ i)
if(q.x[i] ^ p.x[i])return q.x[i] < p.x[i];
return false;
}
map<ice,long long>mp;//用mp存某个方案有多少个奶牛
long long n,ans;
signed main()
{
n = read();
ans = n * (n - 1) / 2;
for(re int i = 1 ; i <= n ; ++ i)
for(re int j = 1 ; j <= 5 ; ++ j)
a[i].x[j] = read();
for(re int i = 1 ; i <= n ; ++ i)
{
sort(a[i].x + 1,a[i].x + 6);//排序方便比较
for(re int j = 1,top ; j < (1 << 5) ; ++ j)//枚举子集
{
ice tmp;
top = 0;
for(re int k = 0;k < 5;++ k)if(j & (1<<k))tmp.x[++top]=a[i].x[k+1];
ans -= (top&1?1:-1) * mp[tmp];//容斥
++ mp[tmp];
}
}
printf("%lld\n",ans);
return 0;
}

但是由于这个做法比较的常数比较大,所以会跑的特别慢。以下介绍一种暴力但是常数特别小的做法。

暴力做法

我们用一个$map<int,bitset >$记录当前的数有哪些奶牛有。然后用$bitset$优化,就可以过了,时间复杂度是$O(n^2)$的。但是$bitset$优化了很大的常数,并且位运算特快。所以比正解快了一倍

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10;
map<int,bitset<maxn> >mp;
int n,a[maxn][10],ans;
signed main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= 5 ; ++ j)
{
cin >> a[i][j];
mp[a[i][j]].set(i);//将第i位数字置为1
}
}
for(int i = 1 ; i <= n ; ++ i)
{
bitset<maxn>q;
for(int j = 1 ; j <= 5 ; ++ j)q |= mp[a[i][j]];//统计有哪些奶牛有这种口味
ans += n - q.count();
}
cout << ans / 2 << endl;
return 0;
}