A16674 | Souvlaki VS. Kalamaki
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
有两位玩家，Souvlaki 和 Kalamaki，得到了一个长度为 $n$ 的整数序列 $a$。
他们将玩一个包含 $n-1$ 轮的游戏，轮次编号从 $1$ 到 $n-1$。Souvlaki 在奇数轮出手，Kalamaki 在偶数轮出手。
在第 $i$ 轮，当前玩家可以选择以下两种操作之一：
- 跳过本回合，进入第 $i+1$ 轮（如果本轮已经是最后一轮，则游戏结束）。
- 交换 $a_i$ 和 $a_{i+1}$ 两个元素。
如果在最后一轮结束后，序列 $a$ 是非递减的（即对于每个 $1 \le i < n$，都有 $a_i \le a_{i+1}$），则 Souvlaki 获胜。否则，Kalamaki 获胜。
然而，Souvlaki 不喜欢输，所以在游戏开始之前，他可以任意重新排列 $a$ 中的元素。请判断他是否可以重新排列 $a$，使得无论 Kalamaki 如何操作，他都一定能获胜。
他们将玩一个包含 $n-1$ 轮的游戏，轮次编号从 $1$ 到 $n-1$。Souvlaki 在奇数轮出手，Kalamaki 在偶数轮出手。
在第 $i$ 轮，当前玩家可以选择以下两种操作之一：
- 跳过本回合，进入第 $i+1$ 轮（如果本轮已经是最后一轮，则游戏结束）。
- 交换 $a_i$ 和 $a_{i+1}$ 两个元素。
如果在最后一轮结束后，序列 $a$ 是非递减的（即对于每个 $1 \le i < n$，都有 $a_i \le a_{i+1}$），则 Souvlaki 获胜。否则，Kalamaki 获胜。
然而，Souvlaki 不喜欢输，所以在游戏开始之前，他可以任意重新排列 $a$ 中的元素。请判断他是否可以重新排列 $a$，使得无论 Kalamaki 如何操作，他都一定能获胜。
输入格式
每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试数据组数。
每组测试数据的第一行为一个整数 $n$（$3 \le n \le 100$），表示 $a$ 的长度。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列 $a$ 的每个元素。
每组测试数据的第一行为一个整数 $n$（$3 \le n \le 100$），表示 $a$ 的长度。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列 $a$ 的每个元素。
输出格式
对于每组测试数据，若 Souvlaki 能通过重新排列 $a$ 来保证自己获胜，输出 “YES”，否则输出 “NO”。
输出不区分大小写，例如 “yEs”、“yes”、“Yes” 和 “YES” 均视为正确答案。
输出不区分大小写，例如 “yEs”、“yes”、“Yes” 和 “YES” 均视为正确答案。
输入输出样例
输入 #1
5 4 4 2 2 1 4 1 1 1 1 5 1 5 1 5 1 3 1 2 3 5 1 3 2 3 5
输出 #1
YES YES YES NO NO
在第一个样例中，$a = [4, 2, 2, 1]$。可以将序列重新排列为 $a = [2, 1, 2, 4]$，此时 Souvlaki 可以这样获胜：
1. 第 1 轮，Souvlaki 行动。他选择交换 $a_1$ 和 $a_2$，此时 $a = [1, 2, 2, 4]$。
2. 第 2 轮，Kalamaki 行动。无论他选择跳过还是交换 $a_2$ 和 $a_3$，$a$ 都不会变。假设他选择跳过。
3. 第 3 轮，Souvlaki 行动。他亦可选择跳过，因为如果此时交换最后两个元素会导致失败。
每一轮后，$a = [1, 2, 2, 4]$，始终是非递减的，所以 Souvlaki 获胜，无论 Kalamaki 如何选择。
在第二个样例中，因为所有元素都相等，序列始终是非递减的，所以 Souvlaki 一定获胜。
1. 第 1 轮，Souvlaki 行动。他选择交换 $a_1$ 和 $a_2$，此时 $a = [1, 2, 2, 4]$。
2. 第 2 轮，Kalamaki 行动。无论他选择跳过还是交换 $a_2$ 和 $a_3$，$a$ 都不会变。假设他选择跳过。
3. 第 3 轮，Souvlaki 行动。他亦可选择跳过，因为如果此时交换最后两个元素会导致失败。
每一轮后，$a = [1, 2, 2, 4]$，始终是非递减的，所以 Souvlaki 获胜，无论 Kalamaki 如何选择。
在第二个样例中，因为所有元素都相等，序列始终是非递减的，所以 Souvlaki 一定获胜。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？