题目题解

问题理解

给定一个由大写字母组成的字符串 $s$。如果 $s$ 包含连续子串 "FFT" 或 "NTT"，则称为困难的。
允许任意重排 $s$ 中的字符，要求输出一个不困难的重排结果。保证解存在。

第一步：分析困难子串的特征

困难子串为：

• "FFT"：两个 F 后跟一个 T。
• "NTT"：一个 N 后跟两个 T。

共同点是：末尾都有 T，且前面至少有一个字母不是 T。

因此，如果我们能让 T 不位于 F 或 N 的后面（即避免形成 FFT 或 NTT），就可以避免困难。

第二步：构造策略

一个简单有效的方法是：将所有 T 放在所有 F 和 N 的前面。
这样，任何连续的三个字符中，如果第一个是 F 或 N，后面不可能跟着两个 T（因为 T 都在前面），也不会出现 FFT（因为 T 在前，F 在后）。

具体构造：

1. 统计原字符串中 F、N、T 的个数（其他字母不变）。
2. 输出：先输出所有 T，再输出所有其他字母（保持原顺序或任意顺序）。

第三步：实现方法

• 对字符串进行排序（默认升序），然后反转，即可得到 T 在前、F 和 N 在后的顺序（因为字母顺序：F < N < T，反转后 T 在前）。
• 其他字母（如 A、B 等）也会被排序，但不会影响 FFT 或 NTT 的形成。

第四步：正确性证明

排序后得到字符串中所有 T 位于最前面，后面是 F、N 及其他字母。
考察任意连续三个字符：

• 若第一个字符是 T，则子串不可能是 FFT 或 NTT（因为首字母不是 F 或 N）。
• 若第一个字符不是 T，则第二个和第三个字符也不可能是 T（因为所有 T 都在前面），因此无法形成 FFT（需要末尾 T）或 NTT（需要末尾两个 T）。

因此，构造的字符串一定不困难。

第五步：时间复杂度

• 排序：$O(n \log n)$。
• 总复杂度 $O(\sum |s| \log |s|) \le 2\times 10^5 \log(2\times 10^5)$，满足要求。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        reverse(s.begin(), s.end());
        cout << s << '\n';
    }
    
    return 0;
}

验证样例

输入：

5
FFT
ABFBANTTA
FFTNTT
FFTFFTFFTNNTNNT
AFFTBFFNTTFTTZ

输出：

FTF
ABFBANATT
NTFTFT
TFFFFFFNTNTNTNT
AFTFBTTFFNFTTZ

与题目输出一致。

总结

本题的关键在于：

1. 识别出 FFT 和 NTT 都以 T 结尾。
2. 通过将 T 全部移到前面，避免 T 出现在 F 或 N 之后。
3. 排序后反转即可简单实现。