欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

阶梯尼姆博弈

程序员文章站 2022-06-29 21:16:00
...

Georgia and Bob

 POJ - 1704 

阶梯尼姆博弈

阶梯尼姆博弈

 运行超时代码:

import java.util.Arrays;
import java.util.Scanner;
//时间超时
public class Main {
	public static int n;
	public static int a[][];

	public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		n = sca.nextInt();
		a = new int[n][];
		
		for(int i = 0; i < n; i ++) {		
			int ns = sca.nextInt();
			a[i] = new int[ns];
			for(int j = 0; j < ns; j ++) {
				a[i][j] = sca.nextInt();
			}
			
			Arrays.sort(a[i]);
			
		}
		Nim();

	}

	private static void Nim() {
		for(int i = 0; i < n; i ++) {
			int res = 0;
			int ns = a[i].length;
			//Nim博弈
			if(ns % 2 == 0) {
				for(int j = 1; j < n; j = j + 2) {
					res ^= a[i][j] - a[i][j - 1] - 1;
				}
			}
			else {
				res ^= a[i][0] - 1;
				for(int j = 2; j < n; j = j + 2) {
					res ^= a[i][j] - a[i][j - 1] - 1;
				}
			}
			
			if(res == 0) {
				System.out.println("Bob will win");
			}
			else {
				System.out.println("Georgia will win");
			}
		}
		
	}
	


}

运行通过:

import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int caseNum = sc.nextInt();
		int a[][] = new int [caseNum][];
		for(int i = 0; i < caseNum; i++){
			int n = sc.nextInt();
			a[i] = new int[n];
			for(int j = 0; j < n; j++){
				a[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < caseNum; i++){
			solve(a[i]);
		}
	}
 
	private static void solve(int[] a) {
		Arrays.sort(a);
		int len = a.length;
		int res = 0;
		if((len & 1) == 1){
			for(int i = 0; i < len; i += 2){
				res ^= (i == 0) ? (a[i] - 1) : a[i] - a[i - 1] - 1;
			}
		}else{
			for(int i = 1; i < len; i += 2){
				res ^= a[i] - a[i - 1] - 1;
			}
		}
		if(res == 0){
			System.out.println("Bob will win");
		}else{
			System.out.println("Georgia will win");
		}
	}
}