题目简述

给出 n 个字符串，你需要判断字符串 s_i 能否有两个字符串 s_j 和 s_k 相加组成。其中 j \not = i , k \not = j。

解题思路

刚看到开始题目的数据量十分的大，t \leq 10^4，n \leq 10^5 的数据范围可以看到不可能枚举 s_j 和 s_k。（这样的时间复杂度是 O(n^2)，完全超时）。
那么我们要针对字符串“下手”。通过题面中强调了 s_i 的长度不超过 8，那么在枚举 s_i 的拆分最多只有 8 种可能（包含）。那么枚举 s_i 的拆分去寻找 s_j,s_k。
s_i 的拆分一直按 8 种计算，那么所有的拆分时间复杂度仅仅为 O(8 \cdot n)。接下来我们要尝试使用接近 O(1) (因为（O(1) 理论上不可以实现）的算法去寻找 s_j,s_k。在这里我使用了 map。（这是由红黑树实现的容器）

```map strs;```

这样我们就可以使用 O(\log n) 的时间复杂度去查找 s_j,s_k 和插入 s_x。

---

AC 代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#pragma GCC optimize(2)//O2优化
using namespace std;
string s[100050];
map<string,bool> strs;
string a,b;
int main(){
    int T,n;bool flag;
    scanf("%d",&T);
    while(T--){
        strs.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cin>>s[i];
            strs[s[i]]=1;
        }
        for(int i=1;i<=n;i++){
            flag=0;
            for(int j=1;j<s[i].length();j++){
                a="";b="";
                for(int k=0;k<j;k++)a+=s[i][k];
                for(int k=j;k<s[i].length();k++)b+=s[i][k];
                if(strs[a]&&strs[b]){flag=1;printf("1");break;}
            }
            if(!flag)printf("0");
        }
        printf("\n");
    }

    return 0;
}