谜题:
这是一个在坐标轴上玩的,关于“坐标集合”({a1,a2,…,am},{b1,b2,…,bl}) 的游戏。 首先,Bob分别在坐标a1,a2,…,am放上一个球。接下来Bob分别在坐标b1+0.5,b2+0.5,…,bl+0.5挖了一个洞。最后Bib会将所有球往前推(往坐标变大的方向),让球滚进第一个遇到的洞里。如果有奇数个洞有最少一个球,Bob就赢得这场游戏。
现在Bob想知道对于n个集合S1,S2,…,Sn, 他可以在多少场“坐标集合”(Si,Sj) (i<j)的游戏中胜出。
Input
一个整数t,表示样例个数(t<=10)。每组样例第一行一个整数n (2≤n≤5000).
接下来n行分别有一个整数ki,表示集合Si的大小,ki后分别有ki个不同的整数Si,1,Si,2,…,Si,ki表示集合Si (1≤ki≤50,1≤Si,j≤50).
Output
每组样例输出一个整数表示Bob可以赢的游戏场数。
Sample Input
2
2
1 1
2 1 2
2
2 1 2
2 2 1
Sample Output
1
0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5005;
ll state[maxn];
int red(){
char z=getchar();
while (z<'0' || z>'9') z=getchar();
int ans=0;
while (z>='0' && z<='9') {
ans=ans*10+z-'0';
z=getchar();
}
return ans;
}
int main(){
int t;
int n,c,a;
scanf("%d",&t);
while(t--){
n=red();
for(int i=1;i<=n;i++){
state[i]=0;
c=red();
for(int j=1;j<=c;j++){
a=red()-1;
state[i]|=1ll<<a; //利用二进制进行保存
}
}
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
ll a1=state[i],a2=state[j];
ll t1=a1&a2; //直接进洞
a1^=t1; //把直接进洞的标记为0
a2=~a2; //把有洞的标记为0,无洞的标记为1
ll a3=(a1+a2)&state[j]; //模拟进位,a1中某一位为1,2中某一位为0的情况是不可能存在的
//所以会一直进位到出现2个0(a1为0,a2为1的时候还是会进位),此时便是前面的求球都进入这个洞
//&state[j]是把原来有洞的地方的球取出来,因为可能某个位置为1的地方原来没有洞,
//这种情况可能是两个1再有一位进位而产生的
a3|=t1;
int res=0;
while(a3){
a3-=a3&(-a3);
res^=1;
}
cnt+=res;
}
printf("%d\n",cnt);
}
return 0;
}