题目描述:给你一串01串 构成一个环 如 10110 等价于01101(向前) 为了使这个串在环中字序最小 现在要你把它们分为很多个小串使得每个串在自己的那个小串里字典序最小,且尽可能少分几段
如
input
0010
out
001 0
有T<300行输入,每行字符串不超过200个字符
分析: 看数据范围很显然是个模拟题,太弱了没模拟出~~~, 首先从头开始判断最远可以有多长的子串满足条件(从后到前 贪心)(判断过程模拟循环一遍将结果保存,如果这个位置是这里面最小的满足条件输出,并且跳到下一个判断)
可以学习下一些小操作
#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ string s; cin>>s; for(int i=0,len=s.length();i<len;i++){ int ans=i; for(int j=len-1;j>=i;j--){ vector<string >ss; for(int k=i;k<=j;k++){ ss.push_back(s.substr(k,j-k+1)+s.substr(i,k-i)); } sort(ss.begin(),ss.end()); if(ss[0]==s.substr(i,j-i+1)){ ans=j;break;} } cout<<s.substr(i,ans-i+1)<< (ans!=len-1?' ':'\n'); i=ans; } } }