文章目录
题目思路代码
题目
思路
分为两个步骤 分背包 Nim博弈
首先奇数时候后手必胜 Nim先手必胜条件是异或和不为0 奇数也就是后手希望异或和不为0 那么先手选择放在
a
a
a 后，后手一直将当前最大的放在
a
a
a 就能保证
a
a
a >剩下所有之和 也就是
a
>
s
/
2
a>s/2
a>s/2，
a
a
a 独占最高位，必定不为0
偶数时候可以从奇数获得启发 那么先手希望异或和不为0 当没有一种数的个数为奇数时，显然后手可以模仿先手操作使得先手必败 当有一种数的个数为奇数时，先手选最大的就行了，
a
>
s
/
2
a>s/2
a>s/2
代码
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std
;
#define LL long long
int read(){
int f
=0,x
=0;char c
=getchar();
while(c
<'0'||'9'<c
){if(c
=='-')f
=1;c
=getchar();}
while('0'<=c
&&c
<='9') x
=(x
<<3)+(x
<<1)+(c
^48),c
=getchar();
return !f
?x
:-x
;
}
#define mp make_pair
const int MAXN
=200000;
const int INF
=0x3f3f3f3f;
int a
[MAXN
+5];
map
<int,int> Map
;
int main(){
int T
=read();
while(T
--){
int n
=read();
Map
.clear();
for(int i
=1;i
<=n
;i
++)
a
[i
]=read(),Map
[a
[i
]]++;
if(n
&1==1){
puts("Second");
continue;
}
for(map
<int,int>::iterator it
=Map
.begin();it
!=Map
.end();it
++)
if(it
->second
%2==1){
puts("First");
goto Break
;
}
puts("Second");
Break
:;
}
return 0;
}
