【正经题解】Recamán

动态数组太好用拉

---

题目大意

一共有 $t$ 次询问，每个询问给你 $n$ 个字符串，要求你判断是否有一个合法拼接序列，使拼接后的字符串单调递增。

---

思路：
由于不能拆字符串，那么最优方案肯定是将所有字符串按字典序从小到大拼接。
对于每次询问，我们将字符串放入数组中，并按字典序进行排序。之后拼接字符串。最后，我们判断这个字符串是否单调递增即可

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<string> s; 
        while(n--){
            string l;
            cin >> l;
            s.push_back(l);
        }sort(s.begin(),s.end());
        string a;
        for(auto i:s){
            a+=i;
        }bool p=false;
        for(int i=0;i<=a.size()-2;i++){
            if(a[i]>a[i+1]){
                p=true;
                break;
            }
        }cout << (p?0:1) << endl;
    }
    return 0;
}

时间复杂度：定义 $l$ 为字符串平均长度，时间复杂度为：$O(n \log n \times l)$，其中主要为排序复杂度，复杂度为 $O(n \log n \times l)$
空间复杂度： $O(n \times l)$ ，再此不做解释。