Solution. CF1600E Array Game

Description

给定 $\{a_n\}$，Alice 和 Bob 正在构造一个新的序列，轮流从 $\{a_n\}$ 开头或末尾取出一个元素接在新序列的后面，需要保证这个新序列单调递增。

Solution

我们取出 $\{a_n\}$ 最长的单调递增前缀，记作 $\{p_{c_1}\}$，以及最长的单调递减后缀，记作 $\{q_{c_2}\}$。

将 $\{q_{c_2}\}$ 翻转后，我们可以将原问题转换为，每次从 $\{p_{c_1}\}$ 或 $\{q_{c_2}\}$ 的开头取出元素构造一个新的单调递增序列。

先给出结论，当 $c_1,c_2$ 至少一者为奇数时，Alice 必胜。

下证明这一结论。

1. 若 $c_1,c_2$ 均为奇数，不妨设 $p_1\ge q_1$。

   接下来，Alice 只需在第一步时取走 $p_1$，接下来 $\{q_{c_2}\}$ 中的元素将永远不能被选取，不难发现必然是 Alice 取走最后一个元素。

   此时 Alice 必胜。

2. 若 $c_1,c_2$ 其一为奇数，不妨设 $c_1$ 为奇，$c_2$ 为偶。

   Alice 第一步仍然取走 $p_1$，接下来 Bob 可能能够从 $\{p_{c_1}\}$ 或 $\{q_{c_2}\}$ 的开头选择元素，注意到 $p_1$ 已被取走，此时两序列长度均为偶数，Bob 取数过后，Alice 只需从 Bob 上一步所选择的序列开头取走元素即可，显然 Alice 这一步必然合法。

   Bob 每次取数后，Alice 必然能够进行下一步操作，那么无数可选的局面只能发生在 Bob 取数时，故最后一个元素也由 Alice 取走。

   此时 Alice 必胜。

3. 若 $c_1,c_2$ 均为偶数。

   Alice 第一步无论取走哪个元素，Bob 均可采用 $\mathrm{case\ 2}$ 中的必胜策略，于是 Bob 必胜。

   此时 Alice 必败。

Code

仅给出核心代码。

namespace Main{
    int n, a[N];
    void Main(){
        input(n);
        for(ri i = 0; i < n; i++) input(a[i]);
        int i = 0, j = n - 1;
        while(i < n && a[i] < a[i+1]) i++;
        while(j > 0 && a[j] < a[j-1]) j--;
        puts((i+1)&1 || (n-j)&1 ? "Alice" : "Bob");
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。