Log*_*est 6 algorithm math game-theory
Alice和Bob玩下面的游戏:
1)他们选择开头的前N个数字的排列.
2)他们交替上场,爱丽丝先上场.
3)在一个回合中,他们可以从排列中删除任何一个剩余的数字.
4)当剩余数字形成递增序列时,游戏结束.最后一个回合(在序列变得增加之后)的人赢得比赛.
假设两者都发挥得最好,谁赢了比赛？
输入:第一行包含测试用例数T.T测试用例如下.每个案例在第一行包含一个整数N,然后在第二行包含整数1..N的排列.
输出:输出T行,每个测试用例一行,如果Alice赢了游戏则包含"Alice",否则包含"Bob".
样本输入:
2
3
1 3 2
五
5 3 2 1 4
样本输出:
爱丽丝
短发
约束:
1 <= T <= 100
2 <= N <= 15
排列最初不会是增加的顺序.
我想解决上面的问题.我已经衍生到很远,但我陷入了困境.请帮我继续.
在上述问题中,对于长度为2的排列,玩家1总是获胜.
对于长度为3的置换,如果字符串严格增加或减少,则播放器2获胜.
对于长度为4的排列,如果玩家1能够通过移除角色使弦完全增加或减少,则她赢得其他玩家2胜.
因此得出的结论是:
如果当前玩家能够使字符串严格增加他/她获胜.(琐碎案例)
如果他/她能够使其严格减少,则获胜者由该序列中的元素数量决定.如果该序列中有偶数个元素,则当前玩家会失败,否则获胜.
但是,如果结果字符串既不增加也不减少,应该怎么办？
这是一个典型的游戏问题.您有2 ^ 15个可能的位置,表示剩余的数字.根据剩余数字的数量,你可以得出轮到它的数量.所以现在你有一个以下面的方式定义的图形 - 顶点是剩余数字的可能集合,并且有一条边连接两个顶点u和v iff有一个移动改变set u to set v(即set v只有一个数字).
现在你已经指出了哪些位置你知道谁是胜利者 - 那些代表不断增加的数字序列的位置被标记为失去.对于所有其他位置,您可以通过以下方式确定它们是否正在获胜或失去:如果有一个边缘将其连接到松动位置,则获胜.所以剩下的就是像带有记忆的dfs那样你可以确定哪些位置正在赢,哪些位置正在消失.由于图形相对较小(2 ^ 15个顶点),因此该解决方案应该足够快.
希望这可以帮助.
当然，这可以通过小 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 获胜。