CF1860C Game on Permutation

XYukari / 2023-08-31 / 原文

递推法解决博弈论问题。

博弈论问题基本思路是先确定“状态”，即先手必胜或者先手必败。这里定义“必胜/必败”为走到当前格子的人的结局（赛时因为搞混了走入的人和走出的人，导致浪费大量时间）。

不难发现，一个位置是“必胜”还是“必败”完全取决于它前面的位置——如果前面有（能合法走入的）“必胜位置”，则当前位置一定是“必败位置”；当前面全是“必败位置”的时候，当前位置才是“必胜位置”。利用动态规划，我们确定出每个位置是“必胜”还是“必败”。

这个动态规划是 \(O(n^2)\) 的，考虑怎样优化。判断前面是否全是“必败位置”的方法是记录一个前缀 \(\min\)，判断前面是否有能合法走入的“必胜位置”的方法是记录“必胜位置”的前缀 \(\min\)。

注意，Alice 放置棋子的行为相当于“走入”，所以她的 Lucky Elements 是“必胜位置”而不是“必败位置”。

下面是 AC 代码：

func main() {
    //积累 go 语言的快速输入输出方式
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    var t int
    fmt.Fscan(reader, &t)
    for ; t > 0; t-- {
        var n int
        fmt.Fscan(reader, &n)
        ans := 0
        mn := n + 1
        mnWin := n + 1
        for ; n > 0; n-- {
            var x int
            fmt.Fscan(reader, &x)
            if mn < x && x < mnWin {
                ans++
                mnWin = x
            }
            mn = min(mn, x)
        }
        fmt.Fprintln(writer, ans)
    }
}