import java.util.*;

public class Main{
	private static final Scanner in=new Scanner(System.in);
	private int size;
	private Set<Integer> typeSizes=new TreeSet<Integer>();
	private boolean[][] covered;
	public Main(){
		size=in.nextInt();
		int typeNum=in.nextInt();
		while(typeNum-->0){
			int typeSize=in.nextInt();
			if(typeSize<=size)
				typeSizes.add(typeSize);
		}
		Set<Integer> toRemove=new HashSet<Integer>();
		for(int typeSize:typeSizes)
			for(int next:typeSizes)
				if(next!=typeSize && next%typeSize==0)
					toRemove.add(next);
		typeSizes.removeAll(toRemove);
	}
	public boolean CanDivide(){
		for(int typeSize:typeSizes)
			if(size%typeSize==0)
				return true;
		covered=new boolean[2*size][4*size];
		for(int x=0;x<size;x++)
			Arrays.fill(covered[x],2*(size+x)+1,4*size,true);
		for(int x=size;x<2*size;x++)
			Arrays.fill(covered[x],0,2*(x-size)+1,true);
		return Search(0,0);
	}
	private boolean Search(int x,int y){
		if(x>=2*size)
			return true;
		if(y>=4*size)
			return Search(x+1,0);
		if(covered[x][y])
			return Search(x,y+1);
		int sizeMax=SizeMax(x,y);
		for(int typeSize:typeSizes){
			if(typeSize>sizeMax)
				break;
			Fill(x,y,typeSize,true);
			if(Search(x,y+1))
				return true;
			Fill(x,y,typeSize,false);
		}
		return false;
	}
	private int SizeMax(int x,int y){
		for(int typeSize=1;typeSize<size;typeSize++)
			if(!SizeAvaliable(x,y,typeSize))
				return typeSize-1;
		return size;
	}
	private boolean SizeAvaliable(int x,int y,int testSize){
		if(y%2==0){
			for(int step=0;step<testSize;step++)
				for(int yFill=y;yFill<=y+2*step;yFill++)
					if(x+step>=2*size || yFill>=4*size || covered[x+step][yFill])
						return false;
		}
		else{
			for(int step=0;step<testSize;step++)
				for(int yFill=y+2*step;yFill<=y+2*(testSize-1);yFill++)
					if(x+step>=2*size || yFill>=4*size ||covered[x+step][yFill])
						return false;

		}
		return true;
	}
	private void Fill(int x,int y,int size,boolean value){
		if(y%2==0){
			for(int step=0;step<size;step++)
				for(int yFill=y;yFill<=y+2*step;yFill++)
					covered[x+step][yFill]=value;
		}
		else{
			for(int step=0;step<size;step++)
				for(int yFill=y+2*step;yFill<=y+2*(size-1);yFill++)
					covered[x+step][yFill]=value;
		}
	}
	public static void main(String[] args){
		int caseNum=in.nextInt();
		while(caseNum-->0){
			Main testCase=new Main();
			System.out.println(testCase.CanDivide()?"YES":"NO");
		}
	}
}

• ding... (18) 150014 2008-11-19 22:40:51
  • 换 G++ 写一遍就 AC 了……算法一模一样啊……为什么捏…… (2) 150014 2008-11-23 16:42:59
    • 再附代码，有人帮忙看么？ (3787) 150014 2008-11-23 16:43:28