题解[COCI2017-2018#1] Lozinke
zhouwc
2018-09-15 15:53:14
## 可以访问我的[博客](http://zwcblog.top./zwc/2018/09/15/%E9%A2%98%E8%A7%A3-p4421-coci2017-20181-lozinke/#i-5)以获得更佳的阅读体验(包括题目翻译)
#### 一道水题?
下面的大神用的都是hash,本蒟蒻太弱了只会一种暴力方法,stl大法好啊。
因为读入的字符串的长度小于10,而且子串必须是连续的,这样的话子串总和并不会太多。
那么对于读入的字符串,直接暴力把这个字符串所包含的所有子集给存到set里面。
然后直接映射到map里,把子集的个数加1.
最后直接统计答案,子集为a[i](读入字符串)的有多少个。全部累加,最后需要剪掉n(因为我们把需要匹配的整个串也算进去了,要剪掉```1*n```个)
讲的已经很清楚了,如果不理解或者有疑问的话可以提出来,也可以私信问我。
code:
```cpp
#include<bits/stdc++.h>
using namespace std;
string a[20005];
set<string>s;
map<string,int>q; //stl的强大力量
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
s.clear();
cin>>a[i];
for (int j=0;j<a[i].size();j++)
{
string c;
for (int k=j;k<a[i].size();k++)
{
c.push_back(a[i][k]);
s.insert(c); //存到set里面
}
}
for(set<string>::iterator i=s.begin();i!=s.end();i++) //map
{
q[*i]++;
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=q[a[i]];
printf("%d",ans-n);
return 0;
}
```