首页 > 搜索 > DFS搜索 > hdu 1581 Number Game-DFS-[解题报告]
2013
12-12

hdu 1581 Number Game-DFS-[解题报告]

Number Game

问题描述 :

Background

Christiane and Matthias are playing a new game, the Number Game. The rules of the Number Game are:

Christian and Matthias take turns in choosing integer numbers greater than or equal to 2. The following rules restrict the set of numbers which may be chosen:

R1 A number which has already been chosen by one of the players or a multiple of such a number cannot be chosen. (A number z is a multiple of a number y if z can be written as y * x and x is a positive integer.)

R2 A sum of two such multiples cannot be chosen either.

R3 For simplicity, a number which is greater than 20 cannot be chosen either. This enables a lot more NPCs (Non-Personal-Computers) to play this game.

The player who cannot choose any number anymore looses the Number Game.

Here is an example: Matthias starts by choosing 4. Then Christiane is not allowed to choose 4, 8, 12, etc. Let us assume her move is 3. Now, the numbers 3, 6, 9, etc. are excluded, too; furthermore, numbers like: 7 = 3 + 4, 10 = 2 * 3 + 4, 11 = 3 + 2 * 4, 13 = 3 * 3 + 4, . . . are not available. So, in fact, the only numbers left are 2 and 5. Matthias now says 2. Since 5 = 2 + 3 is now forbidden, too, he wins because there is no number for Christiane’s move left.

Your task is to write a program which will help to play the Number Game. In general, i.e., without rule R3, this game may go on forever. However, with rule R3, it is possible to write a program that finds a strategy to win the game.

Problem

Given a game situation (a list of numbers which are not yet forbidden), your program should output all winning moves. A winning move is a move by which the player whose turn it is can force a win no matter what the other player will do. Now we define these terms more formally:

A loosing position is a position in which either

1. all numbers are forbidden, or

2. no winning move exists.

A winning position is a position in which a winning move exists.

A winning move is a move after which the position is a loosing position.

输入:

The first line contains the number of scenarios.

The input for each scenario describes a game position. It begins with a line containing the number a, 0 <= a < 20 of numbers which are still available. Next follows a single line with the a numbers still available, separated by single blanks.

You may assume that all game positions in the input could really occur in the Number Game (for example, if 3 is not in the list of numbers available, 6 will not be, either).

输出:

The output for each scenario begins with a line containing "Scenario #i:" where i is the number of the scenario starting at 1. In the next line either print "There is no winning move." if this is true for the position of the current scenario, or "The winning moves are: w1 w2 . . . wk." where the wi are all the winning moves, in ascending order, separated by single blanks. The output for each scenario should be followed by a blank line.

样例输入:

2
1
2
2
2 3

样例输出:

Scenario #1:
The winning moves are: 2.

Scenario #2:
There is no winning move.

import java.io.*;
import java.util.*;
public class Main {
	public static boolean mark[];
	public static Integer a[];
	public static boolean boo;
	public static int edge,sum;
	public static int n,m;
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		PrintWriter pw=new PrintWriter( new BufferedOutputStream(System.out),true);
			n=sc.nextInt();
			for(int i=0;i<n;i++){
				
				m=sc.nextInt();
				
				boo=false;
				mark=new boolean[m];
				a=new Integer[m];
				sum=0;
				edge=0;
				for(int j=0;j<m;j++){
					a[j]=sc.nextInt();
					sum+=a[j];
				}
				Arrays.sort(a,new Comparator<Integer>(){//排序
					public int compare(Integer o1, Integer o2) {
						return o1>o2?-1:1;//按降序排序
					}
					
				});
				edge=sum>>2;//右一位除以2
				if(sum%4==0&&edge>=a[0]){
					DFS(0,0,0);
					if(boo)
						pw.println("yes");
					else
						pw.println("no");
				}else{
					pw.println("no");
				}
		}
			
	}
	// 第一个变量是有几条边,第二个变量是每次循环边长的大小, 第三个变量是第几个元素
	public static void DFS(int length,int size,int index){
		//如果为真就返回
		if(boo)
			return;
		//等于四条边就退出循环
		if(length==4){
			boo=true;
		}
		if(size==edge){
			DFS(length+1,0,length+1);
		}
		else{
			for(int i=index;i<m;i++){
				if(!mark[i]&&size+a[i]<=edge){
					mark[i]=true;
					DFS(length,size+a[i],i+1);
					mark[i]=false;//回溯
				}
			}
		}
	}
}
import java.io.*;
import java.util.*;
public class Main {
	public static int n,m,sum,edge;
	public static boolean mark[];
	public static int a[];
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		PrintWriter pw=new PrintWriter(new BufferedOutputStream(System.out),true);
		n=sc.nextInt();
		for(int i=0;i<n;i++){
			m=sc.nextInt();
			mark=new boolean[m];
			a=new int[m];
			sum=0;
			for(int j=0;j<m;j++){
				a[j]=sc.nextInt();
				sum+=a[j];
			}
			edge=sum>>2;//右移一位除以2
			Arrays.sort(a);//排序
			if(sum%4==0&&edge>=a[a.length-1]){//边长要大于等于数组里里面的元素的最大值
				if(DFS(0,0,0))
					pw.println("yes");
				else
					pw.println("no");
			}else
				pw.println("no");
		}
	}
	// 第一个变量是有几条边,第二个变量是每次循环边长的大小, 第三个变量是第几个元素
	public static boolean DFS(int length,int size,int index){
		//等于四条边的就退出循环
		if(length==4)
			return true;
		if(size==edge){
			if(DFS(length+1,0,length+1))
				return true;
			else
				return false;
		}
		else{
			for(int i=index;i<m;i++){
				if(!mark[i]&&size+a[i]<=edge){
					mark[i]=true;
					if(DFS(length,size+a[i],i+1))
						return true;
					mark[i]=false;
				}
			}
		}
		return false;
	}
}

解题转自:http://blog.csdn.net/deng_hui_long/article/details/9939175


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.