题意:将字符串分割为尽量少的子字符串,每一个子字符串都是本身所有循环排列的字典序最小值
开场第一眼看的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;
}
京公网安备 11010502036488号