问题分析

程先生有一些丰朝花瓶，每个花瓶有特定的形状和装饰。目标是找到最大的整数k，使得存在k种形状和k种装饰，且这些形状和装饰的每一种组合（共k×k种）都至少存在于一个花瓶中。

代码思路

1. 输入处理：读取测试用例数量和每个测试用例中的花瓶信息。
2. 状态压缩：使用位运算将每种形状对应的装饰集合压缩为一个整数（state数组）。
3. 深度优先搜索（DFS）：通过递归方式尝试所有可能的形状组合，寻找最大的k值。

代码详细解释

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int ans;            // 存储最终答案的全局变量
LL state[200];      // 存储每种形状对应的装饰集合的位掩码

// 计算一个整数中二进制位为1的个数（即汉明重量）
int check(LL st)
{
    int cnt=0;
    for(;st;st>>=1)
        cnt+=(st&1);
    return cnt;
}

// 深度优先搜索函数
// k: 当前考虑的形状数量
// i: 当前可以选择的最小形状编号
// st: 当前已选择形状的装饰集合的交集
void dfs(int k,int i,LL st)
{
    if(k>=ans)      // 更新最大k值
        ans=k;
    for(;i<=36;i++) // 尝试所有可能的形状
    {
        // 如果当前形状的装饰集合与已有交集的交集大小至少为k+1
        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);
        }
        
        // 从k=0开始DFS搜索，初始形状可选范围从1开始，初始装饰集合为所有装饰的并集
        dfs(0,1,(1LL<<36)-1);
        printf("%d\n",ans);    // 输出最大k值
    }
    return 0;
}

复杂度分析

• 时间复杂度：由于形状和装饰的数量最多为36，DFS的深度最大为36，每次递归需要O(36)的时间计算交集大小，因此总时间复杂度约为O(36!)，但实际运行时间会因为剪枝条件而显著降低。
• 空间复杂度：主要是存储状态数组和递归调用栈，空间复杂度为O(36)。