嘘~ 正在从服务器偷取页面 . . .

[AGC002E] Candy Piles 题解

发布日期: 2024-06-25

更新日期: 2024-06-25

文章字数: 615

[AGC002E] Candy Piles 题解

题意：

桌上有 \(n\) 堆糖果，第 \(i\) 堆糖果有 \(a_i\) 个糖。

两人在玩游戏，轮流进行，每次进行下列两个操作中的一个:

将当前最大的那堆糖果全部吃完；

将每堆糖果吃掉一个；

吃完的人输，假设两人足够聪明，问谁有必胜策略？

输出 First（表示先手必胜）或 Second（表示后手必胜）

数据范围：

\(1\leq n\leq10^5,~1\leq a_i\leq10^9\)

考虑对这些石子堆降序排序，如下图所示

那么每次操作就变成了

于是原问题就转化成了在一个网格图上走路，每次可以选择向上或者向右走

如果可以一步走到边界，则胜利。如图所示

显然边界是必胜态 \(\rm N\) 。一个位置为必胜态 \(\rm N\) ，当且仅当上方或右方至少有一个为 \(\rm P\) ；否则必为 \(\rm P\) 。

如下图所示，其中 \(\color{red}{\large\unicode{x25CB}}\) 为 \(\rm N\) ， \(\color{blue}{\Large\unicode{x00D7}}\) 为 \(\rm P\) 。（这里 N,P 分别是 Next 和 Previous 的缩写）

注意到 \(1 \le a_i \le 10^9\) ，考虑找规律。

由于原点的状态决定了整个游戏先手必胜/必败，所以我们只需要求出如图7所示的最大正方形

然后判断它到上方的路径长度和到右方的路径长度，即可判断出原点是 \(\rm N\) 还是 \(\rm P\) 。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n, greater<int>());
    rep(i, 1, n) if(i + 1 > a[i + 1])
    {
        int j = 0; while(a[j + i + 1] == i) ++j;
        return cout << ((((a[i] - i) & 1) || (j & 1)) ? "First\n" : "Second\n"), 0;
    }
    return 0;
}