#PQJ1034x5024. QOJ 1034_5024
QOJ 1034_5024
标题: 【模板】双端队列 - Problem - QOJ.ac
#5024. 【模板】双端队列
The problem was used in the following contests:
给定 n 个非负整数 a1,a2,⋯,aN。
Magic 和 Spark 两个人进行博弈,两个人轮流操作,每次每个人可以从数组的最左边或者最右边拿走一个数,最后所有拿走的数的异或和更大的人获胜。
问两人都采取最优策略,谁会获胜。先手获胜输出 First,后手获胜输出 Second,平局输出 Draw。
输入格式
第一行一个正整数 T 表示数据组数。
接下来 T 组数据,
每组第一行一个整数 n,表示 a 的长度; 接下来一行 n 个整数 a1,a2,⋯,an,表示序列 a。
输出格式
对于每组数据,输出一行一个字符串表示答案。
样例数据
样例输入
3
2
3 3
2
3 5
3
4 4 4
样例输出
Draw
First
Second
子任务
对于 100% 的数据,1≤T≤40,1≤n≤5×104,0≤ai<231。
- Subtask #1(15 points):n≤15。
- Subtask #2(20 points):n≤103。
- Subtask #3(25 points):保证每个 ai 在 [0,231−1] 范围内均匀随机。
- Subtask #4(40 points):无特殊限制。