POJ 1632 Vase collection

题意：n个瓶子，每个瓶子有形状颜色两种属性，且这两种属性都有36个类型，告诉你这些瓶子的两种属性的类型，求最大的k满足存在k*k个瓶子，使得这些瓶子的两种属性有k个类型，且覆盖了k*k个属性组合

题解：state[a]是形状为a的覆盖的颜色的状态集（用二进制表示），state[a]&state[b]就是这两个形状都覆盖的颜色，如果这数的二进制位有大于等于2个1，就代表可以组成k=2的符合要求的答案。记录state[a]&state[b]，与第三个形状进行按位与，如果有大于等于3个1，就是可以k=3.......注意别搜重了，由于m只有不超过100，所以最多也就搜10层。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int ans;
LL state[200];
int check(LL st)
{
    int cnt=0;
    for(;st;st>>=1)
        cnt+=(st&1);
    return cnt;
}
void dfs(int k,int i,LL st)
{
    if(k>=ans)
        ans=k;
    for(;i<=36;i++)
    {
        if(check(st&state[i])>=k+1)
            dfs(k+1,i+1,st&state[i]);
    }
}
int main()
{
    int n,T;
    for(scanf("%d",&T);T;T--)
    {
        scanf("%d",&n);
        ans=0;
        memset(state,0,sizeof(state));
        for(int i=0,a,b;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            state[a]|=(1LL<<b);
        }
        dfs(0,1,(1LL<<36)-1);
        printf("%d\n",ans);
    }
    return 0;
}