P11133【MX-X5-T5】「GFOI Round 1」World Ender 题解

· · 题解

前置知识

找规律

根据标准的博弈论思想，我们可以记录每一个状态下，先手有没有必胜策略。如果能转移到一个先手必败的状态，那么有先手必胜策略；反之亦然。

可以发现每一次操作碎片至少减少一块，所以不可能出现循环，状态转移是比较明确的。

然后开始手推不同的状态。我们用 n 来表示剩余几堆。

n = 1 时：

很显然，先手必胜，全部丢弃即可。

n = 2 时：

根据博弈论的基本原理，可以得到如果先手率先把其中的一堆丢光，那么只剩下一堆了，会导致后手获胜，先手必败。

当两堆个数分别为 i,j (i \leq j) 的情况。首先给出结论：i = j，则先手败；i \neq j，则先手胜。

证明：运用归纳法。

证明完毕。

n = 3 时：

结论：先手必胜。

因为，可以把碎片数量最大的一堆给选出来，用它的碎片把数量最小的一堆给补到与另外一堆数量相等，然后把剩下的碎片全部丢弃。就转移到了两堆的先手必败情况，所以 n = 3 时先手必胜。

n 为偶数时：

可以通过总结规律得到判断方法：

  1. 设每一堆碎片的数量组成长度为 n 的数组 a_{1,2,\dots,n}。
  2. 将 a 从小到大排序。
  3. 如果存在 i 使得 a_{2i-1} < a_{2i}，那么先手必胜。反之先手必败。

证明类似于 n = 2 的情况，只是复杂一些，略。

n 为奇数时：

与 n = 3 的情况类似，先手必胜。

证明类似。

实现

当你发现了上述规律，并且能够说明为什么了的时候，你就差不多解决了这道题了。

Init

根据上述规律排序并判断即可。

Get

记录上一步的数组，我的实现中 GET 函数几乎什么都没做。

Play

这是重点！！！分成两种情况：

这样就转移成了必败状态。

代码


#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
struct point {
    int id,val;
    bool operator < (const point b) const {
        return val < b.val;
    }
};
vector <point> v;
vector <int> Play(void) {
    int n = v.size();
    sort (v.begin(),v.end());
    if (n&1) {
        vector <int> res(n);
        for (int i = 0;i < n-1;i += 2) {
            res[v[i].id] = v[i+1].val;
            res[v[i+1].id] = v[i+1].val;
        }
        return res;
    }
    vector <int> res(n);
    vector <point> v2(0);
    for (int i = 0;i < n;i++) {
        if (i < n-1 && v[i].val == v[i+1].val) {
            res[v[i].id] = v[i].val;
            res[v[i+1].id] = v[i+1].val;
            i++;
            continue;
        }
        else v2.push_back(v[i]);
    }
    if (v2.size()) {
        assert (v2.size()>1);
        for (int i = 1;i < v2.size()-1;i += 2)
            res[v2[i].id] =  res[v2[i+1].id] = v2[i+1].val;
        res[v2[0].id] = v2[0].val;
        res[v2[v2.size()-1].id] = v2[0].val;
    }
    fflush(stdout);
    return res;
}
void Get(vector<int> a) {
    v.clear();
    for (int i = 0;i < a.size();i++)
        v.push_back((point){i,a[i]});
    return;
}
bool Init(int n, int op,vector<int> a) {
    v.clear();
    for (int i = 0;i < a.size();i++)
        v.push_back((point){i,a[i]});
    if (a.size()&1) return false;
    sort (a.begin(),a.end());
    for (int j = 0;j < a.size()-1;j += 2)
        if (a[j] != a[j+1]) return false;
    return true;
}

注意不要用 C++14（GCC 9）。轻松 AC。