🧠 题解思路

本质上，这是一个二维正方形覆盖问题（特殊的拼图问题）：

给你一个 $s \times s$ 的大正方形（蛋糕），问能否用给定尺寸的若干个小正方形无重叠地刚好覆盖它。

✅ 关键点

每块小蛋糕是正方形

不能重叠，不能超出大蛋糕区域

必须完全覆盖，没有剩余

✨ 解题方法

这个问题是典型的搜索 + 剪枝 + 回溯问题。下面分步骤解释：

步骤一：面积预判（剪枝）

总面积必须匹配：

∑ 𝑖

1 𝑛 𝑎 𝑖 2

𝑠 2 i=1 ∑ n ​ a i 2 ​ =s 2

如果面积不相等，立即输出 HUTUTU!

步骤二：DFS 搜索贴块

将大蛋糕看作二维网格（比如 $s \times s$ 的布尔数组）

尝试把所有小方块贴上去（从左到右、从上到下）

每次尝试在空位贴一个未使用的小正方形块，满足不越界、不重叠

尝试所有排列方式，直到覆盖成功或搜索失败

步骤三：剪枝优化

优先放大的方块（按边长降序排序）→ 降低深度

对当前空位尝试所有合适的块，如果没有合适块剪枝

用回溯恢复现场

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,m;
int a[11];//边长为[i]的蛋糕的数量
int ck[50];//第[i]列已填的高度
bool dfs(int y){
    if(y==m)return 1;
    int i,j;
    //
    int mi=200,pos=0;
    for(j=1;j<=n;j++)
        if(ck[j]<mi){
            mi=ck[j];
            pos=j;
        }
    //
    for(i=10;i;i--){
        if(!a[i])continue;//没有该尺寸蛋糕，跳过
        if(pos+i-1>n)continue;//该尺寸宽度比剩余宽度大，跳过
        for(j=0;j<i;j++){
            if(ck[pos+j]<=ck[pos] && ck[pos+j]+i<=n)continue;
            else break;
        }
        if(j<i)continue;//高度不足，跳过
        for(j=0;j<i;j++)ck[pos+j]+=i;
        a[i]--;
        if(dfs(y+1))return 1;
        a[i]++;
        for(j=0;j<i;j++)ck[pos+j]-=i;
    }
    return 0;
}
int main(){
    scanf("%d",&T);
    int i,j;
    while(T--){
        memset(ck,0,sizeof ck);
        memset(a,0,sizeof a);
        scanf("%d%d",&n,&m);
        int x;
        int ssum=0;
        int cnt=0;
        for(i=1;i<=m;i++){
            scanf("%d",&x);
            a[x]++;
            ssum+=x*x;
            if(x>n/2)cnt++;//尺寸大于n/2的蛋糕若有多块，肯定不可行
        }
        if(ssum!=n*n || cnt>1){
            printf("HUTUTU!\n");
            continue;
        }
        if(!dfs(0)){
            printf("HUTUTU!\n");
        }
        else printf("KHOOOOB!\n");

    }
    return 0;
}