Tag

博弈。

Description

给定 \(n\) 堆分别为 \(a_i\) 的物品，每一次可以取所有堆的物品一个或者取掉最大的一个物品。如果一个人把所有的物品都取完他就输了。

求出先手必胜还是后手必胜。

\(\texttt{data range:} n\leq 10^5, a_i\leq 10^9\).

Solution

将物品从大到小排序之后不难发现问题转化为了取一个网格图的第一行或者第一列，最终谁会后把物品取完。

这一步转化是比较不显然的，但是想清楚之后可以发现整个问题可以直接转化为一个网格图，求出从 \((0,0)\) 离开这个网格图的问题，这个网格图的边界就是将物品排序之后的一个轮廓（可以自己画图具体理解一下）。

到这里我们又陷入了瓶颈，你会发现到了边缘的时候存在两种情况：

第一种是直接走出去，这一种会导致当前操作的人输掉，所以只有走无可走的时候才选这条路。

第二种是沿着边缘走，但是注意不能往左边和下面走。

这个时候我们发现，如果走到了边缘，胜负就很容易求出。如果往上面有奇数个，那么说明此时操作的人必胜，往右边亦然。

这个时候需要大胆猜测一番，我们猜测当前点与右上角的点的博弈情况一定相同！

首先感性的认识，对于后手而言，如果右上角的点是后手必胜，那么后手一定可以转移到右上角的点。

但是直接证明具有一定难度，所以考虑反证法，假设 \(0\) 为必败，\(1\) 为必胜。

假设当前点为 \(0\)，右上角的点为 \(1\)，那么就有：

1 1
0 1

这种局面，我们对这个局面进行扩展。

0 1? 
1 1 1?
0 1 0

我们发现了矛盾，此刻这个右上角的点明显被两个 \(1\) 给包含了，所以你发现他扯淡了。

对于当前点为 \(1\)，右上角为 \(0\) 的情况。

初始一定有：

1 0
1 1

你看他直接扯淡了。

所以我们直接发现，当前点的状态与右上角点的状态一定一样。

对于原点直接往右上角跳到一个边缘点然后处理就可以了，时间复杂度为排序的 \(O(n \lg n)\)，用基数排序可以做到 \(O(n)\)。

const int N = 1e5 + 10;

int n;
int a[N];

inline void input() {
    n = rd;
    FOR(i, 1, n) a[i] = rd;
    return ;
}

inline void init() {
    sort(a + 1, a + 1 + n, greater<int>());
    return ;
}

inline void work() {
    for(int i = 1; i <= n; i++) 
        if(i + 1 > a[i + 1]) {
            int j = 0;
            for(; a[i + j + 1] == i; j++);
            if((j & 1) || (a[i] - i) & 1) puts("First");
            else puts("Second");
            break;
        }
    return ;
}

inline void solve() {
    input();
    init();
    work();
    return ;
}