题意分析

题目要求将给定的01字符串分解为多个"项链"（在其所有循环旋转中字典序最小的字符串）的连接，且满足： 后一个项链的字典序严格小于前一个项链 相邻两个项链连接后不能是项链

解题思路

将字符串视为环，找到字典序最小的起始位置。 比较该最小表示是否等于原字符串。用动态规划处理：从字符串末尾向前处理，状态转移：

$dp[i]$：从位置i开始的后缀的项链分解列表 转移方程：尝试所有子串$s[i..j-1]$作为候选项链 若候选是项链：

若j在末尾 → 直接作为分解

否则检查：

后一个项链 < 当前项链（字典序）

两项链连接后不是项链

找到首个满足条件的j即可

标程

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

bool is_necklace(const string& s) {
    int n = s.size();
    if (n == 0) 
        return true;
    for (int start = 1; start < n; start++) {
        for (int k = 0; k < n; k++) {
            char c1 = s[k];
            char c2 = s[(start + k) % n];
            if (c1 < c2) {
                break;
            } else if (c1 > c2) {
                return false;
            }
        }
    }
    return true;
}

vector<string> decompose_string(const string& s) {
    int n = s.size();
    vector<vector<string>> dp(n + 1);
    dp[n] = vector<string>();

    for (int i = n - 1; i >= 0; i--) {
        bool found = false;
        for (int j = i + 1; j <= n; j++) {
            string candidate = s.substr(i, j - i);
            if (is_necklace(candidate)) {
                vector<string>& rest_list = dp[j];
                if (rest_list.empty()) {
                    dp[i] = {candidate};
                    found = true;
                    break;
                } else {
                    string next_piece = rest_list[0];
                    if (next_piece < candidate) {
                        string concat = candidate + next_piece;
                        if (!is_necklace(concat)) {
                            vector<string> new_list;
                            new_list.push_back(candidate);
                            for (const string& piece : rest_list) {
                                new_list.push_back(piece);
                            }
                            dp[i] = new_list;
                            found = true;
                            break;
                        }
                    }
                }
            }
        }
        if (!found) {
            string candidate = s.substr(i);
            if (is_necklace(candidate)) {
                dp[i] = {candidate};
            } else {
                dp[i] = {candidate};
            }
        }
    }
    return dp[0];
}

int main() {
    int t;
    cin >> t;
    cin.ignore();
    vector<string> results;
    for (int i = 0; i < t; i++) {
        string s;
        getline(cin, s);
        vector<string> decomposition = decompose_string(s);
        string result_str;
        for (const string& piece : decomposition) {
            result_str += "(" + piece + ")";
        }
        results.push_back(result_str);
    }
    for (const string& res : results) {
        cout << res << endl;
    }
    return 0;
}