6

爱丽丝和鲍勃玩以下游戏：

1）他们选择前 N 个数字的排列开始。

2) 他们轮流玩，爱丽丝先玩。

3）在一个回合中，他们可以从排列中删除任何一个剩余的数字。

4) 当剩余的数字形成一个递增的序列时，游戏结束。玩最后一回合的人（之后序列会增加）赢得游戏。

假设双方都发挥最佳，谁会赢得比赛？

输入：第一行包含测试用例 T 的数量。接下来是 T 测试用例。每个案例在第一行包含一个整数 N，然后在第二行包含整数 1..N 的排列。

输出：输出 T 行，每个测试用例一个，如果 Alice 获胜则包含“Alice”，否则包含“Bob”。

样本输入：

2

3

1 3 2

5

5 3 2 1 4

样本输出：

爱丽丝

鲍勃

约束：

1 <= T <= 100

2 <= N <= 15

排列最初不会是递增序列。

我正在尝试解决上述问题。我已经推导出来，但我被困在一个点上。请帮助我进一步进行。

在上述问题中，对于长度为 2 的排列，玩家 1 总是获胜。

对于长度为 3 的排列，如果字符串严格增加或减少，则玩家 2 获胜。

对于长度为 4 的排列，如果玩家 1 能够通过删除一个字符使字符串严格增加或减少，则她获胜，否则玩家 2 获胜。

因此得出的结论是：

如果当前玩家能够使字符串严格增加他/她获胜。（小案例）

如果他/她能够使其严格递减，则获胜者将由该序列中的元素数量决定。如果该序列中有偶数个元素，则当前玩家输，否则获胜。

但是如果结果字符串既不增加也不减少怎么办？

4

8 回答 8

9

这是一个典型的游戏问题。您有 2^15 个可能的位置，表示剩余的数字。从剩余数字的数量中，您可以得出轮到谁了。所以现在你有一个以下列方式定义的图 - 顶点是剩余数字的可能集合，并且有一条边连接两个顶点 u 和 v 如果有一个移动将集合 u 更改为集合 v（即集合 v正好少一个数）。

现在你已经指出了哪些位置你知道谁是赢家 - 那些代表数字序列增加的位置被标记为失败。对于所有其他位置，您可以通过以下方式确定它们是赢还是输：如果有一条边连接到亏损位置，则该位置是赢的。所以剩下的就是像带有记忆的dfs这样的东西，你可以确定哪些位置是赢的，哪些是输的。由于图形相对较小（2^15 个顶点），该解决方案应该足够快。

希望这可以帮助。

于 2012-04-02T10:06:45.677 回答
4

当然，这可以通过对小 N 的“蛮力”来完成，但是您不怀疑关于反转和排列符号的更简单的答案吗？

最初我怀疑像“如果符号为-1，爱丽丝赢，否则输”这样的答案，但事实并非如此。

但我想提出一个问题的表示，不仅你的算法可以使用，而且同样可以提高你在这个游戏中的纸笔性能。

反转是一对索引 i<j 使得 a[i]>a[j]。考虑 ( i, j) 一个顶点为 1,...,N 的无向图的边。每个玩家从该图中删除一个顶点，如果没有剩余边则获胜。

对于5 3 2 1 4，结果图是

   5--3
  /|\ |
 / | \|
4  1--2

Alice 很快发现删除“5”给了 Bob 删除 2 的机会。然后没有剩下任何反转，Bob 获胜。

于 2012-04-02T11:15:28.030 回答
2

这个游戏可以递归解决。

每次爱丽丝第一次选择并选择 i 时，从所有大于 i 的剩余数字中减去 1。现在我们有同样的游戏，但数字是 1 到 N-1

假设你的序列是

1,3,5,4,2

在她的第一步，爱丽丝可以选择任何数字。案例1：她选择1，如果鲍勃不能用3,5,4,2获胜（相当于2,4,3,1），爱丽丝可以获胜

案例2：她先选了3。如果 bob 不能以 1,5,4,2 获胜（相当于 1,4,3,2），则 Alice 可以获胜

案例3：她先选了5。如果鲍勃不能用 1,3,4,2 赢，爱丽丝可以赢

你明白了。

因此，您可以通过对每个可能的第一次猜测使用大小为 N-1 的排列来创建一个递归函数来计算大小为 N 的排列的解决方案。递归的基本情况是当您有一个有序序列时。

递归的每一步，这个人都会尝试所有的可能性，并选择任何让他们获胜的可能性。

因为有许多移动组合可以归结为相同的序列，所以递归存在重叠子问题。这意味着我们可以使用动态编程，或者简单地“记忆”我们的函数，从而大大提高效率。

为了进一步加快速度，可以在排列中使用对称性，因为许多排列组是等价的，例如一个排列的反转将产生相同的结果。

祝你好运。

于 2012-04-02T10:15:33.640 回答
1

@tiwo ,@rup 考虑到 5 3 2 1 4 是序列首先 alice 删除 5 并且 bob 删除 2 然后序列是 3 1 4 不是递增顺序然后 alice 有机会删除 1 并且序列在升序爱丽丝应该是答案。在您给出的图表中，应该在 3 和 1 之间有一条边，因为 1 和 3 处于反转状态。

请告诉我我错在哪里，因为问题中给出的答案实际上是 BOB

于 2012-09-26T12:58:36.457 回答
1

你可以用极小极大算法来解决它。这是java中的代码

import java.io.*;  
import java.util.*;  
import java.text.*;  
import java.math.*;  
import java.util.regex.*;  

public class Solution {  

    public static Scanner sc = new Scanner(System.in);  
    public static void main(String[] args) {  
        int t = ni();  
        for(int i=0; i<t; i++){  
            int n = ni();  
            Map<Long, Boolean> map = new HashMap<Long, Boolean>();  
            int[] numbers = new int[n];  
            for(int j=0; j<n; j++){  
                numbers[j] = ni();  
            }  
            if(aliceWin(numbers, map)) System.out.println("Alice");  
            else System.out.println("Bob");  
        }  
    }  

    public static boolean aliceWin(int[] a, Map<Long, Boolean> map){  
        long h = hashCode(a); int temp;   
        if(map.containsKey(h)) return true;  

        for(int i=0; i<a.length; i++){  
            if(a[i]>0){  
                temp = a[i] ;  
                a[i] = 0;  
                if(isIncreasing(a)){  
                    map.put(h, true);  
                    a[i] = temp;  
                    return true;  
                }  
                if(!aliceWin(a, map)) {  
                    map.put(h, true);  
                    a[i] = temp;  
                    return true;  
                }  
                a[i] = temp;  
            }  
        }  
        return false;  
    }  

    public static long hashCode(int[] a){  
        long result = 0;  
        for(int i=0; i<a.length; i++){  
            result = (result << 4) + a[i];  
        }  
        return result;  
    }  
    public static boolean isIncreasing(int[] a){  
        int last = 0;  
        for(int i=0; i<a.length; i++){  
            if (a[i] > 0){  
                if(last > a[i]) return false;  
                last = a[i];  
            }  
        }  
        return true;  
    }  
    public static int ni(){  
        return sc.nextInt();  
    }  

    public static void print(Object... args){          
        System.out.println(Arrays.deepToString(args));  
    }  
}

来自博客：hackerrank-permutation-game

于 2015-12-09T19:44:53.603 回答
0

这是一些为您构建图表的代码，但需要您在图表上调用 reverse()，创建一个连接到基础中所有节点的源节点，返回源查看是否有一种方式 alice 获胜。

input_ = """2

3

1 3 2

5

5 3 2 1 4""".splitlines()

perms = [map(int,perm.split()) for perm in input_ if len(perm)>1]
"[['1', '3', '2'], ['5', '3', '2', '1', '4']]"

if networkx is None:
    import networkx
from itertools import combinations

def build_graph(perm):
    base = set()
    G = networkx.DiGraph()
    for r in range(1,len(perm)+1):
        for combo in combinations(perm,r):
            combo = list(combo)
            if combo == sorted(combo):
                base.add(tuple(combo))
                continue
            for i in range(r):
                G.add_edge(tuple(combo),tuple(combo[:i]+combo[i+1:])) #you may want to reverse the graph later to point from base to source.
    return G,base


def solve(G,base):
    #dfs,
    pass

for perm in perms:
    G,base = build_graph(perms[0])
    print solve(G,base)
于 2012-04-02T10:50:01.057 回答
-1

我们不能在每一步都检查..下一个玩家是否进行了一次更改使序列排序..如果是，则进行其他操作..或继续移动

就像 5 3 2 1 4 如果爱丽丝做了 3 2 1 4 鲍勃不能通过消除任何一个来赢得单回合......就像如果他做了 2 1 4 它没有排序.. 他做了 3 1 4 它没有排序..他做了 3 2 4 它没有排序.. 所以 5 3 2 1 4 -> 3 2 1 4 是一个有效的举动！

现在轮到鲍勃了..他会检查同样的..但在一段时间内..不会有一个数字可以让你像上面那样移动..所以你必须随机移动，谁将获胜然后可以通过将序列变为单个元素的步数轻松计算！

于 2012-08-23T06:35:15.507 回答
-2

对我来说（几乎用你自己的话）：

如果他/她能够在第一步中严格增加他/她获胜（平凡的情况），否则获胜者将由该序列中的元素数量决定。

以你的第二种情况为例。

我认为图形解决方案很好，但它忘记了玩家以最佳方式玩。所以不需要检查所有不同的路径，因为其中一些将来自非最佳选择。

于 2012-04-02T10:25:36.303 回答