zhouwc 的博客

题解[COCI2017-2018#1] Lozinke

可以访问我的博客以获得更佳的阅读体验(包括题目翻译)

一道水题?

下面的大神用的都是hash,本蒟蒻太弱了只会一种暴力方法,stl大法好啊。

因为读入的字符串的长度小于10,而且子串必须是连续的,这样的话子串总和并不会太多。

那么对于读入的字符串,直接暴力把这个字符串所包含的所有子集给存到set里面。

然后直接映射到map里,把子集的个数加1.

最后直接统计答案,子集为a[i](读入字符串)的有多少个。全部累加,最后需要剪掉n(因为我们把需要匹配的整个串也算进去了,要剪掉1*n个)

讲的已经很清楚了,如果不理解或者有疑问的话可以提出来,也可以私信问我。

code:

#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;
}

2018-09-15 15:53:14 in 题解