#1683. 【模板】双端队列

    ID: 1683 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1034来源:qoj.ac数据:公开样例动态规划

【模板】双端队列

【模板】双端队列

题目描述

标题: 【模板】双端队列 - Problem - QOJ.ac

#5024. 【模板】双端队列

Statistics

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):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2
3 3
2
3 5
3
4 4 4
Draw
First
Second