AT_arc105_d

分析

注意到本题在放完盘子之后就是一个简单的 Nim 问题，所以考虑每个背包会放到哪个盘子。由于放完盘后谁执先手与 \(n\) 的奇偶性有关，于是分类讨论。

如果 \(n\) 是奇数，放完后后手先取硬币，他肯定会尽量让异或和不为 \(0\)（Nim 的玩法），那么他有一个必胜策略：不管先手取哪个背包，他先取走剩余的背包里硬币最多的，然后放到先手放的盘子里，接下来每次取剩余的背包里硬币最多的，这样初始时先手放的背包必定至少比其它的盘子在二进制下多出一位（因为每次都有进位），所以异或和一定不是 \(0\)。综上，\(n\) 为奇数是后手必胜。

如果 \(n\) 是偶数，放完后先手先取硬币，那么后手肯定会尽量让异或和为 \(0\)，一种可行的策略是，先手干什么他就干什么，先手找了一个 \(a_i\) 个硬币的背包，他也找一个，先手把硬币放到了有 \(b_i\) 个的盘子里，后手也放到有 \(b_i\) 个的盘子里（\(b_i\) 可以为 \(0\)）。当然，这是建立在每个 \(a_i\) 都出现偶数次的情况，此时后手必胜。反之，如果存在 \(a_i\) 出现奇数次，那么先手就可以把那个出现奇数次的 \(a_i\) 放到当时 \(b_i\) 最大的盘子里，然后就会出现上一段提到的情况，这个盘子必定比其它盘子多出至少一位，则异或和必定不是 \(0\)，故先手必胜。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> mp;
int a[100010];
void solve()
{
	mp.clear();
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}
	if(n%2)
	{
		cout<<"Second"<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(mp[a[i]]%2)
		{
			cout<<"First"<<endl;
			return;
		}
	}
	cout<<"Second"<<endl; 
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}