当前位置:编程学习 > C/C++ >>

HDU 3389 Game (博弈)

  题意:
有n个盒子,从1到n排成一排,每个盒子里有一些卡片,每次一个玩家可以进行一个操作,从一个非空的盒子B中取出一些卡片放到盒子A中,A,B要满足 (A < B && (A + B) %2== 1 && (A+B)%3==0),不能操作的人输。
 
解题思路:
这题刚开始想没什么思路,无法将题目转换成常见的博弈问题,不过认真想想很容易发现 (A+B) = 6k + 3 (k >= 0),于是对于两个盒子A,B可行的转移也可以想出来, B%6 == 0的盒子可以转移到B%6 == 3的盒子里, B%6==1的盒子可以转移到B%6==2的盒子...最后发现这样子:
0 -> 3 -> 0 -> 3
2 -> 1 -> 2 -> 1
5 -> 4 -> 5 -> 4
最后的1, 3, 4盒子都是不能继续转移的盒子,找出这样子一个转移公式貌似还是不大好做。首先对于每一个转移公式都是互不影响的,对于第一个转移公式我们可以发现如果当前决策者处于不利形势,他想要挽回形式而移动
x%6==3的盒子到x%6==0的盒子是完全没用的,因为对手总是可以继续把你转移的盒子再转移回x%6==3的盒子里使得你还是处于同样的劣势,所以在这里影响结果的只有x%6==0的盒子,最终是要把x%6==0的盒子里的移动到3这个盒子里,问题似乎就转换成了普通的NIM取石子游戏。。。sg值就是和NIM游戏一样为盒子里的卡片数!对于其他两个转移公式同样如此!
 
 
/* ********************************************** 
Author      : JayYe 
Created Time: 2013-11-1 15:56:17 
File Name   : JayYe.cpp 
*********************************************** */  
  
#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;  
  
int main() {  
    int t, n, x, cas = 1;  
    scanf("%d", &t);  
    while(t--) {  
        scanf("%d", &n);  
        int ans = 0;  
        for(int i = 1;i <= n; i++) {  
            scanf("%d", &x);  
            if(i % 6 == 0 || i % 6 == 2 || i % 6 == 5) // 影响结果的只有取余6为0, 2, 5的盒子  
                ans ^= x;  
        }  
        printf("Case %d: ", cas++);  
        if(ans) puts("Alice");  
        else    puts("Bob");  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,