链接:https://vjudge.net/contest/401586#problem/D
这道题显而易见仅与怎么进入nim游戏有关。
这种题跟转化基本博弈模型或是算sg函数没有关系,属于自己想种策略把自己说服。
如果n为奇数,后手进入nim游戏的时候成为先手,她希望nim和不等于0,我们站在她的角度思考必胜策略,不管先手一开始选了什么,我们总可以从剩余的选最大的放到先手第一次放的盘子里,这样第一个盘子被放了n/2+1次,肯定大于其余的石子,后手必胜。
如果n为偶数,先手进入nim游戏的时候成为先手,她希望nim和不等于0,我们站在她的角度思考必胜策略,每次都取剩下的包里最多的那个包放到一个盘子上。除非两两成对,否则这种策略一定保证最后nim和不等于0。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int a[maxn];
set<int> st;
map<int, int> mp;
int main()
{
int t;
cin >> t;
while(t--)
{
st.clear(); mp.clear();
int n; n = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
mp[a[i]]++;
st.insert(a[i]);
}
bool flag = 1;
for(auto it : st) {
if(mp[it] % 2) {
flag = 0;
break;
}
}
if(n & 1) {
printf("Second\n");
}
else {
if(flag){
printf("Second\n");
}
else {
printf("First\n");
}
}
}
}
京公网安备 11010502036488号