題意是一個覆蓋問題，用n個各種邊長的小三角形來覆蓋一個六邊形，基本上可以直接深搜，可以試著覆蓋六分之一，三分之一和二分之一至全部，四種覆蓋形式有一種達(dá)到完全覆蓋即可退出，以此來降低復(fù)雜度。
對三角形坐標(biāo)的表示上采用了如下的表示法：
以這種方式來表示整個六邊形上的三角形（圖畫的比較省略。。因?yàn)槲抑粫卯媹D。。。。）
這題主要的難點(diǎn)不在思路，而在coding
#include<iostream>
#include<cstring>
using namespace std;
int l,n;
int t[10];
bool b[60][110];
bool used[26];
bool square_vis[6*25*25+1];
int zero;
struct node
{
int x;
int y;
} stack[1000];
void flood_line(int x,int y,int l,int c)
{
int i,j;
int tx,ty;
if ((x+y)%2)
{
i = l-1;
for (j=y-i; j<=y+i; j++)
b[x+i][j] = c;
}
else
{
i = l-1;
tx = x+i;
ty = y+i;
for (j=0; j<2*i+1; j++)
{
b[tx][ty] = c;
if (j%2)ty++;
else tx--;
}
}
}
void flood(int x,int y,int l,int c)
{
if ((x+y)%2)
{
for (int i=0; i<l; i++)
for (int j=y-i; j<=y+i; j++)
b[x+i][j] = c;
}
else
{
for (int i =0; i<l; i++)
{
int tx = x+i;
int ty = y+i;
for (int j=0; j<2*i+1; j++)
{
b[tx][ty] = c;
if(j%2)
ty++;
else tx--;
}
}
}
}
int cal(int x,int y)
{
int tx,ty,i,j;
if ((x+y)%2)
{
for (i=0; ; i++)
for (j=y-i; j<=y+i; j++)
if(b[x+i][j])
return i;
}
else
{
for (i=0; ; i++)
{
tx = x+i;
ty = y+i;
for (j=0; j<2*i+1; j++)
{
if (b[tx][ty])
return i;
if (j%2)
ty++;
else tx--;
}
}
}
}
bool search(int step)
{
int x,y;
int i,maxl;
x = stack[step-1].x;
y = stack[step-1].y;
while(x<2*l)
{
if (b[x][y]) y++;
else break;
if (y>100)
{
x++; y=0;
}
}
if (x>=2*l)
return true;
maxl = cal(x,y);
flood(x,y,maxl,1);
zero -= maxl*maxl;
stack[step].x= x;
stack[step].y = y;
for (i=maxl; i>=2; i--)
{
if(used[i]&&square_vis[zero]&&search(step+1))
return true;
flood_line(x,y,i,0);
zero+=(2*i-1);
}
b[x][y] = 0;
zero++;
return false;
}
void init()
{
memset(used,false,sizeof(used));
cin >> l;
cin >> n;
for (int i=0; i<n; i++)
{
cin >> t[i];
used[t[i]] = true;
}
n = 0;
for (int i=1; i<=l; i++)
if (used[i])
t[n++] = i;
}
void run()
{
for(int i=0; i<n; i++)
if(l%t[i]==0)
{
cout << "YES"<<endl;
return;
}
bool length_vis[26];
memset(length_vis,false,sizeof(length_vis));
length_vis[0] = true;
for (int i = 0; i<=l; i++)
if (length_vis[i])
for (int j=0; j<n; j++)
if (i+t[j]<=l)
length_vis[i+t[j]] = true;
if (!length_vis[l])
{
cout << "NO"<<endl;
return;
}
memset(square_vis,false,sizeof(square_vis));
square_vis[0] = true;
for (int i=0; i<=6*l*l; i++)
if (square_vis[i])
for (int j=0; j<n; j++)
if (i+t[j]*t[j]<=6*l*l)
square_vis[i+t[j]*t[j]]= true;
if (!square_vis[6*l*l])
{
cout << "NO"<<endl;
return;
}
memset(b,true,sizeof(b));
flood(0,25,l,0);
zero = l*l;
stack[0].x = 0;
stack[0].y = 25;
if (search(1))
{
cout << "YES"<<endl;
return;
}
memset(b,true,sizeof(b));
flood(0,25,l,0);
flood(0,26,l,0);
zero = l*l*2;
if (search(1))
{
cout<< "YES"<<endl;
return;
}
memset(b,true,sizeof(b));
flood(0,25,l,0);
flood(0,26,l,0);
flood(0,25+2*l,l,0);
zero = l*l*3;
if (search(1))
{
cout << "YES"<<endl;
return;
}
memset(b,true,sizeof(b));
flood(0,25,l,0);
flood(0,26,l,0);
flood(0,25+2*l,l,0);
flood(l,25-l+1,l,0);
flood(l,25+l,l,0);
flood(l,25+l+1,l,0);
zero = 6*l*l;
if (search(1))
{
cout << "YES"<<endl;
return;
}
cout << "NO"<<endl;
return;
}
int main()
{
int cas;
cin >> cas;
while(cas--)
{
init();
run();
}
}