这是一个用于生成 NOI/CSP 竞赛风格测试数据的数据生成器。

该生成器会一次性在当前目录下创建 1.in/1.out 到 10.in/10.out 共20个文件。

设计思路

1. 覆盖性：
   • 极小数据 (1-2)：用于测试基本的逻辑正确性（如样例）。
   • 边界数据 (3-4)：测试长度为 1 和 2 的情况，检查循环条件和指针是否越界。
   • 中等数据 (5-7)：随机生成的字符串，长度递增，测试算法的稳定性。
   • 大数据 (8-10)：接近或达到 $10^5$ 长度，测试 $O(N)$ 时间复杂度和内存使用。
2. 特殊构造：
   • 包含回文串（翻转后不变）。
   • 包含全相同字符（测试极端情况）。
3. 兼容性：
   • 生成字符范围为 ASCII 33 (!) 到 126 (~)，不包含空格。这是为了配合上一题题解中 cin >> s 的读取方式（cin 遇空格停止）。如果需要包含空格，题解代码需改为 getline。这里默认生成无空格字符串。

C++ 数据生成器代码

/**
 * 题目：字符串的镜像仪式 - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out 测试数据
 * 标准：C++14
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm> // for reverse
#include <random>    // for mt19937
#include <chrono>

using namespace std;

// ================= 配置区域 =================
const int MAX_N = 100000; // 题目最大数据范围
const int TEST_CASES = 10; // 测试点数量

// ================= 工具函数 =================

// 随机数生成器初始化 (使用梅森旋转算法，比 rand() 质量更高)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 生成指定范围内的一个随机整数 [l, r]
int randomInt(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成指定长度的随机字符串 (ASCII 33-126, 可见字符，不含空格)
string generateRandomString(int length) {
    string s = "";
    s.reserve(length);
    for (int i = 0; i < length; ++i) {
        // ASCII 33(!) 到 126(~)
        s += (char)randomInt(33, 126); 
    }
    return s;
}

// 生成全相同的字符串
string generateSameCharString(int length, char c) {
    return string(length, c);
}

// 标准解法函数：用于生成 .out 文件
// 绝对正确暴力解法或库函数解法
string solve(string s) {
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    cout << "开始生成测试数据..." << endl;

    for (int i = 1; i <= TEST_CASES; ++i) {
        string inputStr;
        
        // ================= 数据构造逻辑 =================
        if (i == 1) {
            // 测试点 1: 题目样例 1
            inputStr = "hello";
        } 
        else if (i == 2) {
            // 测试点 2: 题目样例 2
            inputStr = "Hannah";
        } 
        else if (i == 3) {
            // 测试点 3: 最小边界，长度 1
            inputStr = generateRandomString(1);
        } 
        else if (i == 4) {
            // 测试点 4: 极小边界，长度 2 (刚好交换一次)
            inputStr = generateRandomString(2);
        } 
        else if (i == 5) {
            // 测试点 5: 小规模随机，长度 100
            inputStr = generateRandomString(100);
        } 
        else if (i == 6) {
            // 测试点 6: 中规模随机，长度 1000
            inputStr = generateRandomString(1000);
        } 
        else if (i == 7) {
            // 测试点 7: 回文串构造，长度 5000 (如 AB...BA)
            // 先生成一半
            string half = generateRandomString(2500);
            string revHalf = half;
            reverse(revHalf.begin(), revHalf.end());
            inputStr = half + revHalf;
        } 
        else if (i == 8) {
            // 测试点 8: 大规模全同字符，长度 50000 (测试大量重复字符处理)
            inputStr = generateSameCharString(50000, 'A');
        } 
        else if (i == 9) {
            // 测试点 9: 大规模随机，长度 100000 (最大范围)
            inputStr = generateRandomString(MAX_N);
        } 
        else if (i == 10) {
            // 测试点 10: 大规模随机，长度 100000 (最大范围，增加鲁棒性测试)
            inputStr = generateRandomString(MAX_N);
        }

        // ================= 写入文件 =================
        string inFileName = to_string(i) + ".in";
        string outFileName = to_string(i) + ".out";

        // 写入 .in
        ofstream fin(inFileName);
        fin << inputStr << endl; // 保证文末有换行
        fin.close();

        // 计算答案并写入 .out
        ofstream fout(outFileName);
        fout << solve(inputStr) << endl;
        fout.close();

        cout << "Generated Test Case " << i << ": Length = " << inputStr.length() << endl;
    }

    cout << "所有数据生成完毕。" << endl;
    return 0;
}

使用指南

1. 编译运行： 将上述代码保存为 generator.cpp，使用 G++ 编译并运行：

   g++ generator.cpp -o generator -O2
   ./generator
   

2. 生成结果： 运行后，当前目录下会出现 1.in, 1.out ... 10.in, 10.out。
3. 数据说明：
   • 1-2.in: 样例数据，方便学生自测。
   • 3.in: 长度1，测试边界。
   • 7.in: 回文串，输出应与输入相同。
   • 9-10.in: 满载 $10^5$ 长度，用于卡掉 $O(N^2)$ 的错误写法（如每次取出字符再拼接）。

注意事项

• 空格处理：本生成器生成的字符串不含空格。如果你的题目允许输入带空格的句子（如 "Hello World"），请将 generateRandomString 中的 randomInt(33, 126) 改为 randomInt(32, 126)，并且在读取 .in 文件的标准代码中必须使用 getline(cin, s) 而非 cin >> s。
• 换行符：fin << inputStr << endl; 保证了输入文件末尾有一个换行符，这是 NOI 数据的标准格式，防止某些 getline 写法读取异常。

你好！作为金牌教练，我为你整理了这份完全符合 NOIP/CSP C++14 竞赛标准的题解代码。

这份代码不仅演示了如何解决问题，更展示了竞赛代码的规范写法（如 IO 优化、引用传参、边界处理）。

一、 NOIP C++14 标准题解代码

/**
 * 题目名称：字符串的镜像仪式 (String Reversal)
 * 算法标签：双指针 (Two Pointers), 模拟
 * 语言标准：C++14
 */

#include <iostream>
#include <string>
#include <algorithm> // 用于 std::swap
#include <vector>

using namespace std;

// 【核心逻辑】
// 使用引用传参 (string& s)，确保是在原内存空间进行修改，
// 避免产生副本，从而满足“原地修改”和 O(1) 空间的要求。
void reverseString(string& s) {
    // 定义双指针
    // left 指向头部，right 指向尾部
    int left = 0;
    int right = (int)s.length() - 1; // 易错点1：size() 返回无符号整型，建议转为 int 防止空串时的溢出风险

    // 只要左指针在右指针的左侧，就进行交换
    while (left < right) {
        // 交换两端的字符
        // C++ 标准库 swap 高效且不易出错
        swap(s[left], s[right]);
        
        // 指针向中间靠拢
        left++;
        right--;
    }
}

int main() {
    // 【竞赛技巧】IO 性能优化
    // 关闭 stdio 与 iostream 的同步，解除 cin 与 cout 的绑定
    // 在数据量达到 10^5 ~ 10^6 级别时，能显著降低输入输出耗时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    // 读入字符串
    // 易错点2：如果题目输入包含空格（如 "Hello World"），应使用 getline(cin, s);
    // 针对本题样例（无空格单词），cin >> s 足够，但 getline 兼容性更强。
    // 这里为了严谨适配题目描述的 "字符串"，我们采用 cin >> s (假设无空格) 
    // 若需处理带空格的整行，请改为 getline(cin, s);
    if (cin >> s) {
        reverseString(s);
        cout << s << endl;
    }

    return 0;
}

二、 复杂度分析与思考过程

在考场上，写完代码后必须进行复杂度的估算，以确保不会 TLE (Time Limit Exceeded) 或 MLE (Memory Limit Exceeded)。

1. 时间复杂度分析

• 思考过程：
  • 我们的算法主要在一个 while 循环中运行。
  • 指针 left 从 $0$ 走到 $N/2$，指针 right 从 $N-1$ 走到 $N/2$。
  • 总共进行的交换次数大约是 $N/2$ 次。
  • 每一次交换 swap 和指针移动的操作都是常数时间 $O(1)$。
  • 总操作次数 $T(N) \approx \frac{N}{2} \times C$。
• 结论：忽略常数系数，时间复杂度为 $O(N)$。
  • 其中 $N$ 为字符串长度。对于 $N=10^5$ 的数据，计算机大约需要执行 $5 \times 10^4$ 次基础运算，远小于竞赛通常的限制（$10^8$ 次/秒），所以绝对安全。

2. 空间复杂度分析

• 思考过程：
  • 我们要看除了存储输入的字符串 $S$ 之外，我们在算法运行中额外申请了多少内存。
  • 我们只定义了两个整型变量 left, right。（在 swap 内部可能有一个临时的 char 变量）。
  • 无论 $N$ 是 10 还是 100,000，我们占用的额外变量数量永远是固定的几个。
• 结论：空间复杂度为 $O(1)$。
  • 这完全符合题目中“原地修改”和“不使用额外空间”的要求。

三、 优化建议 (针对竞赛场景)

虽然算法本身的 $O(N)$ 已经是理论最优（你不可能在不访问所有字符的情况下反转它们），但在工程和竞赛细节上仍有优化空间：

1. I/O 优化 (关键)：

   • 现象：C++ 的 cin / cout 默认为了兼容 C 语言的 scanf / printf，会有同步缓存操作，效率较低。当输入输出数据量巨大（例如字符串长达 $10^6$ 或有多组测试数据）时，可能会导致 I/O 瓶颈。
   • 对策：使用代码中演示的 ios::sync_with_stdio(false); cin.tie(nullptr);。这在 NOI 系列比赛中是必备模板。

2. 类型安全：

   • s.length() 返回的是 size_t (无符号整数)。如果字符串为空（长度0），直接写 s.length() - 1 会发生下溢，变成一个巨大的正整数，导致数组越界访问。
   • 对策：代码中使用了 (int)s.length() - 1 强转，或者判断 !s.empty()，这是保证代码健壮性的细节。

3. 内联 (Inline)：

   • 虽然现代编译器优化很强，但在极度卡常（Time Limit 非常紧）的情况下，可以直接将 reverseString 的逻辑写在 main 函数里，减少一次函数调用的开销（尽管在这个量级通常忽略不计）。