一、题目回顾（精简版）

给定：

• 一个字符串 $s$
• 一个偶数 $n$（$n \ge 2$，可到 $10^9$）

你可以做恰好 $n$ 次操作：

1. 操作1：把当前字符串的反转拼到后面
2. 操作2：把当前字符串反转

要求：输出操作后字典序最小的字符串。

二、代码分析

完整代码

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

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

    int tt;
    cin >> tt;
    while (tt--) {
        long long n;  // n 最大 1e9，必须用 long long
        cin >> n;
        string s;
        cin >> s;
        
        string t = s;
        reverse(t.begin(), t.end()); // t = s 的反转
        
        cout << min(s, t + s) << "\n"; // 核心：二选一最优
    }
    return 0;
}

代码逐行解析

1. 快读优化
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   加速 cin/cout，避免大数据超时。

2. 变量类型正确
   long long n
   $n \le 10^9$ 超过 int 范围（int≈2e8），必须用 long long。

3. 核心逻辑

   string t = s;
   reverse(t.begin(), t.end());
   cout << min(s, t + s);
   

   • 先求反转串 t
   • 最优答案只有两种可能： ✔ s（一直反转，偶数次抵消） ✔ t+s（先反转 → 拼接 → 剩下反转抵消）

三、完整题解（构造算法）

1. 关键观察（破题点）

• 操作 2（反转）做偶数次 = 白做 反转 2 次、4 次、1000000000 次 → 字符串不变
• $n$ 一定是偶数，所以：
  • 无论中间怎么操作，最后偶数次反转都会抵消
  • 我们只需要做 0 次或 1 次有效反转

2. 最优策略（构造结论）

只有 2 种最优方案：

1. 不使用操作 1 全程只反转（偶数次）→ 结果 = $s$
2. 使用一次操作 1 反转 → 拼接 → 剩下反转抵消 → 结果 = $t+s$

最终答案 = $\boldsymbol{\min(s,\ t+s)}$

3. 为什么不用考虑其他情况？

• 操作 1 用多次会让字符串变得更大，字典序一定更差
• 操作 2 做多次无意义
• 所以只需要比较两个候选答案

四、时间 & 空间复杂度

• 时间复杂度：$O(\sum |s|)$ 字符串长度最多 100，总数据量极小，完全无压力。
• 空间复杂度：$O(|s|)$ 只存字符串和反转串，极简高效。

五、样例验证

样例 2

输入：grib

• $s = \text{grib}$
• $t = \text{birg}$
• $t+s = \text{birggrib}$
• $\min(\text{grib},\ \text{birggrib}) = \text{birggrib}$ ✅

样例 1

输入：cpm

• $\min(cpm, mpc+cpm) = cpm$ ✅

最终总结（最重要的三句话）

1. 这是一道构造算法题，不需要模拟，找规律直接输出答案。
2. 因为 $n$ 是偶数，反转偶数次等于没反转。
3. 最优答案只有两个候选：$\boldsymbol{\min(s,\ \text{reverse}(s)+s)}$。