AT_arc116_f [ARC116F] Deque Game 题解

tags：博弈，贪心

差不多是双倍经验

感觉不算太难（）

先考虑只有一个数列的情况：

一、假设 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})$ 。

然后回到 $n$ 个序列的情况：假设其中存在一个长度为 $m$ 的序列，那么：

（1） $2\mid m$

若 Takahashi 是先手，则答案为 $\max(a_{\text{mid}},a_{\text{mid}+1})$ 。
若 Aoki 是先手，则答案为 $\min(a_{\text{mid}},a_{\text{mid}+1})$ 。

（2） $2\nmid m$

若 Takahashi 是先手，则答案为 $\max(\min(a_{\text{mid}-1,a_\text{mid}},\min(a_\text{mid},a_{\text{mid}+1})))$ 。
若 Aoki 是先手，则答案为 $\min(\max(a_{\text{mid}-1,a_\text{mid}},\max(a_\text{mid},a_{\text{mid}+1})))$ 。

对于第一种情况，不论哪一方先操作，一定都比后操作对自己更有利。

对于第二种情况，考虑经典套路，对所有 $a_{\text{mid}-1},a_\text{mid},a_{\text{mid}+1}$ 三个元素之间的偏序关系进行分类讨论，最终可以发现不论哪一方先操作，一定都比后操作对自己更不利。

然后又可以分析得出，若某个人操作了一个序列，那么另一方一定可以对称的操作序列，使得序列的关系不变。因此一个最优的策略是给所有的序列按照一定顺序排序，然后双方按顺序轮流对一个序列执行操作。

于是现在的问题在于，怎么快速的找出这个操作顺序。这一步是比较容易的。考虑经典套路，对每个长度为奇数的序列求出 Takahashi 作为先手选这个序列的代价和 Aoki 作为先手选这个序列的代价，然后将其作差，并按照贡献从大到小排序。因为 Takahashi 是先手，所以她一定会选择所有序列中对自己贡献最大的，然后 Aoki 会选择所有序列中对自己贡献第二大的，依次类推……而对于长度为偶数的序列，两个人操作完之后不会影响先后手的顺序，且这些序列作为先手一定给自己带来的贡献更大，因此 Takahashi 作为先手一定会把所有这些序列都先手操作掉。

于是这个题就做完了，总时间复杂度为 $O(n\log n)$ 瓶颈在于排序。将快排换为基数排序可以做到理论时间复杂度 $O(n)$ 。

vector<int> a[N];
inline int solve(vector<int> &a, int l, int r, int typ)
{
    if (l == r)
        return a[l];
    int mid = l + r >> 1;
    if (typ)
        return min(max(a[mid - 1], a[mid]), max(a[mid], a[mid + 1]));
    return max(min(a[mid - 1], a[mid]), min(a[mid], a[mid + 1]));
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int n, typ = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int m;
        cin >> m;
        for (int j = 0; j < m; ++j)
        {
            int x;
            cin >> x;
            a[i].emplace_back(x);
        }
        typ ^= (~m & 1);
    }
    vector<int> v;
    int all = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i].size() & 1)
            all += solve(a[i], 0, a[i].size() - 1, typ);
        else
        {
            int v1 = solve(a[i], 0, a[i].size() - 2, typ), v2 = solve(a[i], 1, a[i].size() - 1, typ);
            all += min(v1, v2);
            v.emplace_back(abs(v1 - v2));
        }
    }
    sort(v.begin(), v.end(), greater<int>());
    for (int i = 0; i < v.size(); i += 2)
        all += v[i];
    cout << all << '\n';
    return 0;
}

隐藏／恢复文章

随机文章