1.Candy Piles

题意

桌子上有 $N$ 堆糖果。每堆糖果有 $a_i$ 颗糖果。

Snuke 和 Ciel 正在玩游戏。他们轮流走。Snuke 先走。在每个回合中，当前玩家必须执行以下两个操作之一：

• 选择剩余糖果数量最多的一堆，然后吃掉那堆糖果中的所有糖果。
• 从仍有糖果剩余的每堆中吃一颗糖果。

吃了桌上最后一块糖的玩家输掉了比赛。确定如果两个玩家都以最佳方式玩游戏，哪个玩家会赢。

$1\le N\le 10^5$，$a_i\in [1,10^9]$。

思路

先对所有 $a_i$ 从大到小排序，操作 $1$ 相当于把最左边的移除，操作 $2$ 相当于对所有 $a_i\leftarrow a_i-1$。我们把它们抽象成柱状图：

我们找到 $a_i\ge i$ 的最大 $i$，这是二人轮流做操作 $1,2$ 后，此时轮到 Snuke 决策，剩下上有 $a_i-i$ 格，右边有 $right$ 格。这二者有一个是奇数，Snuke 就赢了：设 $a_i-i$ 是奇数（如上图），Snuke 做一个操作 $2$，这时最后一步必然是 Ciel 来做；$right$ 是奇数，Snuke 就先做一次操作 $1$。

其余情况就是 Ciel 赢。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9;
ll Q,n,a[N];
bool cmp(ll x,ll y)
{
	return x>y;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(i+1>a[i+1])//(0,0)-(i,i) 
		{//先手是Snuke 
			ll right=0;
			while(a[right+i+1]==a[i])right++;
			if(right%2==1||(a[i]-i)%2==1)puts("First");
			else puts("Second");
			break;
		}
	}
	return 0;
}

2.Remove and Decrease Game

题意

给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个，保证 $a_i$ 互不相同。

Alice 和 Bob 轮流执行以下两种操作中的一种，并在操作后移除石子数为 $0$ 的石子堆。Alice 先手，不能执行操作的人判负。

• 对于每堆石子均取走一个石子。
• 移除石子数量最小的一堆石子。

在两人均采取最优策略的情况下，问谁可以获胜。你需要回答 $T$ 次询问。

$1\le T\le 2\times 10^5$，$1\le n\le 2\times 10^5$，$\sum n\le 2\times 10^5$，$a_i\in [1,10^9]$，$a_i$ 互不相同。

思路

和上一题刚好反过来。考虑从小到大排序。仿照上一题的消减，找到最后一个 $a_i=i$ 的 $i$，但是依然很有区别，主要取决于那个最后一个 $i$。我的实现参考了这个思路。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9;
ll Q,n,a[N];
int main()
{
	scanf("%lld",&Q);
	while(Q--)
	{
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
		if(n==1)
		{
			puts("Alice");
			continue;
		}
		sort(a+1,a+n+1);
		ll cur=0;
		for(int i=1;i<=n-2;i++)
		{
			if(a[i]!=i)break;
			cur=i;
		}
		//剩下n-1,n两堆
		if(cur&1)
		{
			puts("Alice");
			continue;
		}
		if((a[n-1]-(n-1))%2==1)puts("Alice");//第一堆奇偶性 
		else puts("Bob");
	}
	return 0;
}