Gardener and the Capybaras (easy version)

题目集链接
简单版本就是字符串的长度很小，可以用n²的时间复杂度来算，因为n<=100
所以我们可以先枚举a的终点，这时候b的起点就有了，然后我们再枚举b的终点，这时候c的起点和终点也就都有了，然后再验证

code

#include<bits/stdc++.h>
using namespace std;const int N = 110;int t;bool fun(string a, string b, string c)
{//string 之间的比较就是按照字典序来比的if((b >= a && b >= c) || (b <= a && b <= c)) return 1;return 0;
}int main()
{cin >> t;while(t --)	{string s;cin >> s;bool f = 0;int n = s.size();string s1, s2, s3;for(int i = 1; i <= n-2; i ++){if(f) break;s1 = s.substr(0, i);for(int j = 1; j <= n-1-i; j ++){//substr函数是真好用，参数就是起始位置，和长度s2 = s.substr(i, j);s3 = s.substr(i+j, n - (i+j));if(fun(s1, s2, s3)){f = 1;break;}}}if(f){cout << s1 << " " << s2 << " "<< s3 <<endl;}if(!f){puts(":(");}	}return 0;
}

Gardener and the Capybaras (hard version)

困难版本就是n<=200000这就要求我们要实现O(n)的时间复杂度或者O(nlogn）的时间复杂度，我们再重新看下这个题不难发现，这个题肯定是有答案的，就是一定可以找出来满足条件的a,b,c。

当b中含有‘a’时那么b可以当作最小的，然后b就只含一个’a’肯定b<=a && b<=c
当b中含有’b’时那么b可以当作最大的，我们可以让s[1]开始到s[n-2]当作b这s[1]肯定是’b’,有’a’的话直接上面那一种情况,这时候a=s[0]，c=s[n-1]，b肯定满足 b>=a && b >=c。

code

#include<bits/stdc++.h>using namespace std;const int N = 110;int t;bool fun(string a, string b, string c)
{if((b >= a && b >= c) || (b <= a && b <= c)) return 1;return 0;
}int main()
{cin >> t;while(t --)	{string s;cin >> s;bool f = 0;int n = s.size();string s1, s2, s3;for(int i = 1; i <= n - 2; i ++){if(s[i] == 'a'){f = 1;s1 = s.substr(0, i);s2 = "a";s3 = s.substr(i+1, n-i);break;}}if(!f){int p = 0;for(int i = 1; i <= n-2; i ++){if(s[i] == 'b'){p = i;	break;}}if(p){f = 1;s1 = s.substr(0, p);s2 = s.substr(p, n-1-p);s3 = s.substr(n-1, 1);}		}if(f){cout << s1 << " " << s2 << " "<< s3 <<endl;}if(!f){puts(":(");}	}return 0;
}