ARC#105D 题解

lightup37 · 2022-09-20 09:21:24 · 个人记录

ARC#105D

给定 n 堆石子，第 i 堆石子有 a_i 个。再给定 n 个盘子。A 和 B 在这些石子和盘子上玩游戏，A 先手 B 后手，一次操作是：

• 如果还有石子堆不在盘子上，选择任意一堆石子放在任意一个盘子上。
• 否则，从一个盘子上取走若干（但不能是 0）个石子。

问：先手是否有必胜策略。

解法

容易观察到应该对 n 的奇偶性分开讨论。

若 n 为偶数，则「放石子游戏」的先手也是「取石子游戏」游戏的先手。考虑 nim 游戏的必胜策略，容易发现若一堆石子的数量严格大于所有石子数量的一半，则先手必有必胜策略（这是因为要让异或和的每一位都是 0 则必然要有不少于那堆石子数量的石子）。那么先手如果每次取出数量最多的那堆石子放在 1 号盘中，则 1 号盘中的石子必然最多 —— 除非所有数量的石子出现次数均为偶数。而如果所有数量的石子出现次数均为偶数，则后手每次模仿先手的动作即可，最终状态下必然也有所有盘子中所有石子的数量的出现次数也为偶数。

若 n 为奇数，则「放石子游戏」的先手也是「取石子游戏」游戏的后手。那么先手必然先取出一堆石子放在某个盘子中，而此时后手只需要每次取最多数量最多的石子放在先手第一次放的盘子上，「放石子游戏」结束时，那个盘子上的石子数量必然严格大于所有石子数量的一半，也即「放石子游戏」的后手必有必胜策略。

#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
    int f=1, x=0; ch=getchar();
    while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 1000005
int T, n, a[_];
void solve() {
    map<int, int> M;
    rd(n); f(i,1,n) rd(a[i]), ++M[a[i]];
    int ok=1; f(i,1,n) ok&=(!(M[a[i]]&1));
    if(n&1) { puts("Second"); }
    else { puts(ok ? "Second" : "First"); }
}
int main() {
    rd(T); while(T--) solve();
    return 0;
}