OR160. 小游戏
描述
有一天，小A和小B玩了一个神奇的游戏，游戏开始时，桌面上有a0个不同盒子和b0个不同的物品，每个回合，两个人可以选择增加一个新的盒子或者一个新的物品(所有物品和盒子都不同)，记当前桌子上的盒子数量为a，物品数量为b，当把b个物品放入a个盒子的方案数不小于n时，游戏结束，此时最后一位操作者判负。
给出a0，b0，n，如果小A先手，两个人都采用最优策略，谁能获胜，如果A获胜输出“A”，如果B获胜，输出“B”，如果是平局，输出“A&B”。
输入描述
输入第一行是一个数据组数T(T<=10)。
接下来T行，每行描述一个测试数据，包含三个整数a0,b0,n(1<=a0<=10000,1<=b0<=30,2<=n<=10^9)。分别表示桌子上初始的盒子数，球数和n值。
输出描述
对于每个测试数据，输出一行，仅包含一个字符串，即“A”，“B”或“A&B”。示例1
输入:
3 2 2 10 3 1 4 1 4 10
输出:
B A A&B
Java 解法, 执行用时: 8ms, 内存消耗: 9480KB, 提交时间: 2020-10-31
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
public class Main{
static int n;
//2代表平局,1代表谁先手谁赢，0代表谁后手谁赢
static HashMap<Integer,HashMap<Integer,Integer>> temp=new HashMap();
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
int a,b;
while(T-->0){
String[] str=br.readLine().split(" ");
a=Integer.parseInt(str[0]);
b=Integer.parseInt(str[1]);
n=Integer.parseInt(str[2]);
temp.clear();
int res=solution(a,b,1);
if(res==0)
System.out.println('A');
else if(res==1)
System.out.println('B');
else System.out.println("A&B");
}
}
//status:0,1,2
//返回0代表A获胜，1代表B获胜，2代表平局
public static int solution(int a,int b,int Bstart){
if(temp.containsKey(a)&&temp.get(a).containsKey(b)){
int rt=temp.get(a).get(b);
if(rt==2)
return 2;
return (rt==1)?Bstart:(1-Bstart);
}
if(a==1&&Math.pow(a+1,b)>=n){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,2);
return 2;
}
if(a==1){
int s1=solution(a+1,b,1-Bstart);
int s2=solution(a,b+1,1-Bstart);
if(s1==Bstart||s2==Bstart){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
if(s1==2||s2==2){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,2);
return 2;
}
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
double d1=Math.pow(a,b+1);
double d2=Math.pow(a+1,b);
if(d1>=n&&d2>=n){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
if(d2>=n){
int rs=solution(a,b+1,1-Bstart);
int kk=(rs==Bstart)?1:0;
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,kk);
return rs;
}
if(d1>=n){
int maxmum=(int)Math.pow(n,1.0/b);
if(Math.pow(maxmum,b)==n)
maxmum--;
int odd=(maxmum-a)&1;
int rs=(odd==1)?Bstart:1-Bstart;
int kk=(odd==1)?1:0;
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,kk);
return rs;
}
int s1=solution(a,b+1,1-Bstart);
if(s1==Bstart){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
int s2=solution(a+1,b,1-Bstart);
if(s2==Bstart) {
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
}
Java 解法, 执行用时: 9ms, 内存消耗: 9544KB, 提交时间: 2020-10-31
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
public class Main{
static int n;
//2代表平局,1代表谁先手谁赢，0代表谁后手谁赢
static HashMap<Integer,HashMap<Integer,Integer>> temp=new HashMap();
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
int a,b;
while(T-->0){
String[] str=br.readLine().split(" ");
a=Integer.parseInt(str[0]);
b=Integer.parseInt(str[1]);
n=Integer.parseInt(str[2]);
temp.clear();
int res=solution(a,b,1);
if(res==0)
System.out.println('A');
else if(res==1)
System.out.println('B');
else System.out.println("A&B");
}
}
//status:0,1,2
//返回0代表A获胜，1代表B获胜，2代表平局
public static int solution(int a,int b,int Bstart){
if(temp.containsKey(a)&&temp.get(a).containsKey(b)){
int rt=temp.get(a).get(b);
if(rt==2)
return 2;
return (rt==1)?Bstart:(1-Bstart);
}
if(a==1&&Math.pow(a+1,b)>=n){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,2);
return 2;
}
if(a==1){
int s1=solution(a+1,b,1-Bstart);
int s2=solution(a,b+1,1-Bstart);
if(s1==Bstart||s2==Bstart){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
if(s1==2||s2==2){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,2);
return 2;
}
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
double d1=Math.pow(a,b+1);
double d2=Math.pow(a+1,b);
if(d1>=n&&d2>=n){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
if(d2>=n){
int rs=solution(a,b+1,1-Bstart);
int kk=(rs==Bstart)?1:0;
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,kk);
return rs;
}
if(d1>=n){
int maxmum=(int)Math.pow(n,1.0/b);
if(Math.pow(maxmum,b)==n)
maxmum--;
int odd=(maxmum-a)&1;
int rs=(odd==1)?Bstart:1-Bstart;
int kk=(odd==1)?1:0;
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,kk);
return rs;
}
int s1=solution(a,b+1,1-Bstart);
if(s1==Bstart){
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
int s2=solution(a+1,b,1-Bstart);
if(s2==Bstart) {
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,1);
return Bstart;
}
if(!temp.containsKey(a)){
temp.put(a,new HashMap<Integer,Integer>());
}
temp.get(a).put(b,0);
return 1-Bstart;
}
}