#B4227. [常州市程序设计小能手 2024] 游戏

[常州市程序设计小能手 2024] 游戏

题目背景

搬运自 http://czoj.com.cn/p/953。数据为民间数据。

题目描述

小 Y 和小 H 在玩游戏,由小 Y 开始,他们轮流操作一个长度为 2n2n 的正整数序列,一次删除这个序列中的一个数,直到最后剩下 22个数时停止。若小 H 进行某次操作后序列形成一个回文序列或者这个序列初始本身就是回文序列,则小H胜利,否则小 Y 胜利。

小 Y 和小 H 都是极其聪明的(即每一步操作都是对他们自身而言的最优操作),小 Y 想知道最后他可以获胜吗?

回文序列是指一个序列倒过来跟本身一样的序列,如 {17,23,23,17}\{17,23,23,17\} 是一个回文序列,而 {1,2,1,2}\{1,2,1,2\} 则不是回文序列。

输入格式

第一行为一个正整数 TT,表示共有 TT 组测试数据。

每组测试数据第一行为一个正整数 nn,第二行为 2n2n 个正整数表示这个序列。

输出格式

TT 行,每一行给出一个字符串表示对应测试数据的结果。

若小 Y 可以获胜,输出 Win\tt Win,否则输出 Lose\tt Lose注意首字母要大写!

2
3
1 1 2 2 1 1
2
1 1 2 2
Lose
Lose
1
2
1 1 2 3
Win

提示

样例 1\textbf 1 解释

对于第一组测试数据,这个序列本身就是回文序列。

对于第二组测试数据,无论小 Y 删除 11 还是 22,小 H 只要删除和小 Y 一样的数,最后就能剩下两个一样的数,形成回文序列。

样例 2\textbf 2 解释

小 Y 只要删除 11,小 H 无论删除哪个数,最后只能剩下两个不一样的数,无法形成回文序列。

数据范围

对于所有数据,1T5,1n1051\le T\le 5,1\le n≤10^5,序列中正整数的大小不超过 10510^5

测试点编号 特殊性质
131\sim3 α\alpha
454\sim 5 β\beta
6106\sim10
  • 特殊性质 α\alpha1n21\le n\le 2
  • 特殊性质 β\beta:保证序列中最多只有两种不同的数。