题意分析

题目背景

本题属于几何分割与回溯搜索问题，描述如何用给定大小的等边三角形完全分割一个正六边形蛋糕。关键在于验证是否存在一种切割方式，使得所有三角形块无重叠、无遗漏地覆盖整个六边形。

核心问题

1. 六边形结构：边长为$s$的正六边形，可映射为二维网格坐标系。
2. 三角形切割规则：
   • 使用指定边长的等边三角形。
   • 三角形可朝上或朝下放置（由$y$坐标奇偶性决定）。
3. 目标：判断是否存在一种切割方案，使得六边形被完全覆盖。

输入输出

• 输入：
  • $t$：测试用例数量。
  • 每个测试用例包含：
    • $s$：六边形边长。
    • $n$：三角形类型数量。
    • $n$个整数：三角形边长列表。
• 输出：若可完全分割输出YES，否则NO。

解题思路

1. 预处理优化

1. 直接整除检查：若存在三角形边长$k$满足$s \mod k = 0$，直接返回YES。
2. 无效边长过滤：移除所有边长$>s$的三角形。
3. 去冗余：若某边长能被更小的边长整除，则移除该边长。

2. 六边形网格建模

• 将六边形映射为二维布尔数组hexagon[110][110]：
  • true表示可切割区域。
  • false表示已切割或无效区域。
• 坐标映射规则：
  • 行范围：$1$到$2s$。
  • 列范围：动态扩展，取决于行号$i$：
    • $i \leq s$时，列数为$2s - 1 + 2i$。
    • $i > s$时，列数为$4s - 2(i - s)$。

3. 回溯搜索（DFS）

1. 切割验证：
   • 朝上三角形（$y$为奇数）：检查区域是否未被占用。
   • 朝下三角形（$y$为偶数）：类似验证。
2. 递归切割：
   • 尝试所有有效边长，标记已切割区域。
   • 若后续递归失败，回溯恢复状态。
3. 终止条件：
   • 所有区域被切割（返回YES）。
   • 无法继续切割（返回NO）。

算法实现

代码框架

#include<bits/stdc++.h> 
using namespace std;
 
int hexagon[110][110];
int ori_size,n,cut_size[11];
 
bool can_cut(int x,int y,int size)
{
    int i,j;
    if (y+2*size-2>ori_size*4 || x+size-1>ori_size*2)
        return false;
    if (y%2==1)
    {
        for (i=0;i<size;i++)
            for (j=0;j<2*i+1;j++)
                if (hexagon[x+i][y+j]==false)
                    return false;
    }
    else
    {
        for (i=0;i<size;i++)
            for (j=2*i;j<2*size-1;j++)
                if (hexagon[x+i][y+j]==false)
                    return false;
    }
    return true;
}
 
void cut(int x,int y,int size)
{
    int i,j;
    if (y%2==1)
        for (i=0;i<size;i++)
            for (j=0;j<2*i+1;j++)
                hexagon[x+i][y+j]=false;
    else
        for (i=0;i<size;i++)
            for(j=2*i;j<2*size-1;j++)
                hexagon[x+i][y+j]=false;
}
 
void decut(int x,int y,int size)
{
    int i,j;
    if (y%2==1)
        for (i=0;i<size;i++)
            for (j=0;j<2*i+1;j++)
                hexagon[x+i][y+j]=true;
    else
        for (i=0;i<size;i++)
            for(j=2*i;j<2*size-1;j++)
                hexagon[x+i][y+j]=true;
}
 
bool dfs(int x,int y)
{
    int i,j;
    if (x>ori_size*2)
        return true;
    if (y>4*ori_size)
        return dfs(x+1,1);
    if (hexagon[x][y]==false)
    {
        for (j=y+1;j<=4*ori_size;j++)
            if (hexagon[x][j])
                break;
        return dfs(x,j);
    }
    for (i=0;i<n;i++)
    {
        if (can_cut(x,y,cut_size[i]))
        {
            cut(x,y,cut_size[i]);
            if (dfs(x,y+1))
                return true;
            decut(x,y,cut_size[i]);
        }
        else
            break;
    }
    return false;
}
 
int main()
{
    int test_cases,i,j,k;
    bool flag;
    scanf("%d",&test_cases);
    while (test_cases--)
    {
        scanf("%d%d",&ori_size,&n);
        for (i=0,flag=false;i<n;i++)
        {
            scanf("%d",&cut_size[i]);
            if (ori_size%cut_size[i]==0)
                flag=true;
        }
        if (flag)
        {
            printf("YES\n");
            continue;
        }
        memset(hexagon,false,sizeof(hexagon));
        for (i=1;i<=ori_size;i++)
            for (j=1;j<=ori_size*2-1+2*i;j++)
                hexagon[i][j]=true;
        for (i=ori_size+1;i<=ori_size*2;i++)
            for (j=(i-ori_size)*2;j<=ori_size*4;j++)
                hexagon[i][j]=true;
        sort(cut_size,cut_size+n);
        for (i=0;i<n;i++)
            if (cut_size[i]>ori_size)
            {
                n=i-1;
                break;
            }
        for (i=0;i<n;i++)
            for (j=0;j<i;j++)
                if (cut_size[i]%cut_size[j]==0)
                {
                    for (k=i;k<n-1;k++)
                        cut_size[k]=cut_size[k+1];
                    i--;
                    n--;
                    break;
                }
        if (dfs(1,1))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

关键步骤

1. 直接整除检查：快速判断简单情况。
2. 网格初始化：根据六边形几何填充可切割区域。
3. 回溯搜索：
   • 按行列扫描未切割区域。
   • 尝试所有有效三角形切割方案。
   • 递归验证后续切割可行性。

复杂度分析

• 时间：最坏$O((2s)^2 \cdot n!)$，实际因剪枝大幅优化。
• 空间：$O(s^2)$存储网格状态。