2013
12-09

# The Bermuda Triangle

People in the hidden region of the Bermuda Triangle make everything they need in triangular shapes. One day, someone decided to break the rule and bake a hexagonally shaped cake. But as usual, he has to serve the cake in triangular pieces. The pieces are equilateral triangles but in different sizes for different people. He can use as many triangles as needed to cut the cake into pieces, such that nothing remains from the cake. For example, the following figure shows one way that a hexagon with side 9 can be cut into triangles with side 2 and 3. (The cake is cut along the thick lines, thin lines are drawn to show the sizes).

Input is a hexagon and triangle types (specified by the length of their sides) and the goal is to decide if the hexagon can be completely divided by the given triangle types.

The first line of the input file contains a single integer t (1<=t <=10), the number of test cases, followed by the input data for each test case. Each test case consists of a single line, containing s (1<= s <=25), the length of the hexagon’s side, followed by n, the number of triangle types (1 <=n <=10), followed by n integers representing the length of each triangle type’s side (between 1 and 25, inclusive).

There should be one output line per test case containing either YES or NO depending on whether the hexagon can be completely divided by the given triangle types.

3
5 2 2 3
7 2 3 2
13 2 2 3

NO
NO
YES

000000011111

000000000111

000000000001

100000000000

111000000000

111110000000

（2）、等边三角形映射到这个左边中即为直角三角形了   如下图则是表示边长为3的三角形  （正着和倒着）

0                                     00000

000                                     000

00000                                     0

1：如果有小三角形的边长能整除六边形边长，直接yes。
2：如果给的小三角形中某一个边长能整除另一个边长，去掉大的。
3：三角形从小往大搜，当某个三角形不能放的时候，直接return。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 110
using namespace std;

int n,m,flag,cnt;
int a[15],b[15];
bool mp[maxn][maxn];

void showmap()                // 中间输出函数  方便debug
{
int i,j;
printf("\n");
for(i=1; i<=2*n; i++)
{
for(j=1; j<=4*n; j++)
{
printf("%d",mp[i][j]);
}
printf("\n");
}
}
void presolve()
{
int i,j;
sort(a+1,a+m+1);
cnt=0;
for(i=1; i<=m; i++)
{
if(a[i]>=2*n) break;
for(j=1; j<=cnt; j++)
{
if(a[i]%b[j]==0) break;
}
if(j==cnt+1) b[++cnt]=a[i];
}
}
void init()
{
int i,j,temp;
memset(mp,1,sizeof(mp));
for(i=1; i<=n; i++)
{
temp=2*n+1+(i-1)*2;
for(j=1; j<=temp; j++)
{
mp[i][j]=0;
}
}
for(i=n+1; i<=2*n; i++)
{
for(j=4*n; j>1+(i-n-1)*2; j--)
{
mp[i][j]=0;
}
}
}
bool isok(int u,int v,int k)
{
int i,j;
//   printf("u:%d v:%d k:%d\n",u,v,k);
if(v%2==0)
{
for(i=u+b[k]-1;i>=u;i--)
{
for(j=v+2*(b[k]-1);j>=v+2*(b[k]-1)-2*(b[k]+u-1-i);j--)
{
if(mp[i][j])
{
//                  printf("i:%d j:%d\n",i,j);
return false;
}
}
}
}
else
{
for(i=u;i<u+b[k];i++)
{
for(j=v;j<v+1+2*(i-u);j++)
{
if(mp[i][j]) return false;
}
}
}
return true;
}
void mark(int u,int v,int k,int flag1)
{
int i,j;
if(v%2==0)
{
for(i=u+b[k]-1;i>=u;i--)
{
for(j=v+2*(b[k]-1);j>=v+2*(b[k]-1)-2*(b[k]+u-1-i);j--)
{
if(flag1) mp[i][j]=1;
else mp[i][j]=0;
}
}
}
else
{
for(i=u;i<u+b[k];i++)
{
for(j=v;j<v+1+2*(i-u);j++)
{
if(flag1) mp[i][j]=1;
else mp[i][j]=0;
}
}
}
}
void dfs(int x,int y)
{
int i,j;
if(flag) return ;
//   showmap();
//   printf("x:%d y:%d\n",x,y);
if(x==2*n&&y>4*n||x>2*n)
{
flag=1;
return ;
}
if(y>4*n) dfs(x+1,1);
else if(mp[x][y])             // 加上else  不然会死循环  想一想 为什么
{
for(j=y+1; j<=4*n; j++)
{
if(mp[x][j]==0) break;
}
dfs(x,j);
}
else
{
for(i=1; i<=cnt; i++)
{
if(isok(x,y,i))
{
mark(x,y,i,1);     // 标记
dfs(x,y+1);
mark(x,y,i,0);     // 取消标记
}
else break;
}
}
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++)
{
scanf("%d",&a[i]);
if(n%a[i]==0) flag=1;
}
if(flag)  printf("YES\n");      // 预处理  三角形的边长是六边形约数则一定满足条件
else
{
presolve();                 // 预处理
init();
showmap();
dfs(1,1);
if(flag)  printf("YES\n");
else printf("NO\n");
}
}
}

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……

3. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。