CF794E Choosing Carrot 题解

tags：博弈，贪心

差不多是双倍经验

感觉不算太难（）

note：

#define Takahashi 奶牛A
#define Aoki 奶牛B
#define 石子 草

（其实是复制过来的然后懒得改了）

一、假设 Takahashi 是先手

假设当前只有一个长度为 $n$ 的序列 $a$，则先考虑这样的一个策略：假设先手取走了序列某一侧的元素，则后手一定可以取走对侧的元素，这样可以将最后剩余的唯一元素局限在序列的中部。

对 $n$ 的奇偶性分类讨论：

（1）$2\nmid n$

先模拟 $n$ 比较小的情况。$n=1$ 时答案显然。$n=3$ 时：

• 若此时先手取走了最左侧的 $a_1$，那么此时后手可以选择取走 $a_2$ 或 $a_3$ 中的某个元素。在最优策略下，最终数列剩下的元素显然是 $\min(a_2,a_3)$。
• 若此时先手取走了最右侧的 $a_2$，那么此时后手可以选择取走 $a_1$ 或 $a_2$ 中的某个元素。在最优策略下，最终序列剩下的元素显然是 $\min(a_1,a_2)$。

而此时先手也会选择最优策略最大化答案，因此显然此时答案为 $\max(\min(a_1,a_2),\min(a_2,a_3))$。

扩展到 $n=2k+1$ 的情况：假设此时先手取走了最左边的石子，那么：

• 后手取最右边的石子。那么规约到 $n=2k-1$ 的情况递归处理。
• 后手取最左边的石子。激情的左右脑博弈之后可以发现此时有两种情况：
  • 先手继续取最左边的石子。那么此时情况比较偏离轨道，但是倒推一下，若后手取最左边的石子比取最右边的石子更优，那么此时其肯定是希望先手取最左侧的石子以达到其目标的。而若先手取了最左侧的式子就正好符合了后手的心意。
  • 先手取右边的石子，回到情况开始。因此此时情况形如：后手一直取左边石子，先手一直取右边石子，局面保持平衡，直到某一时刻后手取左边石子不优，打破局面取右侧石子，此时又规约到了 $n=2k+1-2p$ 时的情况。

先手第一步取右侧的石子也同理。因此最终都规约到了 $n=3$ 的情况。这堆石子的最优解即形如：找出石子的中位编号 $\text{mid}$，最终的答案即为 $\max(\min(a_{\text{mid}-1},a_{\text{mid}},\min(a_{\text{mid}},a_{\text{mid}+1})))$。

（2）$2\mid n$

同样还是模拟 $n$ 比较小的情况。$n=2$ 时先手可以直接决定最后保留的石子，答案为 $\max(a_1,a_2)$。

扩展到 $n=2k$ 的情况：假设此时先手取走了最左边的石子，那么：

• 后手取最右边的石子。那么规约到 $n=2k-2$ 的情况递归处理。
• 后手取最左边的石子。激情的左右脑博弈之后可以发现此时有两种情况：
  • 先手继续取最左边的石子。那么此时情况比较偏离轨道，但是倒推一下，若后手取最左边的石子比取最右边的石子更优，那么此时其肯定是希望先手取最左侧的石子以达到其目标的。而若先手取了最左侧的式子就正好符合了后手的心意。
  • 先手取右边的石子，回到情况开始。因此此时情况形如：后手一直取左边石子，先手一直取右边石子，局面保持平衡，直到某一时刻后手取左边石子不优，打破局面取右侧石子，此时又规约到了 $n=2k-2p$ 时的情况。

先手第一步取右侧的石子也同理。因此最终都规约到了 $n=2$ 的情况。这堆石子的最优解即形如：找出石子的中位编号中相对较小的编号 $\text{mid}$，最终的答案即为 $\max(a_\text{mid},a_\text{mid+1})$。

二、假设 Aoki 是先手

好吧其实和之前的没啥差别（）

（1）$2\nmid n$

$n=1$ 时答案为 $a_1$，$n=3$ 时答案为 $\min(\max(a_1,a_2),\max(a_2,a_3))$，扩展到 $n=2k+1$ 的情况：设中位数编号为 $\text{mid}$，则答案即为 $\min(\max(a_{\text{mid}-1},a_\text{mid}),\max(a_\text{mid},a_{\text{mid}+1}))$。

（2）$2\mid n$

$n=2$ 时答案为 $\min(a_1,a_2)$，扩展到 $n=2k$ 的情况：设中位数编号相对较小的编号 $\text{mid}$，则答案即为 $\min(a_\text{mid},a_{\text{mid}+1})$。

然后问题在于此时 Takahashi 可以先执行 $k$ 次操作。

此时容易计算出 $k=0$ 和 $k=1$ 时的答案，而若 $k=p$（$p\ge 2$），则可以规约到 $k=p-2$ 时的情况，然后在此基础上：

• 取一次左侧和一次右侧，那么和 $k=p-2$ 的情况完全相同。
• 取两次左侧，那么此时相当于是 $k=p-2$ 的基础上整体向左平移，答案可以再往左取一个位置。
• 取两次右侧，那么此时相当于是 $k=p-2$ 的基础上整体向右平移，答案可以再往右取一个位置。

容易发现上面这个东西可以做到 $O(n)$ 递推转移，注意需要特判 $k=n-1$，此时答案即为 $\max\limits_{i=1}^n a_i$。

int res[N], a[N];
 
signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    a[0] = a[n + 1] = inf;
    int mid = n + 1 >> 1;
    if (n & 1)
    {
        res[0] = max(min(a[mid - 1], a[mid]), min(a[mid], a[mid + 1]));
        res[1] = max({a[mid - 1], a[mid], a[mid + 1]});
        for (int i = 2; i <= n - 2; ++i)
            if (i & 1)
                res[i] = max({res[i - 2], a[i / 2 + 1 + mid], a[mid - i / 2 - 1]});
            else
                res[i] = max({res[i - 2], min(a[i / 2 + mid], a[i / 2 + 1 + mid]), min(a[mid - i / 2], a[mid - i / 2 - 1])});
        res[n - 1] = *max_element(a + 1, a + n + 1);
    }
    else
    {
        res[0] = max(a[mid], a[mid + 1]);
        res[1] = max({min(a[mid - 1], a[mid]), min(a[mid], a[mid + 1]), min(a[mid + 1], a[mid + 2])});
        for (int i = 2; i <= n - 2; ++i)
            if (i & 1)
                res[i] = max({res[i - 2], min(a[mid + i / 2 + 1], a[mid + i / 2 + 2]), min(a[mid - i / 2], a[mid - i / 2 - 1])});
            else
                res[i] = max({res[i - 2], a[mid + i / 2 + 1], a[mid - i / 2]});
        res[n - 1] = *max_element(a + 1, a + n + 1);
    }
    for (int i = 0; i < n; ++i)
        cout << res[i] << ' ';
    cout << '\n';
    return 0;
}