CF1703D Double Strings-题解
ZhanPJ
·
·
题解
题目简述：
给出 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。
```map<string,bool> strs;```
这样我们就可以使用 $O(\log n)$ 的时间复杂度去查找 $s_j,s_k$ 和插入 $s_x$。
---
**AC 代码：**
```cpp
#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;
}
```