阶梯尼姆博弈
程序员文章站
2022-06-29 21:16:00
...
Georgia and Bob
运行超时代码:
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");
}
}
}
下一篇: JQuery实现图片轮播效果