2019牛客暑期多校训练营（第七场）

A String

题意：给一个01串，把该串划分，使得每个子串都是所在串形成的环中字典序最小的。 题解：把01串中以1、0分界处都拆开，对拆分出来的子串我们再两两比对，可以合并则合并。队友AC代码

#include #define LL long long #define ms0(x) memset(x,0,sizeof(x)) #define ms-1(x) memset(x,-1,sizeof(x)) bool vis[300]; using namespace std; int pos[300]; string save[300]; struct node{ string str; int num_0; int num_1; node(string a):str(a) { num_0=0;int j=0; for(;j<str.size();j++) { if(a[j]=='1') break; } num_0=j; num_1=str.size()-num_0; } node(){ } bool operator >(const node & tmp)const{ string tmp1,tmp2; tmp1=str+tmp.str; tmp2=tmp.str+str; return tmp1<=tmp2; //      if(tmp.num_1==0) //      { //          if(num_1==0) //              return true; //          else //              return false; //      } //      if(num_0==tmp.num_0) //          return num_1<=tmp.num_1; //      else //          return num_0>tmp.num_0; } }ans[300]; int main() { ios::sync_with_stdio(false); int t; cin>>t;string str; while(t--) { cin>>str; pos[0]=-1; memset(vis,0,sizeof(vis)); int cnt=1; for(int j=0;j<str.size();j++) { if(str[j]=='1'&&j<str.size()-1&&str[j+1]=='0') { save[cnt]=str.substr(pos[cnt-1]+1,j-pos[cnt-1]); pos[cnt]=j; cnt++; } } save[cnt]=str.substr(pos[cnt-1]+1,str.size()-1-pos[cnt-1]); pos[cnt]=str.size()-1; cnt++; int ans_num=1; ans[1]=node(save[1]); for(int j=2;j<cnt;j++) { node tmp=node(save[j]); if(ans[ans_num]>tmp) { ans[ans_num].str+=tmp.str; } else { ans[++ans_num]=tmp; } } while(ans_num>1) { int tmpnum=1; bool flag=0; for(int j=2;j<=ans_num;j++) { if(ans[tmpnum]>ans[j]) { ans[tmpnum].str+=ans[j].str; flag=1; } else { ans[++tmpnum]=ans[j]; } } ans_num=tmpnum; if(flag==0) break; } for(int j=1;j<=ans_num;j++) cout<<ans[j].str<<" "; cout<<endl; //      for(int j=1;j //      { //          cout<