2019牛客多校第七场A题

题意：将字符串分割为尽量少的子字符串，每一个子字符串都是本身所有循环排列的字典序最小值
开场第一眼看的A题 觉得能做，一开始的想法是遇见先0后1就输出完1然后空格，后来发现题目的0101就不对
后来想到做每一个1的前导0的数量，当前导0数量非递减排列的时候，必然要分割，当相邻两端前导0数量相等我们判断1的数量，1的数量非递增就可以连着，否则就分开，如此一来，样例和能想到的数据都能过了，贴一个wa码

#include<cstdio>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <queue>

#define rep(i, n) for(int i=0;i<n;i++)
#define per(i, n) for(int i=n;i>=1;i--)
#define pb(x) push_back(x)
#define clint(x, n) memset(x,n,sizeof(x))
typedef long long ll;
const int maxn = 25;
const ll inf = 99999999;
using namespace std;
int dirx[] = {1, 0, -1, 0, 0, 0};
int diry[] = {0, 1, 0, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int px, py, pz;
int m, n, T, t;
char ma[30][30][30];
int vis[30][30][30];
int ans;
int ex, ey, ez;
char ss[10];
string str;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        cin >> str;
        int len = str.size();
        int ff[1000];
        int mark[300];
        clint(mark, -1);
        clint(ff, 0);
        int cnt0 = 0, cnt1 = 0;
        int x1, x2;
        int i = 0;
        for (i = 0; i < len; i++) {
            if (str[i] == '1') cout << str[i], mark[i] = 0;
            else break;
        }
        if(str[0]=='1') cout << ' ';
        for (int j = i; j < len; j++) {
            if (str[j] == '1') {
                for (int k = j - 1; k >= 0; k--) {
                    if (str[k] == '1' || k == 0) {
                        if (k == 0 && str[0] == '0')
                            cnt0++;
                        mark[j] = cnt0;
                        //cout<<"test:"<<j<<' '<<mark[j]<<endl;
                        cnt1++;
                        cnt0 = 0;
                        break;
                    } else {
                        cnt0++;
                    }
                }
            }
        }
        rep(j, len) {
            //cout << mark[j] << ' ';
            if (mark[j] > 0) {
                for (int k = j - 1; k >= 0; k--) {
                    if (mark[k] < mark[j]&&mark[k]>0) {
                        for (int o = k; o <= j; o++) {
                            if (mark[o] == -1) {
                                ff[o - 1] = 1;
                                break;
                            }
                        }
                    } else if (mark[k]==mark[j]&&mark[k]>0) {
                        x1 = 0, x2 = 0;
                        for (int o = k; o < len; o++) {
                            if (mark[o] == -1) break;
                            x1++;
                        }
                        for (int o = j; o < len; o++) {
                            if (mark[o] == -1) break;
                            x2++;
                        }
                        if (x2 < x1)
                            for (int o = k; o <= j; o++) {
                                if (mark[o] == -1) {
                                    ff[o - 1] = 1;
                                    break;
                                }
                            }
                    }
                }
            }
        }
        if(str[len-1]=='0'){
            for(int j=len;j>=0;j--){
                if(mark[j]>=0) {
                    ff[j]=1;
                    break;
                }
            }
        }
//        rep(j,len) cout<<mark[j]<<' ';
//        cout<<endl;
        for (int j = i; j < len; j++) {
            cout << str[j];
            if (ff[j]) cout << ' ';

        }
        cout << endl;
    }
    return 0;
}

后来我看题解居然直接暴力？？？？我都没看过这种题能暴力，不过。。。数据长度200.不暴力都对不起自己啊。。我无语了，贴一个补题ac码：

#include<cstdio>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <queue>

#define rep(i, n) for(int i=0;i<n;i++)
#define per(i, n) for(int i=n;i>=1;i--)
#define pb(x) push_back(x)
#define clint(x, n) memset(x,n,sizeof(x))
typedef long long ll;
const int maxn = 25;
const ll inf = 99999999;
using namespace std;
int dirx[] = {1, 0, -1, 0, 0, 0};
int diry[] = {0, 1, 0, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int px, py, pz;
int m, n, T, t;
char ma[30][30][30];
int vis[30][30][30];
int ans;
int ex, ey, ez;
char ss[10];
string str;
bool check(string s){                                 //判断当前字符串是否自身循环内字典序最小
    int len=s.length();
    for(int i=1;i<len;i++)                            //枚举循环情况
        for(int j=0;j<len;j++){                       //枚举s中字符 比较字典序
            if(s[j]<s[(i+j)%len]) break;              //如若当前位小于 则无需再次比较 一定小于
            if(s[j]>s[(i+j)%len]) return false;       // 如果当前位大于 说明不是字典序最小
        }
    return true;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int len=s.length();
        int i=0;
        while(i<len){
            for(int j=len-i;j>=0;j--){           //暴力枚举当前01串长度
                if(check(s.substr(i,j))){        //判断 从i位置开始到j的01串 是否最小        复制字符串-> substr(开始位置，长度)
                    cout<<s.substr(i,j);         //输出
                    i+=j;                        //将i移至当前字符串之后一位
                    if(i<len) cout<<" ";         //如果不是最后一串01串 加上空格
                    break;                       //已经找到字符串 跳出本次循环
                }
            }
        }
        cout<<endl;
    }
    return 0;
}