[[构造]]

A. Souvlaki VS. Kalamaki

时间限制：每个测试 1 秒
内存限制：每个测试 256 MB

问题描述

两个玩家 Souvlaki 和 Kalamaki 被给定一个包含 $n$ 个整数的序列 $a$。

他们将进行一个包含 $n-1$ 轮的游戏，轮次编号从 $1$ 到 $n-1$。Souvlaki 在奇数轮行动，Kalamaki 在偶数轮行动。

在第 $i$ 轮中，当前玩家可以选择执行以下操作之一：

• 跳过他的回合，进入第 $i+1$ 轮（如果第 $i$ 轮是最后一轮，则结束游戏）。
• 交换元素 $a_i$ 和 $a_{i+1}$。

如果在最后一轮结束后，$a$ 按非递减顺序排序（即对于每个 $1 \leq i < n$，都有 $a_i \leq a_{i+1}$），则 Souvlaki 获胜。否则，Kalamaki 获胜。

然而，Souvlaki 不喜欢输，所以在游戏开始前，他可以用任何他想要的方式重新排列 $a$ 的元素。他是否可能通过重新排列元素，使得他有一个保证获胜的策略？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 100$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ($3 \leq n \leq 100$) —— 序列 $a$ 中的整数个数。

第二行包含恰好 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) —— 表示 $a$ 的第 $i$ 个元素。

输出格式

对于每个测试用例，如果 Souvlaki 能够通过重新排列 $a$ 的元素来获得保证获胜的策略，则在单独一行输出 "YES"，否则输出 "NO"。

你可以以任何大小写形式输出答案。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

样例输入

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

样例输出

YES
YES
YES
NO
NO

样例说明

在第一个样例中，$a = [4, 2, 2, 1]$。一种可能的重新排列方式是 $a = [2, 1, 2, 4]$。然后游戏可能按如下进行：

• 第 1 轮是 Souvlaki 的回合。他选择交换 $a_1$ 和 $a_2$，现在 $a = [1, 2, 2, 4]$。
• 第 2 轮是 Kalamaki 的回合。无论他选择跳过回合还是交换元素 $a_2$ 和 $a_3$，$a$ 都将保持不变。假设他跳过回合。
• 第 3 轮是 Souvlaki 的回合。他也可以选择跳过回合，因为如果他交换最后两个元素，他可能会输。

在每一轮之后，$a = [1, 2, 2, 4]$，按非递减顺序排序，所以无论 Kalamaki 如何选择，Souvlaki 都会获胜。

在第二个样例中，由于所有元素都相等，$a$ 总是按非递减顺序排序，因此 Souvlaki 总是获胜。

赛时AC代码

• 赛时思路，
• 假如 1-6
• 对于偶数们直接判断类似 2-3 4-5；
• 对于技术直接判断（1-5） 2 -3 4-5

  // Problem: CF 2163 A
  // Contest: Codeforces - Codeforces Round 1063 (Div. 2)
  // URL: https://codeforces.com/contest/2163/problem/A
  // Memory Limit: 256 MB
  // Time Limit: 1000 ms
  // 
  // Powered by CP Editor (https://cpeditor.org)
  
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<LL,LL> PII;
  const int N=1e9+7,INF=0x3f3f3f3f;
  
  
  void solve() {
      int n;
      cin>>n;
      vector<int> a(n+1);
      for(int i=1;i<=n;i++) cin>>a[i];
      sort(a.begin()+1,a.end());
      if(n&1)
      {
          for(int i=2;i<n;i+=2){
              if(a[i]!=a[i+1]){
                  printf("NO\n");
                  return ;
              }
          }
      }else{
          for(int i=3;i<n;i+=2){
              if(a[i]!=a[i-1]){
                  printf("NO\n");
                  return ;
              }
          }
      }
      printf("YES\n");
      return;
  }
  
  int main() {
      int t;
      cin >> t;
      while (t--) {
          solve();
      }
      return 0;
  }
  

jiangly 代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    for (int i = 2; i < n; i += 2) {
        if (a[i] != a[i - 1]) {
            std::cout << "NO\n";
            return;
        }
    }

    std::cout << "YES\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

对题目的解析

很高兴能帮你分析这个问题！你能在比赛中AC这道题，说明你对问题有不错的直觉和实现能力。

你提供的两份代码，你自己的AC代码和jiangly的代码，在核心逻辑上是完全一致且正确的。这道题表面上是一个博弈论问题，但实际上是一个巧妙的构造和条件检查问题。

下面我来帮你分析这道题在考验什么，以及如何从对比中提高。

---

🧐 这道题在考验什么？

这道题主要在考验你以下几种能力：

1. 博弈论问题的简化能力： 能否看穿游戏规则的表象，找到问题的“死穴”。

2. 非对称性分析能力： 识别出两个玩家的行动（Souvlaki在奇数位，Kalamaki在偶数位）是_非对称_且_互不干涉_的。

3. 最优策略的构造能力： 意识到Souvlaki的_唯一_制胜机会在于游戏开始前的“重新排列”。

4. 将策略转化为代码的能力： 把“必胜策略”翻译成一个简单的、可执行的检查条件（即排序后检查特定位置的元素是否相等）。

---

💡 核心思路拆解 (Step-by-Step)

让我们来一步步拆解这个游戏，看看为什么最后会变成一个简单的 sort + check。

1. 问题的核心：谁在“捣乱”，谁能“修复”？

• Souvlaki (S, 玩家1)：在第 $1, 3, 5, \dots$ 轮行动。他可以交换 $(a_1, a_2), (a_3, a_4), (a_5, a_6), \dots$。

• Kalamaki (K, 玩家2)：在第 $2, 4, 6, \dots$ 轮行动。他可以交换 $(a_2, a_3), (a_4, a_5), (a_6, a_7), \dots$。

这里最关键的洞察是：S 和 K 的行动“领地”是错开的！

• K 可以制造 $(a_2, a_3)$ 之间的逆序。

• S 永远 无法通过他的行动（交换 $a_1, a_2$ 或 $a_3, a_4$）来_修复_ $(a_2, a_3)$ 之间的逆序。

2. Souvlaki 的必胜策略是什么？

Souvlaki (S) 的目标是让数组最终有序。Kalamaki (K) 的目标是阻止这件事。

S 拥有一个巨大的优势：游戏开始前可以任意排列数组。

S 显然应该先把数组排成非递减顺序，即 $a_1 \le a_2 \le a_3 \le \dots \le a_n$。这是他的目标状态。

现在，游戏开始。

• 第 1 轮 (S)：S 看到 $(a_1, a_2)$。因为 $a_1 \le a_2$，S 绝对不会交换。他选择“跳过”。

• 第 2 轮 (K)：K 看到 $(a_2, a_3)$。

  • 情况 A (K 的机会)： 如果 $a_2 < a_3$，K 就可以选择“交换”，数组变为 $a_1, a_3, a_2, a_4, \dots$。此时 $a_3 \ge a_2$，数组出现了一个逆序。

  • 情况 B (K 的绝望)： 如果 $a_2 = a_3$，K 无论“交换”还是“跳过”，数组都保持 $a_1, a_2, a_3, a_4, \dots$。K 无法制造逆序。

3. 关键的推论

在第 2 轮，如果 $a_2 < a_3$，K 就可以制造一个 S _永远无法修复_的逆序，S 必败。

因此，S 要想_保证获胜_，他必须在游戏开始前，就确保 K _没有任何机会_制造逆序。

S 必须让 K 的所有可能行动都变得“无效”。K 的行动有哪些？

• 第 2 轮，K 威胁 $(a_2, a_3)$。S 必须保证 $a_2 = a_3$。

• 第 4 轮，K 威胁 $(a_4, a_5)$。S 必须保证 $a_4 = a_5$。

• 第 6 轮，K 威胁 $(a_6, a_7)$。S 必须保证 $a_6 = a_7$。

• ...

• 第 $2k$ 轮，K 威胁 $(a_{2k}, a_{2k+1})$。S 必须保证 $a_{2k} = a_{2k+1}$。

结论： Souvlaki 的必胜策略是：

1. 将 $a$ 数组排序。

2. 检查所有 K 可能行动的位置，即 $(a_2, a_3), (a_4, a_5), (a_6, a_7), \dots$。

3. 如果这些对中的_所有_元素都相等，S 就能获胜。

4. 只要有_任何一个_ $a_{2k} < a_{2k+1}$，K 就可以在那一轮进行交换，S 必败。

---

📈 如何从代码对比中提高？

你的代码和 jiangly 的代码都正确实现了这个逻辑。区别在于实现的简洁性。

你的代码：

C++

    sort(a.begin()+1,a.end());
    if(n&1) // n 是奇数
    {
        for(int i=2;i<n;i+=2){ // i = 2, 4, ... n-1
            if(a[i]!=a[i+1]){ // 检查 (a[2],a[3]), (a[4],a[5]), ... (a[n-1],a[n])
                printf("NO\n");
                return ;
            }
        }
    }else{ // n 是偶数
        for(int i=3;i<n;i+=2){ // i = 3, 5, ... n-1
            if(a[i]!=a[i-1]){ // 检查 (a[2],a[3]), (a[4],a[5]), ... (a[n-2],a[n-1])
                printf("NO\n");
                return ;
            }
        }
    }
    printf("YES\n");

• 优点： 逻辑正确。你很可能通过分析奇数（如n=5）和偶数（如n=4或n=6）的例子，分别得出了循环的边界，这是非常扎实的做法。

• 可提高点： 你对 n 的奇偶性进行了分类讨论。虽然正确，但这通常暗示着可能存在一个更统一的表达方式。

jiangly 的代码 (0-indexed)：

C++

    std::sort(a.begin(), a.end());

    // i = 2, 4, 6, ...
    for (int i = 2; i < n; i += 2) { 
        // 检查 a[1] vs a[2], a[3] vs a[4], a[5] vs a[6], ...
        if (a[i] != a[i - 1]) { 
            std::cout << "NO\n";
            return;
        }
    }

    std::cout << "YES\n";

• 优点： 非常简洁。它用一个循环就处理了所有情况。

• 为什么这一个循环就够了？

  • jiangly 的代码是 0-indexed。他检查的是 a[i] 和 a[i-1]。

  • 当 i=2，检查 a[2] 和 a[1]。(对应 1-indexed 的 $a_3$ 和 $a_2$)

  • 当 i=4，检查 a[4] 和 a[3]。(对应 1-indexed 的 $a_5$ 和 $a_4$)

  • ...

  • 这个循环的终止条件 i < n 自动处理了奇偶性：

    • 如果 n=5 (奇数)：i 会取 2, 4。检查 (a[1],a[2]) 和 (a[3],a[4])。对应我们分析的 $(a_2,a_3)$ 和 $(a_4,a_5)$。 i=6 时 6 < 5 不成立，循环结束。正确。

    • 如果 n=6 (偶数)：i 会取 2, 4。检查 (a[1],a[2]) 和 (a[3],a[4])。对应我们分析的 $(a_2,a_3)$ 和 $(a_4,a_5)$。 i=6 时 6 < 6 不成立，循环结束。正确。

🚀 你的提高点

1. 相信统一的规律： 当你发现需要按奇偶性分类讨论时，可以多花 10 秒钟想一想：“这两个 case 的循环体是不是在做本质相同的事？它们的起止点是否能用一个关于 n 的表达式统一起来？”

2. 抓住循环的本质： 你的两个 for 循环，本质都是在检查“第2、3个元素”，“第4、5个元素”...

   • (1-indexed) for (int i = 2; i + 1 <= n; i += 2)

   • 这个循环 i 会取 $2, 4, 6, \dots$

   • 它会检查 a[i] 和 a[i+1]

   • i 的上界是 i+1 <= n (即 $i$ 最大可以是 $n-1$)。

   • 如果 n=5：i 取 2 (检查 a[2],a[3])，i 取 4 (检查 a[4],a[5])。i=6 时 6+1 <= 5 不成立。

   • 如果 n=6：i 取 2 (检查 a[2],a[3])，i 取 4 (检查 a[4],a[5])。i=6 时 6+1 <= 6 不成立。

   • 你看，这一个循环就可以替代你的 if/else 结构了。

总的来说，你对问题的核心洞察是完全正确的，这最重要。下一步的提高就是在实现时，寻找更简洁、更统一的表达，这能减少边界错误，也让代码更清晰。

这个分析对你有帮助吗？你想不想再看一个类似的、关于博弈论和策略简化的题目？

CF 题解思路

• 假设轮到卡拉马基在某个偶数轮 $2k$ 上。Kalamaki可以将元素 $a_{2k}$ 与 $a_{2k+1}$ 交换。如果 $a_{2k} > a_{2k+1}$ ，他将不交换元素，但如果 $a_{2k} < a_{2k+1}$ ，他将交换元素。在这两种情况下，他都赢得了游戏，因为数组永远不会被排序。因此，如果 $a_{2k} \neq a_{2k+1}$ ，卡拉马基无论如何都会赢。现在假设Kalamaki每次玩游戏时，他可以交换的两个元素具有相同的值，否则我们就会证明他赢了。

假设轮到Souvlaki的回合 $2k+1$ 。根据前面的假设，我们知道 $a_{2k} = a_{2k+1}$ 。如果 $a_{2k+1} > a_{2k+2}$ ，我们知道 $a_{2k+1} = a_{2k} > a_{2k+2}$ ，但他无法交换 $a_{2k}$ 和 $a_{2k+2}$ ，因此他输了。否则，如果 $a_{2k+1} \le a_{2k+2}$ ，他将什么也不做，并进入下一轮。从这些观察中，我们看到 $a$ 可被Souvlaki赢得，当且仅当： $a_1 \le a_2 = a_3 \le a_4 = a_5 \le \ldots$ ，或 $a_2 \le a_1 = a_3 \le a_4 = a_5 \le \ldots$ 。

现在很明显，在游戏开始之前，Souvlaki将以非递减顺序排序 $a$ 。要确定Souvlaki是否获胜，只需检查排序后是否满足上述条件即可。

CF 题解代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    int a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for (int i = 2; i <= n - 1; i+=2) {
        if (a[i] != a[i+1]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}