本文主要是介绍奶牛合作 对于位操作的敏感，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有n( <= 50)头奶牛，每头奶牛都有一个编号(<1048576)，把他们分成警察和小偷两队（不能有一队为空），如果两队的合作指数相同，那么就是合法的方案（合作指数是指该队成员的编号进行and操作的结果）（限时2000ms）。
首先比较敏感的就是编号不算大，是2的20次方，还有就是and操作的结果只和0的个数有关系，如果某位有一个0，那么结果必然是0。所以对每一位进行考虑（指的是将数字转成二进制的某位）：
假如有4有奶牛，编号依次为1、2、3、4：
位 3 2 1
1 0 0 1 //最左边的0称为第三位，中间的0为第二位，1是第一位
2 0 1 0
3 0 1 1
4 1 0 0
方式一： 奶牛1和奶牛2扮演警察，奶牛3和奶牛4扮演小偷。
方式二： 奶牛1和奶牛2扮演小偷，奶牛3和奶牛4扮演警察。
有四种情况：
1.若每头奶牛该位都是0，那么无论怎么分配，结果的这一位还是0。
2.若每头奶牛该位都是1，那么无论怎么分配，结果的这一位还是1。
3.如果有且只有一头奶牛该位是0，那么结果就是一队是0，一队是1。是无解的。
4.如果有两头以上的（包括两头）奶牛该位是0，只要不把他们都安放在同一个队伍就是合法的。
那么就可以用容斥原理算出不合法的方案数。从每一位进行考虑，将所有该位为0的奶牛都在同一个队伍的情况减去。
有点超时，我是用并查集来寻找0的连通块。
//#define watch
#include <cstdio>
using namespace std;
typedef long long LL;const int N = 50, M = 20;int n, father[M];
bool vis[M];
LL d[M];inline int getfather(int k)
{if (father[k] == k) return k;return father[k] = getfather(father[k]);
}int main()
{freopen("role.in", "r", stdin);freopen("role.out", "w", stdout);scanf("%d\n", &n);for (int i = 0; i < n; i ++) {int a;scanf("%d", &a);for (int j = 0; j < M; j ++) if ((a >> j & 1) == 0)d[j] |= 1LL << i;}int cant = 0;for (int i = 0; i < M; i ++) {int cnt = 0;for (int j = 0; j < n; j ++)if (d[i] >> j & 1) cnt ++;if (cnt == n || cnt == 0) cant |= 1 << i;else if (cnt == 1){printf("0\n");return 0;}}LL ans = (1LL << n) - 2LL;int setn = 1 << M;for (int set = 1; set < setn; set ++) {if (set & cant) continue;bool isplus = true;LL tot = 0LL;for (int i = 0; i < M; i ++)if (set >> i & 1) {vis[i] = false;father[i] = i;isplus = !isplus;tot |= d[i];for (int j = 0; j < i; j ++)if ((set >> j & 1) && (d[i] & d[j])) father[getfather(i)] = getfather(j);}int cnt = 0;for (int i = 0; i < M; i ++)if ((set >> i & 1) && (! vis[getfather(i)])) {vis[father[i]] = true;cnt ++;}for (int i = 0; i < n; i ++) if ((tot >> i & 1LL) == 0) cnt ++;LL t = (1LL << cnt) - 2LL;#ifdef watchprintf("set:%d isplus:%s val:%I64d\n", set, isplus?"true ":"false", t);#endifif (isplus) ans += t;else ans -= t;}printf("%I64d\n", ans);return 0;
}
这篇关于奶牛合作 对于位操作的敏感的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
